樹、森林及二叉樹的互相轉換 - 資料結構和算法50

樹、森林及二叉樹的互相轉換

讓程式設計改變世界

Change the world by program

從一個屌絲逆襲高富帥的小故事說起。

在這一章節開始的時候我們是從一棵普通的樹開始介紹，在滿足樹的條件下可以是任意形狀，一個結點可以有任意多個孩子，這樣對樹的處理顯然要複雜很多。

是以我們研究出了一些條條框框的限定，如：二叉樹，完全二叉樹，滿二叉樹等。

那麼這時候你就會想，如果所有的樹都像二叉樹一樣友善處理就好了。

普通樹轉換為二叉樹

步驟如下：

1. 加線，在所有兄弟結點之間加一條連線。
2. 去線，對樹中每個結點，隻保留它與第一孩子結點的連線，删除它與其他孩子結點之間的連線。
3. 層次調整，以樹的根結點為軸心，将整棵樹順時針旋轉一定的角度，使之結構層次分明。

森林轉換為二叉樹

1. 把每棵樹轉換為二叉樹。
2. 第一棵二叉樹不動，從第二棵二叉樹開始，依次把後一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子，用線連接配接起來。

二叉樹轉換為樹、森林

二叉樹轉換為普通樹是剛才的逆過程，步驟也就是反過來做而已。

判斷一棵二叉樹能夠轉換成一棵樹還是森林，标準很簡單，那就是隻要看這棵二叉樹的根結點有沒有右孩子，有的話就是森林，沒有的話就是一棵樹。

樹與森林的周遊

樹的周遊分為兩種方式：一種是先根周遊，另一種是後根周遊。

• 先根周遊：先通路樹的根結點，然後再依次先根周遊根的每棵子樹。
• 後根周遊：先依次周遊每棵子樹，然後再通路根結點。