c语言非递归遍历二叉树

运行结果正确
其实也不难，牢牢记住栈是用来放右节点的就行了。

#include
#include
typedef struct tree_node{int val;struct tree_node *left;struct tree_node *right;
}tree;
//top是为非递归的栈提供的
int top=-1;
//创建新树
int creat_tree(tree **t){int val;scanf("%d",&val);if(val==-1){*t=NULL;}else{*t=(tree*)malloc(sizeof(struct tree_node));(*t)->val=val;printf("输入%d左节点\n",val);creat_tree(&((*t)->left));printf("输入%d右节点\n",val);creat_tree(&((*t)->right));}return 1;
}
//递归先序遍历
void pre_tra(tree *t){if(t!=NULL){printf("%d ",t->val);pre_tra(t->left);pre_tra(t->right);};
}
//非递归实现
//入栈
//二级指针就相当于栈的数组，所以我们构造的这个栈是用数组实现的
void push(tree **base,tree *elem){base[++top]=elem;
}
//出栈
void pop() {if(top==-1){return ;}top--;
}
//非递归遍历
void pre_tra1(tree *t){tree *base[20];//这就是个二级指针tree *t1=t;//防止破环原树tree *temp;//移动指针push(base,t1);//当栈不空的时候，说明还有右儿子没遍历 while(top!=-1){temp=base[top];pop();//把左儿子遍历干净 while(temp){//访问根节点 printf("%d ",temp->val);//栈就是用来放右儿子的 if(temp->right){push(base,temp->right);};temp=temp->left;}}} int main(){tree *t;printf("输入根节点\n");creat_tree(&t);printf("递归遍历结果为\n");pre_tra(t);printf("\n非递归遍历结果为\n");pre_tra1(t);return 0;
}