5.13.樹、森林與二叉樹的轉換

當使用"孩子兄弟表示法"存儲樹或森林時，最終會呈現出與二叉樹類似的形態，

所以樹、森林與二叉樹之間的轉換本質上就是畫出采用孩子兄弟表示法存儲的樹和森林。

一."樹->二叉樹"的轉換：

1.例一：

以上述圖片左邊的樹為例，

現將該樹轉化為二叉樹，本質上就是用孩子兄弟表示法存儲該樹，

"樹->二叉樹"轉換技巧：

首先在一棵二叉樹中畫出樹的根節點
按"樹的層序"依次處理每個結點

上述圖片左邊的樹的根結點為A，因此轉換后的二叉樹的根結點也為A，

如下圖：

如上圖，

接下來需要按"樹的層序"依次處理每個結點，這是什么意思呢？

也就是說先處理樹中第一層的A，再處理第二層的B、C，接下來處理第三層的D、H、F、E、J、K，最后處理第四層的G、I、L，就是一層一層的按順序處理結點，按這種方式處理的話不容易亂，

首先處理樹中第一層的A，處理的方法如下：

如上圖，

首先要觀察當前處理的結點即A在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于A結點來說，他有B、C兩個孩子，因此需要把B、C用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把A結點的第一個孩子即B掛在當前處理的結點即A的左指針上，

如下圖：

如上圖，

A結點處理完畢，接下來處理B結點，同理，

首先要觀察當前處理的結點即B在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于B結點來說，他有D、H、F三個孩子，因此需要把D、H、F用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把B結點的第一個孩子即D掛在當前處理的結點即B的左指針上，

如下圖：

如上圖，

B結點處理完畢，接下來處理C結點，同理，

首先要觀察當前處理的結點即C在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于C結點來說，他有E、J、K三個孩子，因此需要把E、J、K用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把C結點的第一個孩子即E掛在當前處理的結點即C的左指針上，

如下圖：

如上圖，

C結點處理完畢，接下來按照"樹的層序"應該處理D結點，同理，

首先要觀察當前處理的結點即D在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于D結點來說，顯然沒有孩子，所以D結點不需要做任何處理；

D結點處理完畢，接下來處理H結點，同理，

首先要觀察當前處理的結點即H在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于H結點來說，他有G、I、L三個孩子，因此需要把G、I、L用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把H結點的第一個孩子即G掛在當前處理的結點即H的左指針上，

如下圖：

如上圖，

H結點處理完畢，接下來按照"樹的層序"應該依次處理F、E、J、K、G、I、L結點，同理，

首先要觀察當前處理的結點在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于F、E、J、K、G、I、L結點來說，顯然都沒有孩子，所以F、E、J、K、G、I、L結點都不需要做任何處理，

至此，就完成了"樹->二叉樹"的轉換，

如下圖：

2.例二：原理同例一

以上述圖片左邊的樹為例，

現將該樹轉化為二叉樹，本質上就是用孩子兄弟表示法存儲該樹，

上述圖片左邊的樹的根結點為A，因此轉換后的二叉樹的根結點也為A，

如下圖：

如上圖，

首先要觀察當前處理的結點即A在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于A結點來說，他有B、C、F、L四個孩子，因此需要把B、C、F、L用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把A結點的第一個孩子即B掛在當前處理的結點即A的左指針上，

如下圖：

如上圖，

A結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理B結點，

首先要觀察當前處理的結點即B在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于B結點來說，他有D、H兩個孩子，因此需要把D、H用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把B結點的第一個孩子即D掛在當前處理的結點即B的左指針上，

如下圖：

如上圖，

B結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理C結點，

首先要觀察當前處理的結點即C在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于C結點來說，他有E、J兩個孩子，因此需要把E、J用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把C結點的第一個孩子即E掛在當前處理的結點即C的左指針上，

如下圖：

如上圖，

C結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理F結點，

首先要觀察當前處理的結點即F在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于F結點來說，他只有一個孩子即K結點，

因此接下來要在創建的二叉樹中把F結點的第一個孩子即K掛在當前處理的結點即F的左指針上，

如下圖：

如上圖，

F結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理L結點，

首先要觀察當前處理的結點即L在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于L結點來說，L結點沒有孩子，所以不需要處理，

如下圖：

如上圖，

L結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理D結點，

首先要觀察當前處理的結點即D在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于D結點來說，他只有一個孩子即G結點，

因此接下來要在創建的二叉樹中把D結點的第一個孩子即G掛在當前處理的結點即D的左指針上，

如下圖：

如上圖，

D結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理H結點，

首先要觀察當前處理的結點即H在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于H結點來說，H結點沒有孩子，所以不需要處理，

如下圖：

如上圖，

H結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理E結點，

首先要觀察當前處理的結點即E在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于E結點來說，他只有一個孩子即I結點，

因此接下來要在創建的二叉樹中把E結點的第一個孩子即I掛在當前處理的結點即E的左指針上，

如下圖：

如上圖，

E結點處理完畢，接下來按照"樹的層序"應該依次處理J、K、G、I結點，同理，

首先要觀察當前處理的結點在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于J、K、G、I結點來說，顯然都沒有孩子，所以J、K、G、I結點都不需要做任何處理，

至此，就完成了"樹->二叉樹"的轉換，

如下圖：

二."森林->二叉樹"的轉換：

1.例一：

如上圖，

"森林->二叉樹"的轉換思路與"樹->二叉樹"的轉換思路類似，

唯一需要注意的是第一步中樹只有1個根結點，而森林至少有2兩個平級的根結點，

森林中所有的根結點視為平級的兄弟結點，

所以森林轉換為二叉樹的時候，第一步需要把森林中所有的根結點用右指針"串成糖葫蘆"，

本例中森林的根結點為A、D、G，

如下圖：

如上圖，

接下來按照"森林的層序"依次處理每個結點，"森林的層序"就是指把整個森林看作一個整體，

第一層就是A、D、G，第二層就是B、C、E、H、I、J，第三層就是F、K、L、M、N、O，第四層就是P，因此處理順序就是A->D->G->B->C->E->H->I->J->F->K->L->M->N->O->P，

首先處理樹中第一層的A，處理的方法如下：

如上圖，

首先要觀察當前處理的結點即A在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于A結點來說，他有B、C兩個孩子，因此需要把B、C用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把A結點的第一個孩子即B掛在當前處理的結點即A的左指針上，

如下圖：

如上圖，

A結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理D結點，

首先要觀察當前處理的結點即D在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于D結點來說，他只有一個孩子即E結點，

因此接下來要在創建的二叉樹中把D結點的第一個孩子即E掛在當前處理的結點即D的左指針上，

如下圖：

如上圖，

D結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理G結點，

首先要觀察當前處理的結點即G在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于G結點來說，他有H、I、J三個孩子，因此需要把H、I、J用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把G結點的第一個孩子即H掛在當前處理的結點即G的左指針上，

如下圖：

如上圖，

G結點處理完畢，接下來按照"樹的層序"應該依次處理B、C結點，同理，

首先要觀察當前處理的結點在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于B、C結點來說，顯然都沒有孩子，所以B、C結點都不需要做任何處理；

B、C結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理E結點，

首先要觀察當前處理的結點即E在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于E結點來說，他只有一個孩子即F結點，

因此接下來要在創建的二叉樹中把E結點的第一個孩子即F掛在當前處理的結點即E的左指針上，

如下圖：

如上圖，

E結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理H結點，

首先要觀察當前處理的結點即H在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于H結點來說，他有K、L兩個孩子，因此需要把K、L用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把H結點的第一個孩子即K掛在當前處理的結點即H的左指針上，

如下圖：

如上圖，

H結點處理完畢，接下來按照"樹的層序"應該處理I結點，同理，

首先要觀察當前處理的結點即I在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于I結點來說，顯然都沒有孩子，所以I結點都不需要做任何處理；

I結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理J結點，

首先要觀察當前處理的結點即J在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于J結點來說，他有M、N、O三個孩子，因此需要把M、N、O用右指針串成一個"冰糖葫蘆"的形態，

如下圖：

如上圖，

接下來要在創建的二叉樹中把J結點的第一個孩子即M掛在當前處理的結點即J的左指針上，

如下圖：

上圖，

J結點處理完畢，接下來按照"樹的層序"應該依次處理F、K、L結點，同理，

首先要觀察當前處理的結點在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于F、K、L結點來說，顯然都沒有孩子，所以F、K、L結點都不需要做任何處理；

F、K、L結點處理完畢，接下來需要按"樹的層序"依次處理每個結點，因此接下來處理M結點，

首先要觀察當前處理的結點即M在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于M結點來說，他只有一個孩子即P結點，

因此接下來要在創建的二叉樹中把M結點的第一個孩子即P掛在當前處理的結點即M的左指針上，

如下圖：

如上圖，

M結點處理完畢，接下來按照"樹的層序"應該依次處理N、O、P結點，同理，

首先要觀察當前處理的結點在樹中是否有孩子，如果有孩子，那么就要把它所有的孩子"用右指針串成糖葫蘆"，

對于N、O、P結點來說，顯然都沒有孩子，所以N、O、P結點都不需要做任何處理，

至此，就完成了"森林->二叉樹"的轉換，

如下圖：

2.例二：原理同例一

如上圖，

"森林->二叉樹"的轉換思路與"樹->二叉樹"的轉換思路類似，

唯一需要注意的是第一步中樹只有1個根結點，而森林至少有2兩個平級的根結點，

森林中所有的根結點視為平級的兄弟結點，

所以森林轉換為二叉樹的時候，第一步需要把森林中所有的根結點用右指針"串成糖葫蘆"，

本例中森林的根結點為A、C、F、L，

如下圖：

如上圖，

接下來按照"森林的層序"依次處理每個結點，"森林的層序"就是指把整個森林看作一個整體，

第一層就是A、C、F、L，第二層就是B、E、J、K，第三層就是D、H、I，第四層就是G，因此處理順序就是A->C->F->L->B->E->J->K->D->H->I->G，

處理方法同例一，

最終的結果如下圖：

三."二叉樹->樹"的轉換：

1.例一：

以上述圖片左邊的二叉樹為例，

現在把該二叉樹轉換為樹，

"二叉樹->樹"的轉換技巧：

先畫出樹的根結點
從樹的根結點開始，按"樹的層序"恢復每個結點的孩子

(注：按"樹的層序"是為了不容易出錯)

上述圖片左邊的二叉樹的根結點為A，因此轉換后的樹的根結點為A，

如下圖：

如上圖，

接下來從樹的根結點A開始，按"樹的層序"恢復每個結點的孩子(注意是從樹的層序開始恢復，不是二叉樹，也就是按照上述圖片右邊的樹的層序恢復，不是上述圖片左邊的二叉樹)，

那么如何恢復一個結點的孩子呢？

當前處理的是根結點A，也就是要恢復結點A的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點A有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來（如果沒有左孩子，就不需要做恢復孩子的處理;如果有左孩子但沒有"一整串右指針糖葫蘆"，那么只需要把左孩子掛上即可，"一整串右指針糖葫蘆"看作NULL）->對于A結點來說，就需要把它的左孩子即B結點以及"一整串右指針糖葫蘆"即C結點拆下來，再把B、C分別掛在A結點的下方，

如下圖：

如上圖，

至此，A結點的孩子恢復完畢，按照"樹的層序"，接下來要恢復B結點的孩子(注：是按照樹的層序，即按照上述圖片右邊的樹的層序，不是上述圖片左邊的二叉樹)，

當前處理的是B結點，此時就要觀察在上述圖片內左側的二叉樹中結點B有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于B結點來說，就需要把它的左孩子即D結點以及"一整串右指針糖葫蘆"即H、F結點拆下來，再把D、H、F分別掛在B結點的下方，

如下圖：

如上圖，

至此，B結點的孩子恢復完畢，按照"樹的層序"，接下來要恢復C結點的孩子(注：是按照樹的層序，即按照上述圖片右邊的樹的層序，不是上述圖片左邊的二叉樹)，

當前處理的是C結點，此時就要觀察在上述圖片內左側的二叉樹中結點C有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于C結點來說，就需要把它的左孩子即E結點以及"一整串右指針糖葫蘆"即J、K結點拆下來，再把E、J、K分別掛在C結點的下方，

如下圖：

如上圖，

至此，C結點的孩子恢復完畢，按照"樹的層序"，接下來要恢復D結點的孩子(注：是按照樹的層序，即按照上述圖片右邊的樹的層序，不是上述圖片左邊的二叉樹)，

當前處理的是D結點，此時就要觀察在上述圖片內左側的二叉樹中結點D有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于D結點來說，由于D結點的左指針為空，說明D結點沒有左孩子，所以D結點不需要做恢復孩子的處理；

至此，D結點的孩子恢復完畢，按照"樹的層序"，接下來要恢復H結點的孩子(注：是按照樹的層序，即按照上述圖片右邊的樹的層序，不是上述圖片左邊的二叉樹)，

當前處理的是H結點，此時就要觀察在上述圖片內左側的二叉樹中結點H有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于H結點來說，就需要把它的左孩子即G結點以及"一整串右指針糖葫蘆"即I、L結點拆下來，再把G、I、L分別掛在H結點的下方，

如下圖：

如上圖，

至此，H結點的孩子恢復完畢，按照"樹的層序"，接下來要依次恢復F、E、J、K、G、I、L結點的孩子(注：是按照樹的層序，即按照上述圖片右邊的樹的層序，不是上述圖片左邊的二叉樹)，

然而對于F、E、J、K、G、I、L結點來說，F、E、J、K、G、I、L結點在上述圖片內左側的二叉樹中都沒有左孩子，所以F、E、J、K、G、I、L結點都不需要做恢復孩子的處理，

至此，就完成了上述圖片中左邊的"二叉樹->樹"的轉換，

如下圖：

2.例二：原理同例一

四."二叉樹->森林"的轉換：

1.例一：

如上圖，

"二叉樹->森林"的轉換思路與"二叉樹->樹"的轉換思路類似，

唯一需要注意的是森林中至少有兩棵樹，

所以把二叉樹轉換為森林的時候首先要把二叉樹的根結點和根結點右指針上的一整串結點全部拆下來，

上述圖片中左邊的二叉樹的根結點為A，A的右指針上的一整串結點依次為D、G，

因此A、D、G分別是該森林中三棵樹的根結點，

如下圖：

如上圖，

接下來按照"森林的層序"依次恢復結點的孩子，

首先需要恢復A結點的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點A有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于A結點來說，就需要把它的左孩子即B結點以及"一整串右指針糖葫蘆"即C結點拆下來，再把B、C分別掛在A結點的下方，

如下圖：

如上圖，

至此，A結點的孩子恢復完畢，接下來按照"森林的層序"依次恢復結點的孩子，

因此需要恢復D結點的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點D有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于D結點來說，就需要把它的左孩子即E結點拆下來，由于E結點的"一整串右指針糖葫蘆"為空，因此不需要管，所以只需要把E掛在D結點的下方即可，

如下圖：

如上圖，

至此，D結點的孩子恢復完畢，接下來按照"森林的層序"依次恢復結點的孩子，

因此需要恢復G結點的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點G有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于G結點來說，就需要把它的左孩子即H結點以及"一整串右指針糖葫蘆"即I、J結點拆下來，再把H、I、J分別掛在G結點的下方，

如下圖：

如上圖，

至此，G結點的孩子恢復完畢，接下來按照"森林的層序"依次恢復結點的孩子，

因此需要恢復B結點的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點B有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于B結點來說，B結點沒有左孩子，因此B結點不需要做恢復孩子的處理，同理按照"森林的層序"接下來需要恢復C結點的孩子，由于C結點在上述圖片內左側的二叉樹中沒有左孩子，所以也不需要做恢復孩子的處理；

接下來按照"森林的層序"依次恢復結點的孩子，

因此需要恢復E結點的孩子，此時就要觀察在上述圖片內左側的二叉樹中結點E有沒有左孩子，如果有左孩子，那么就要把它的左孩子以及"一整串右指針糖葫蘆"拆下來->對于E結點來說，就需要把它的左孩子即F結點拆下來，由于F結點的"一整串右指針糖葫蘆"為空，因此不需要管，所以只需要把F掛在E結點的下方即可，

如下圖：