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

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

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

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

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

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

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

? ? ? ? ? ? ? ? ? ??

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

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

? ? ? ? ? ? ? ? ? ?

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

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

步驟如下：

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

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

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

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

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ??

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

---- 二叉樹(shù)轉(zhuǎn)換為樹(shù)是樹(shù)轉(zhuǎn)換為二叉樹(shù)的逆過(guò)程，反過(guò)來(lái)做。步驟如下：

--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)用線連接起來(lái)。

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

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

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

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ?

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

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

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

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

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

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

5、樹(shù)與森林的遍歷

---- 樹(shù)的遍歷分為兩種方式：

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

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

? ? ? ? ? ? ?

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

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

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

構(gòu)成的森林。

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

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

? ? ? ? ? ?

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

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

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

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

找到了對(duì)樹(shù)和森林這種復(fù)雜問(wèn)題的簡(jiǎn)單解決辦法。