关于二叉树后序遍历的三种方法

采用两个辅助栈来进行后序遍历
由于后序遍历的顺序是“左-右-根”，将其逆序则得到“根-右-左”，发现和前序遍历的顺序很相似，所以可以将前序遍历的代码进行改动得到后序遍历的非递归代码。

void PostOrder(BiTree T)
{
    if(T == NULL) return;
    InitStack(S1);
    InitStack(S2);
    BitNode *p = NULL;
    Push(S1, T);
    while(!Empty(S1))
    {
        Pop(S1, p);
        Push(S2, p);
        if(p->lchild != NULL)
        {
            Push(p->lchild, S1);
        }
        if(P->rchild !=NULL)
        {
            Push(p->rchild, S1);
        }
    }

    while(!Empty(S2))
    {
        Pop(S2, p);
        visit(p);
    }

}

在前序遍历中，由于栈的特性，先访问右子树再访问左子树，而后序遍历的逆序的特点，直接访问左子树，再访问右子树，最后在将“根-右-左”序列输出到辅助栈S2中，再将其输出即可得到后序遍历 序列。

采用一个结构体，里面包含二叉树的结点和一个用以判断左右子树是否访问的标记

typedef struct StackElem
{
    BitNode *pt;
    int flag;
}StackElem;

void PostOrder(BiTree T)
{
    StackElem e;
    InitStack(S);
    BitNode *p = T;
    BitNode *t;
    if(p = NULL)    return;
    while(p || !IsEmpty(S))
    {
        while(p != NULL)
        {
            e.pt = p;
            e.flag = 0;
            Push(S, e);
            p = p->lchild;
        }
        Pop(S, e);
        p = e.pt;
        if(e.flag == 0)
        {
            e.flag = 1;
            Push(S, e);
            p = p->rchild;
        }
        else
        {
            visit(p);
            p = NULL;
        }
    }
}

只采用一个指针来记录上次访问的结点

void PostOrder(BiTree T)
{
    InitStack(S);
    BitNode *p = T, *r = NULL;
    while(p || !IsEmpty(S))
    {
        if(p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            GetTop(S, p);
            if(p->rchild && p->rchild != r)
            {
                p = p->rchild;
                Push(S, p);
                p = p->lchild;
            }
            else
            {
                Pop(S, p);
                visit(p);
                r = p;
                p = NULL;
            }
        }
    }
}