数据结构-二叉树的前序，中序，后序遍历（非递归实现）

之前在实现二叉树的前中后序遍历时，采用了递归版本实现，比较简单。 这次，我采用了非递归版本实现。需要借助到栈的基本操作。

前序

根据之前学到的，前序实际上就是先访问，再遍历左子树，再遍历右子树。 下面画图解释：

void PreOrderByLoop(TreeNode* root) { if(root==NULL) { return; } TreeNode* cur=root; SeqStack s; TreeNode* value; SeqStackInit(&s); while(SeqStackEmpty(&s)!=0||cur!=NULL) { while(cur!= NULL) { if(cur!=NULL) { printf("%c ",cur->data); SeqStackPush(&s,cur); cur=cur->lchild; } } SeqStackTop(&s,&value); SeqStackPop(&s); cur=value->rchild; } }

中序

中序与前序的思路基本类似，只是调换了一下入栈和访问顺序。 还是画图来解释一下：

void InOrderByLoop(TreeNode* root) { if(root==NULL) { return; } TreeNode* cur=root; SeqStack s; TreeNode* value; SeqStackInit(&s); while(SeqStackEmpty(&s)!=0||cur!=NULL) { while(cur!= NULL) { if(cur!=NULL) { SeqStackPush(&s,cur); cur=cur->lchild; } } SeqStackTop(&s,&value); printf("%c ",value->data); SeqStackPop(&s); cur=value->rchild; } }

后序

后序比前序和中序，多了一个判断的条件，也就是访问节点的条件，要么是该结点无右孩子，要么是从右孩子访问后返回到该节点。所以需要一个prev指针，记录下上一次访问过的结点是谁。

void PostOrderByLoop(TreeNode* root) { if(root==NULL) { return; } TreeNode* cur=root; TreeNode* prev=NULL; SeqStack s; TreeNode* value=NULL; SeqStackInit(&s); while(SeqStackEmpty(&s)!=0||cur!=NULL) { while(cur!= NULL) { if(cur!=NULL) { SeqStackPush(&s,cur); cur=cur->lchild; } } SeqStackTop(&s,&value); if(value->rchild==NULL||value->rchild==prev) { //如果此时的value没有右孩子，可以直接访问。 //或者此时 value的右孩子已经被访问了，就可以直接访问 printf("%c ",value->data); prev=value; SeqStackPop(&s); } else { cur=value->rchild; } } }