详解二叉树的递归遍历与非递归遍历—

详解二叉树的递归遍历与非递归遍历——（二）

非递归遍历

上一边文章中，咱们谈到了二叉树的递归遍历，也是十分的简单哈，这回又继续将非递归遍历写一下。从前序开始扯吧，哈哈！！！
先给出存储结构：

typedef struct Node{
int data; //保存节点中的值
struct BTNode *lchild; //左孩子指针
struct BTNode *rchild; //右孩子指针
}BTNode,*BiTree;

1.前序遍历

先访问根结点；
然后在访问左子树；
最后访问右子树；

前序遍历大体流程：

首先，扫描并访问根结点1，（这里用到一个保存节点的栈）然后将根结点保存到栈中，并将根节点指向他的左孩子2（如果存在）；
然后开始循环，每一次循环都访问改结点，然后将该结点压入栈中，一直循环到某一时刻的左孩子为NULL的时候，也就是访问到了A结点的左子树中的最深层左孩子7；
则进行下一步，将结点指针指向该7的右孩子（如果存在），先访问该结点，然后继续访问该右孩子的左子树，重复第一步，就会一直自底向上的将1结点的左子树访问完毕；
最后，当回到1结点时，根结点1和他的左子树已经全部遍历完成，则开始遍历右子树了。流程和第3步类似。

在这里插入图片描述

代码重现：

void  PreOrder(BiTree  T){
    InitStack(S);    //初始化栈
    BiTree p = T;    //将P指向T，作为遍历指针
    while(p || !StackEmpty(S)){//p不为空或者栈不为空时候，继续遍历
        if(p){
            visit(p);    //访问根结点
            Push(S,p);    //将根节点压入栈中
            p = p->lchild; //往左子树走
        }//if
        //p为空跳到else表示已经访问到了左子树的最底层的那个左孩子；
        //现在要做的是从下往上一次打印左右节点（实际上只有右节点了）；
        else{
            Pop(S,p);//弹出栈顶元素，访问
            p = p->rchild; //往右子树走
        }
    }//while
}//PreOrder

可以说从整个流程比较简单。

2.中序遍历

中序遍历可以说是三种非递归遍历最简单的一种的。

先访问左子树；
然后在访问根结点；
最后访问右子树；

中序遍历大体流程：

先扫描根结点（并非访问根结点）的所有的左结点，并将它们一一入栈，直到扫描到最深层的左结点，即停止该操作。进而将栈顶元素弹出，这里设为*p,（显然 *p没有左孩子结点或左孩子结点均已经被访问郭），访问它。然后扫描该结点的右孩子结点，将其进栈，在扫描该右孩子的所有结点并一一进栈，如此继续，直到栈为空位置。

void InOrder(BiTree T){

 InitStack(S);    //初始化栈
 BiTree p = T;    //p作为遍历指针
 while(p || !EmptStack(S)){     //只要p不为空，且栈不为空，就继续扫描
     if(p){    //每次遇到非空二叉树，就向左走
         push(S,p);
         p=p->lchild;    
     }else{    //跟指针退栈，访问根结点，遍历右子树
         Pop(S,p);    //退栈
         visit(p);    //访问根结点
         p=p->rchild;    //在向右子树走
     }
 }

}

3.后序遍历

都说后续非递归是最难的。可是换个角度想想：你把最难的都掌握了，你就肯定不会比别人差，可能写的不好，但是请看下去。
直接谈后序遍历的思想吧！
————后序遍历就是先访问左子树，在访问右子树，最后访问根结点，当用堆栈来存储结点时，应该分清返回根节点时是从左子树访问返回的还是从右子树返回的，
①因为如果是访问了左子树返回的，那么久还需要去访问右子树；
②如果是从右子树返回的，则可以直接访问根结点了，这一点需要特别注意。
所以这里借助辅助指针 preNode,指向醉经访问过的结点。也可在结点中增加一个标志域，记录是否已被访问。

void PostOrder(BiTree T){
    InitStack(S);
    p=T;
    preNode=NULL;
    while(p && !EmptyStack(S)){
        if(p){    //走到最左边的结点
            push(S,p);
            p = p->lchild;
        }else{    //向右
            GetTop(S,p);    //去栈顶节点
            if(p->rchild && p->rchild != preNode){
                //若右子树存在，且未被访问过
                p = p->rchild;    //转向右子树
                push(S,p);        //压入栈
                p = p->lchild;    //再走到最左    
            }//if
            else{//否则，直接访问根结点了
                pop(S,p);    //将该结点弹出
                visit(p);    //访问改结点
                preNode = p;    //记录最近访问过的结点
                p = NULL;    //结点访问完后，重置指针p
            }//else
        }//else向右结尾
    }//while
}//PostOrder