二叉树的先序、中序、后序遍历递归函数和非递归函数的实现（c++）

找了很多代码都无法直接运行，那我就给大家一个可以直接运行的，记得理解过程哦！！！

#include 
#include
#include 
#include 

struct treenode
{
    char val;
    struct treenode *left=NULL;
    struct treenode *right=NULL;
};

//建立二叉树
treenode* build_tree(char* s,int i)
{

    if(i>=strlen(s))return NULL;
    if(s[i]=='#')return NULL;
    //printf("%dn",i);
    treenode* root=(treenode*)malloc(sizeof(treenode));
    root->val=s[i];
    if(2*i+1left=build_tree(s,2*i+1);
    if(2*i+2right=build_tree(s,2*i+2);
    return root;
}
//先根递归遍历
void preOrder(treenode* root)
{
    if(root==NULL)return ;
    printf("%c",root->val);
    if(root->left!=NULL)preOrder(root->left);
    if(root->right!=NULL)preOrder(root->right);
}
//中根递归遍历
void inOrder(treenode* root)
{
    if(root==NULL)return ;
    inOrder(root->left);
    printf("%c",root->val);
    inOrder(root->right);
}
//后根递归遍历
void postOrder(treenode* root)
{
    if(root==NULL)return ;
    postOrder(root->left);
    postOrder(root->right);
    printf("%c",root->val);
}
//先根非递归遍历
//ABC#DE#
void Pre1Order(treenode *bt)
{
    treenode **s;
	treenode *p;
	int top=-1;
	//创建栈；
	s=(treenode **)malloc((100+1)*sizeof(treenode *));
	//初始化栈；
	s[++top]=bt;
	//非递归前序遍历；
	while(top!=-1)
	{
		p=s[top--];
		printf("%c",p->val);    //栈的特点，先进后出；
		if(p->right)
			s[++top]=p->right;
		if(p->left)
			s[++top]=p->left;
	}
	free(s);
}

void In1Order(treenode *bt)
{
	treenode **s;
    treenode *p,*q;
    int top=-1;
	//创建栈；
	s=(treenode **)malloc((100+1)*sizeof(treenode *));
	//非递归中序遍历；
    if(bt)
    {
        while(bt)   //一直遍历左子树直到该结点的左孩子空为止；
        {
            s[++top]=bt;   //将所有左孩子存入栈中；
            bt=bt->left;     //指向下一个左子树；
        }
        while(top!=-1)  //栈空时结束循环；
        {
            p=s[top--];//刚开始将最p指向左下角的左孩子，并且移向该结点的父结点；
            printf("%c",p->val);  //输出左下角的结点；
            while(p->right)  //遍历移动后结点有没有右结点；
            {
                s[++top]=p->right;   //将这个结点的右子树入栈；
                q=p->right;		  //这个右子树结点赋给q；
                while(q->left)      //判断结点q有没有左子树；
                {
                    s[++top]=q->left;  //有左子树，将与这个结点相连的所有左子树都入栈；
                    q=q->left;
                }
                break;   //结束当前循环，回到第二个while循环继续刚才的步骤；
            }
        }
    }
}


void Post1Order(treenode *bt)
{
	treenode **s;
	treenode *p;
    int top=-1;
	//创建栈；
	s=(treenode **)malloc((100+1)*sizeof(treenode *));
	//非递归后序遍历；
    do
    {
        while(bt)     //一直遍历左子树直到该左子树的左孩子空为止；
        {
            s[++top]=bt;     //将所有左孩子存入栈中；
            bt=bt->left;   //指向下一个左子树；
        }
        p=NULL;
        while(top!=-1)
        {
            bt=s[top];
            if(bt->right==p)  //p:表示为null，或者右子节点被访问过了;
            {
                printf("%c",bt->val);   //输出结点数据域；
                top--;           //输出以后，top--；
                p=bt;  //p记录下刚刚访问的节点;
            }
            else
            {
                bt=bt->right;   //访问右子树结点；
                break;
            }
        }
    }while(top!=-1);
}



int main()
{
    char s[100]={0};
    gets(s);
    treenode* root=(treenode*)malloc(sizeof(treenode));
    root=build_tree(s,0);
    printf("递归遍历：n");
    printf("先根 ");
    preOrder(root);
    printf("n");

    printf("中根 ");
    inOrder(root);
    printf("n");
    printf("后根 ");
    postOrder(root);
    printf("n");
    printf("非递归遍历：n");
    printf("先根 ");
    Pre1Order(root);
    printf("n");
    printf("中根 ");
    In1Order(root);
    printf("n");
    printf("后根 ");
    Post1Order(root);
    printf("n");
    return 0;

}