王道課後習題4.3.3：編寫後序周遊二叉樹的非遞歸算法

後序：
void postorder_1(TNode* bt)
{
    Stack S;
    InitStack(S);
    TNode* p=bt;
    TNode* r=NULL;
    while(!StackEmpty(S)||p!=NULL)
    {
        while(p!=NULL)
        {
            Push(S,p);
            p=p->lchild;
        }
        GetTop(S,p);
        if(p->rchild!=NULL&&p->rchild!=r)
            p=p->rchild;//轉向右子樹
        else
        {
            Pop(S,p);
            visit(p);
            r=p;//标記右孩子已經通路過了
            p=NULL;//通路完一個結點之後需要置空，不置空的話又會把這個結點壓進去

        }
    }
}
void postorder_2(TNode* &L)
{
    Stack S;
    InitStack(S);
    TNode* p=L;
    TNode* r=NULL;
    while(!StackEmpty(S)||p!=NULL)
    {
        if(p!=NULL)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            GetTop(S,p);
            if(p->rchild!=NULL&&p->rchild!=r)
                p=p->rchild;
            else
            {
                Pop(S,p);
                visit(p);
                r=p;//标記右孩子已經通路過了
                p=NULL;//通路完一個結點後需要置空，不置空則又會把這個結點壓進去
            }
        }
    }
}
/*
  A
 / \
B   C
先序序列：ABC
後序序列：BCA
逆後序序列：ACB=先序周遊對左右子樹的周遊順序互換
Stack1存放逆後序周遊，然後壓入Stack2
Stack2的元素全部出棧所得序列即為後序周遊序列
*/
void postorder_3(TNode* bt)
{
    TNode* p;
    Stack S1,S2;
    InitStack(S1);
    InitStack(S2);
    Push(S1,bt);
    while(StackEmpty(S1)!=true)
    {
        Pop(S1,p);
        Push(S2,p);
        if(p->lchild!=NULL)
            Push(S1,p->lchild);
        if(p->rchild!=NULL)
            Push(S1,p->rchild);
    }
    while(StackEmpty(S2)!=true)
    {
        Pop(S2,p);
        visit(p);
    }
}