樹、森林與二叉樹的轉(zhuǎn)換

1、樹轉(zhuǎn)換為二叉樹

---- 將樹轉(zhuǎn)換為二叉樹的步驟如下：

--1）加線。在所有兄弟結(jié)點(diǎn)之間加一條連線。

--2）去線。對樹中每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其他孩子結(jié)點(diǎn)之間的連線。

--3）層次調(diào)整。以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

注意第一個(gè)孩子是二叉樹結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過來的孩子是結(jié)點(diǎn)的右孩子。

例如下圖，一棵樹經(jīng)過三個(gè)步驟轉(zhuǎn)換為一棵二叉樹。

? ? ? ? ? ? ? ? ? ??

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

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

? ? ? ? ? ? ? ? ? ?

2、森林轉(zhuǎn)換為二叉樹

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

步驟如下：

--1）把每個(gè)樹轉(zhuǎn)換為二叉樹。

--2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，用線連接起來。

當(dāng)所有的二叉樹連接起來后就得到了由森林轉(zhuǎn)換來的二叉樹。

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

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ??

3、二叉樹轉(zhuǎn)換為樹

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

--1）加線。若某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，則將這個(gè)左孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子結(jié)點(diǎn).....右孩子的右孩子的右孩子的結(jié)點(diǎn)。。

左孩子的n個(gè)右孩子結(jié)點(diǎn)都作為此結(jié)點(diǎn)的孩子。將該結(jié)點(diǎn)與這些右孩子結(jié)點(diǎn)用線連接起來。

--2）去線。刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線。

--3）層次調(diào)整。使之結(jié)構(gòu)層次分明。

---- 轉(zhuǎn)換過程如下圖所示：

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ?

4、二叉樹轉(zhuǎn)換為森林

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

如果是轉(zhuǎn)換成森林，步驟如下：

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

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

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

5、樹與森林的遍歷

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

--1）一種是先根遍歷樹，即先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹。

--2）另一種是后根遍歷，即先依次后根遍歷每棵子樹，然后再訪問根結(jié)點(diǎn)。

? ? ? ? ? ? ?

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

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

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

構(gòu)成的森林。

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

樹構(gòu)成的森林。

? ? ? ? ? ?

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

通過對森林轉(zhuǎn)化為的二叉樹進(jìn)行分析發(fā)現(xiàn)：

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

---- 當(dāng)以二叉鏈表做樹的存儲結(jié)構(gòu)時(shí)，樹的先根遍歷和后根遍歷完全可以借用二叉樹的前序遍歷和中序遍歷的算法來實(shí)現(xiàn)。

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