C語言實現二叉樹的遞歸遍歷與非遞歸遍歷

本文實現了對二叉樹的遞歸遍歷和非遞歸遍歷，當然還包括了一些棧操作。

二叉樹的遍歷本質上其實就是入棧出棧的問題，遞歸算法簡單且容易理解，但是效率始終是個問題。非遞歸算法可以清楚的知道每步實現的細節，但是乍一看不想遞歸算法那麼好理解，各有各的好處吧。接下來根據下圖講講樹的遍歷。

1、先序遍歷：先序遍歷是先輸出根節點，再輸出左子樹，最後輸出右子樹。上圖的先序遍歷結果就是：ABCDEF

2、中序遍歷：中序遍歷是先輸出左子樹，再輸出根節點，最後輸出右子樹。上圖的中序遍歷結果就是：CBDAEF

3、後序遍歷：後序遍歷是先輸出左子樹，再輸出右子樹，最後輸出根節點。上圖的後序遍歷結果就是：CDBFEA

其中，後序遍歷的非遞歸算法是最復雜的，我用了一個標識符isOut來表明是否需要彈出打印。因為只有當節點的左右子樹都打印後該節點 才能彈出棧打印，所以標識isOut為1時打印，isOut初始值為0，這主要是為了處理非葉子節點。由後序遍歷的原理決定，左右子樹都被打印該節點才能打印，所以該節點肯定會被訪問2次，第一次的時候不要打印，第二次打印完右子樹的時候打印。葉子節點打印完後將isOut置為1。（純粹是自己想的，應該還有邏輯更簡單的算法）

isOut處理具體如下：

• 所有節點入棧的時候初始化為0；
• 葉子節點打印輸出後將isOut置為1；
• 非葉子節點分兩種情況。如果存在左子樹，則輸出左子樹後將isOut置為1，此時指針已獲得其右子樹節點；如果不存在左子樹，則將isOut置為1，此時指針已獲得其右子樹節點；在代碼中分別體現在 if ( (p->lchild) && (p->lchild->isOut == 1) ) {//如果存在左子樹,並且左子樹已經遍歷完，則說明該節點已經入棧，不用再次Push,直接走向右子樹
  p->isOut = 1;
  p = p->rchild;
  }和 if (!StackEmpty(s))
  {
  GetTop(s,p);
  if ( p->lchild == NULL )
  p->isOut = 1; //右子樹已輸出，將父節點isOut置1
  }；
• 遇到isOut=1的時候，說明左右子樹都已輸出，所以該節點也出棧打印出來。

以中序遍歷為例，看看棧的內容是如何變化的：

具體的代碼實現如下：見 http://www.linuxidc.com/Linux/2013-11/92544p2.htm