二叉樹後序周遊

關于書中bug

近日在看書過程中，發現書中的僞代碼或是源碼有些錯誤，不禁告誡自己牢記以下幾點：

1、思想很重要，行動更重要，把想法變成程式，加幾個測試用例跑一跑，有結果才有發言權

2、程式架構很重要，細節更重要。

總之呢，不能懶，自己敲了驗證了，變成自己的才最重要。

不扯皮了，進入正題：

二叉樹後序周遊的非遞歸實作

這是清華出版社王紅梅老師資料結構(C++版)裡的一段僞碼： 節點的結構為：

struct BiNode
{
        int data;
        BiNode *lchild, *child;
};
           

後序周遊為

void PostOrder(BiNode *root)
{
        top=-1;
        while(root!=NULL || top !=-1)
        {
                while(root !=NULL)
                {
                        top++;
                        s[top].ptr=root;
                        s[top].flag=1;
                        root=rot->lchild;
                }
                while(top !=-1 && s[top].flag==2)
                {
                         root=s[top--].ptr;
                         cout<<root->data;
                }
                if(top!=-1)
                {
                         s[top].flag=2;
                         root=s[top].ptr->rchild;
                }
        }
}
           

其中s是這樣的類型的一個數組：

struct element
{
        BiNode *ptr;
        int flag;
}
           

ptr存儲節點，flag标志節點的右子節點是否已周遊(1--否，2--是); 我們看下上述的後序周遊算法，顯然用s模拟棧的存儲結構，top訓示棧頂。當節點為空并且棧為空時，說明樹是空的或者已經周遊完。否則我們執行周遊操作，目前節點非空，将其入棧并周遊其左子節點，直到左子結點為空，注意此時尚未周遊其右子節點，故flag置為1.然後while循環判斷是否已經周遊過右子節點，若已周遊,根據後序周遊特點，此時節點可以出棧了，然後将目前棧頂節點flag置為2，并開始周遊其右子節點,,,,,,,,         這樣一個個周遊後，最終棧中将隻剩下根節點，我們将進入while循環，并将其彈出，那麼後序周遊就完成了，然而不幸的是，我們将彈出的根節點指派給了root，然後呢，在第一個while循環判斷時，因為root !=NULL,好吧，我們隻能一遍又一遍的重複上述過程........... 其實呢錯就錯在彈出操作哪裡，我們可以改為：

cout<<s[top--].ptr->data;
           

OK啦~