數據結構-遍歷二叉樹

在樹中搜索某種特徵的節點，或者對樹中全部節點逐一進行處理。

遍歷二叉樹是指以一定的次序訪問二叉樹中的每個節點，並且每個節點僅被訪問一次；

例如：查詢節點數據閾的內容，或輸出它的值，或者找出節點位置，活著其他操作。

遍歷過程實質是把二叉樹的節點進行線性排列的過程，遍歷時是先訪問根節點還是先訪問子樹，要有遍歷規則，採用不同的規則，則有不同的結果。

一顆非空二叉樹是由根節點／左子樹／右子樹三個基本部分組成。用D，L，R分別表示訪問根節點／遍歷左右子樹，則有6重遍歷形式，A33 ，分別DLR、LDR、LRD、DRL、RDL、RLD。

1、 先跟遍歷

如果跟不空，則依次執行訪問根節點，按先跟次序遍歷左子樹，按先跟次序遍歷右子樹，否則返回。

2、 中跟遍歷

如果跟不空，按中跟次序遍歷左子樹，訪問根節點，按中跟次序遍歷右子樹，否則返回。

3、 後跟遍歷

如果跟不空，按後跟次序遍歷左子樹，按後跟次序遍歷右子樹，最後訪問根節點，否則返回。

同時還可計算樹的深度，節點個數和葉子節點個數。

一般樹轉化為二叉樹：主要根據樹的孩子-兄弟存儲方式來的，步驟是：

（a）加線：在各兄弟節點之間用虛線相連。可理解為每個節點的兄弟指針指向它的一個兄弟。

(b) 抹線：對每個節點僅保留它與其最左一個孩子的連線，抹去該節點與其孩子之間的連線。可理解為每個節點僅有一個孩子指針，讓它指向自己的長子。

(c) 旋轉：把虛線改為實線從水平方向向下旋轉45度，成右寫下方向，原樹中實線成左斜下方向，就OK了

由於二叉樹中各節點的右孩子都是原一般樹中該節點的兄弟，而一般樹的根節點又沒有兄弟節點，因此所生成的二叉樹的根節點沒有右子樹。在所生成的二叉樹中某一節點的左孩子仍是原來書中該節點的長子，並且是它的最左孩子。

圖是一個是一般樹轉為二叉樹的實例：

來再還原回來：二叉樹還原為一般樹

必須是由某一棵樹轉化而來的且沒有右子樹，

（a） 加線：若某節點i是雙親節點的左孩子，則將該節點i的右孩子以及當且僅當連續地沿著右孩子的右鏈不斷搜索到所有右孩子都分別與節點i的雙親節點用虛線鏈接。

（b） 抹線：把原二叉樹中所有雙親節點與其右孩子的連線抹去。這裡的右孩子實質是原一般樹節點的兄弟，抹去的連線是兄弟關係。

（c)整理：把虛線改成實現，把節點按層次排列。

以上，二叉樹&樹～