非递归实现二叉树结点的遍历

考研复习时遇到了二叉树遍历的考点，于是把它按照自己的思路整理出来，可能存在些许错误 ，但大致思想应该没问题。

思想：先序遍历的处理顺序是根、左、右，如果我们把每个结点都看做一个树的根结点时，可以发现在先序遍历时，某结点压栈之后第一次被访问时，就需要处理该结点，然后将左右孩子压栈，等待后续被访问时处理，先序遍历实现起来相对简单。

伪代码如下：

status PreOrderTraverse(BiTree T, status(* visit)(int e)){
    Initstack(S);
    Push(S,T);
    while(!StackEmpty(S)){
        pop(S,P);//出栈
        if(P){
            visit(P->data);
            // 注意根据栈后进先出的特点和先序遍历根左右的访问顺序，因此先把右孩子压入栈中。
            push(S,P->right);
            push(S,P->left);
        }
    }
    return OK;
}

思想：中序遍历的处理顺序是左、根、右，如果我们把每个结点都看做一个树的根结点时，可以发现中序遍历时，在某结点第一次被访问时，需要先处理该结点的左孩子，将其先压栈，左孩子处理完毕返回，第二次访问该结点时，再处理该结点，然后再处理该结点的右孩子。

伪代码如下：

status InTraverse(BiTree T, status(* visit)(int e)){
    Initstack(S);
    P = T;
    Push(S,P);
    while(P || !StackEmpty(S)){
        while(P){
            push(S,P);
            P = P->left;
        }
        if(!StackEmpty(S)){
            Pop(S,P);
            visit(P->data);
            P = P->right;
        }
    }
    return OK;
}

思想：后序遍历是最复杂的，后序遍历的处理顺序是左、右、根，我们需要在某结点的左右孩子都处理完返回时才能处理该结点，也就是说我们需要在第三次访问此结点时才处理它（第一次访问时需要先将其左孩子结点压栈，处理左孩子，第二次访问是在左孩子处理完毕返回时，但此时还需要先处理右孩子，只有等到第三次右孩子处理完毕返回时，才能处理该结点），于是就会有个一个问题，当某结点的左或右孩子处理完毕返回，再次访问该结点，我们怎么知道它是从左孩子返回的还是右孩子返回的。显然从左孩子和右孩子返回的处理方式是完全不同的，因此这里借助一个visit变量记录它是第几次被访问的。

这里有两个方法，虽然有所不同，但是本质思想是一样的。

方法一：在构造二叉树结点结构体时添加visit变量；

伪代码如下：

typedef struct BiTNode{
	int   data;
	struct BiTNode *lchild,*rchild;
	int    visit;  //记录结点被访问的次数
}BiTNode,*BiTree; 

status PostOrderTraverse(BiTree T, status(* visit)(int e)){
    Initstack(S);
    P = T;
    while(P || !StackEmpty(S)){
        while(P){
            push(S,P);
            P->visit = 1; //第一次访问;
            P = P->left;
        }
        if(!StackEmpty(S)){
            GetTop(S,P);
            if(P->visit == 1){
                //只访问过一次，这是第二次访问，需要先处理右子树；
                P->visit++;
                P = P->right;
            }
            else{
                // 已经访问过两次，这是第三次访问，即左右子树都已处理完毕；
                pop(S,P);
                visit(P->data);
                P = NULL;//以p为根结点的子树都已处理完毕，置空，重新获得栈顶元素；
            }
        }
    }
    return OK;
}

方法二：在构造栈结构体时添加visit变量;

结构伪代码如下，遍历过程和方法1一致：

typedef struct SNode{
	BiTNode * Node;
	int    visit;  
}

typedef struct Stack{
	STNode  *base,*Top;
	int    MaxSize;
}