樹、森林與二叉樹的轉換

1、樹轉換為二叉樹

---- 將樹轉換為二叉樹的步驟如下：

--1）加線。在所有兄弟結點之間加一條連線。

--2）去線。對樹中每個結點，只保留它與第一個孩子結點的連線，刪除它與其他孩子結點之間的連線。

--3）層次調整。以樹的根結點為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

注意第一個孩子是二叉樹結點的左孩子，兄弟轉換過來的孩子是結點的右孩子。

例如下圖，一棵樹經過三個步驟轉換為一棵二叉樹。

? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ?

2、森林轉換為二叉樹

---- 森林是由若干棵樹組成的，所以完全可以理解為：森林中的每一棵樹都是兄弟，可以按照兄弟的處理辦法來操作。

步驟如下：

--1）把每個樹轉換為二叉樹。

--2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子，用線連接起來。

當所有的二叉樹連接起來后就得到了由森林轉換來的二叉樹。

如下圖所示，將森林的三棵樹轉化為一棵二叉樹：

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ??

3、二叉樹轉換為樹

---- 二叉樹轉換為樹是樹轉換為二叉樹的逆過程，反過來做。步驟如下：

--1）加線。若某結點的左孩子結點存在，則將這個左孩子的右孩子結點、右孩子的右孩子結點.....右孩子的右孩子的右孩子的結點。。

左孩子的n個右孩子結點都作為此結點的孩子。將該結點與這些右孩子結點用線連接起來。

--2）去線。刪除原二叉樹中所有結點與其右孩子結點的連線。

--3）層次調整。使之結構層次分明。

---- 轉換過程如下圖所示：

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ?

4、二叉樹轉換為森林

---- 判斷一棵二叉樹能夠轉換為一棵樹還是森林，只要看這棵二叉樹的根結點有沒有右孩子，有就是森林，沒有就是一棵樹。

如果是轉換成森林，步驟如下：

--1）從根結點開始，若右孩子存在，則把與右孩子結點的連線刪除，再查看分離后的二叉樹，若右孩子存在，則連線刪除......，

直到所有右孩子連線都刪除為止，得到分離的二叉樹。

--2）再將每棵分離后的二叉樹轉換為樹即可。

5、樹與森林的遍歷

---- 樹的遍歷分為兩種方式：

--1）一種是先根遍歷樹，即先訪問樹的根結點，然后依次先根遍歷根的每棵子樹。

--2）另一種是后根遍歷，即先依次后根遍歷每棵子樹，然后再訪問根結點。

? ? ? ? ? ? ?

如上圖的樹，先根遍歷序列為ABEFCDG，后根遍歷序列為EFBCGDA。

---- 森林的遍歷也分為兩種方式：

--1）前序遍歷：先訪問森林中第一棵樹的根結點，然后再依次先根遍歷根的每棵子樹，再依次用同樣方式遍歷除去第一棵樹的剩余樹

構成的森林。

--2）后序遍歷：先訪問森林中第一棵樹，后根遍歷的方式遍歷每棵子樹，然后再訪問根結點，再依次同樣方式遍歷除去第一棵樹的剩余

樹構成的森林。

? ? ? ? ? ?

如上圖有三棵樹的森林，前序遍歷序列的結果是：ABCDEFGHJI。后續(xù)遍歷的結果是：BCDAFEJHIG。

通過對森林轉化為的二叉樹進行分析發(fā)現：

森林的前序遍歷和二叉樹的前序遍歷結果相同，森林的后序遍歷和二叉樹的中序遍歷結果相同。

---- 當以二叉鏈表做樹的存儲結構時，樹的先根遍歷和后根遍歷完全可以借用二叉樹的前序遍歷和中序遍歷的算法來實現。

找到了對樹和森林這種復雜問題的簡單解決辦法。