二叉樹前序、后序和后序遍歷（非遞歸實現）

二叉樹前序、后序和后序遍歷（非遞歸實現）

（1）前序

    我們知道，前序遍歷的順序是根左右，當根節點不為空時，該節點才可以被打印。目前書上常見對樹的遍歷都是采用遞歸的方法實現的，我們知道遞歸必然會產生中斷，也就是有現場信息的保存，如果要實現非遞歸，那么我們必須自己要有一個棧，用來保存現場信息。

    我先給出實現的偽代碼，稍后我將解釋為什么需要這么做，為何要用到這些條件。

    偽代碼如下：

1 void PreOrderTraverse(BinaryTree root)

2 {

3    BinaryTree cur = root;

4    stack<BinaryTree> s;

5    while(null != cur || !s.empty())

6    {

7        while(null != cur)

8        {

9            print cur.data;

10           s.push(cur);

11           cur = cur.left;

12       }

13       if(!s.empty()) {

14           cur = s.top();

15           s.pop();

16           cur = cur.right;

17       }

18   }     //loop end!

19}

    第3行的cur就相當于遞歸中的現場信息，而第4行聲明到的棧則用來保存它。

    第5行的循環條件暫時不用關注，我們看第7行到第12行的代碼，它主要做的是，如果當前節點不為空，則打印，同時將該結點的信息保存到用戶棧中，接著把當前節點改變成它到的左子。當左子為空時，循環結束。

    接著再看第13行到第16行的代碼，它做的是取棧頂的現場信息（也就是最后一次保存的現場信息），然后改變當前結點為它的右子。

    最后我們關注這個大循環結束的條件。當第16行執行結束，cur為右結點，可能存在兩種情形:

         ① 右子為空，那么我們從用戶?；謴捅４娴默F場信息。

         ② 右子不為空，那么整個邏輯不變，按照之前的方法進行處理。

    所以我們得出整個循環繼續得以執行的條件是結點不為空或者用戶棧不空，滿足二者其一即可。

（2）后序

    后序遍歷的順序是左右根，我們要保證根節點在左孩子和右孩子訪問之后才能訪問。

    首先我們來考慮一個結點P能被訪問的條件：

        ① P的左孩子和右孩子都為空，則該節點可以被直接訪問；

        ② P有左孩子或右孩子，但左孩子和右孩子都已經被訪問過，那么結點P也可以直接訪問。

    如果不是上面兩種條件，那我們將P的右孩子和左孩子依次入棧，這樣就可以保證每次取棧頂元素的時候，左孩子在右孩子的前面被訪問，左孩子和右孩子都在根節點的前面被訪問。

    實現的偽代碼如下:

void PostOrderTraverse(BinaryTree root)

{

   if(null == root)

      return;

   stack<BinaryTree> s;

   s.push(root);

   BinaryTree pre = null;

   BinaryTree cur;

   while(!s.empty())

   {

      cur = s.top();

      if(null == cur.lchild) && null == cur.rchild

         || (null != pre) && (pre == cur.lchild || pre == cur.rchild)) {

         print cur.data;

      s.pop();

      pre = cur;

   }

      else {

         if(null != cur.rchild) {

            s.push(cur.rchild);

         }

         if(null != cur.lchild) {

            s.push(cur.lchild);

         }

      }

   }     //loop end!

}