從 Day 14 開始，我們一路都在處理二元樹：怎麼建立、怎麼走訪、怎麼把空指標拿來當引線。二元樹好處理，是因為每個節點最多只有左、右兩個子節點，用兩個指標就能存下。但 Day 13 介紹的一般樹，一個節點可以有任意多個子節點；好幾棵樹放在一起，還會形成森林。這些結構有沒有辦法也變成二元樹，好讓前面學過的方法都能沿用？

今天就來回答這個問題：先看樹和森林的關係，再學會把森林轉換成二元樹。

從一棵樹到森林

**森林（forest）**是由零棵或多棵互不相連的樹組成的集合，有些書也簡稱為「林」。樹和森林的關係很密切：把一棵樹的根節點刪掉，根底下的每棵子樹都會各自成為一棵獨立的樹，合起來就是一座森林。

左邊是原本的一棵樹，右邊是刪除根節點 A 之後得到的森林：

      A       刪除 A
   /  |  \    ------>     B     C     D
  B   C   D              / \          |
 / \      |             E   F         G
E   F     G
                         樹 1  樹 2  樹 3

A 原本有 B、C、D 三個子節點，刪除 A 之後，B、C、D 各自成為一棵樹的根。C 底下沒有任何節點，但只有一個節點也算一棵樹。因此：

• 刪除根節點後，森林裡樹的數量，等於原本根節點的分支度（子節點個數）。
• 反過來，在森林上方加一個新的根節點，把每棵樹的根都接到它底下，就會變回一棵樹。

林轉二元樹

把森林轉成二元樹後，就能沿用二元樹的節點結構（每個節點只有左、右兩個指標），也能套用前幾天學過的走訪方法。這個轉換其實就是 Day 13 介紹過的左子右兄弟表示法，只是多了一條規則：把森林中各棵樹的根，也當成彼此的兄弟。轉換後，每個節點的兩個指標分別代表：

• 左指標：指向這個節點的第一個子節點。
• 右指標：指向這個節點的下一個兄弟。

遞迴定義

假設森林由 T₁、T₂、…、Tₙ 這 n 棵樹組成，轉換出來的二元樹可以這樣定義：

1. 如果 n = 0，也就是森林是空的，轉換結果就是空的二元樹。
2. 否則：
   • 根節點：第一棵樹 T₁ 的根。
   • 左子樹：T₁ 的根底下的各棵子樹也構成一個森林，把它用同樣的方法轉換。
   • 右子樹：剩下的樹 T₂、…、Tₙ 構成一個森林，把它用同樣的方法轉換。

左子樹處理的是「往下一層」的子節點，右子樹處理的是「同一層」的兄弟，正好對應上面兩個指標的意義。

手算步驟

實際畫圖時，可以照以下三步進行：

1. 連兄弟：把同一個父節點底下的兄弟節點從左到右連起來，各棵樹的根也從左到右連起來。
2. 剪子線：每個節點只保留連到最左邊子節點的那條線，其他連到子節點的線都刪掉。
3. 轉 45 度：把整張圖順時針轉約 45 度，往下的線就成為左子節點，往右的線就成為右子節點。

範例

以前一節的森林為例，左邊是三棵樹組成的森林，右邊是轉換後的二元樹：

      B        C        D                 B
     / \                |                / \
    E   F               G               E   C
                                         \   \
                                          F   D
                                             /
                                            G

下面依照前面的三個手算步驟，一步一步畫出轉換過程。

步驟 1：連兄弟。 三棵樹的根 B、C、D 從左到右連起來；E、F 同樣是 B 的子節點，也連起來。G 沒有兄弟，不用連。

    B ----- C ----- D
   / \              |
  E - F             G

步驟 2：剪子線。 B 有兩條往下的線，只保留連到最左邊子節點 E 的那一條，右邊的線都刪掉，所以 B 到 F 的線刪掉。D 只有一個子節點 G，線保留。

    B ----- C ----- D
   /                |
  E - F             G

步驟 3：轉 45 度。 步驟 2 做完後，每個節點最多只剩一條往下的線和一條往右的線，誰是左子節點、誰是右子節點其實已經決定好了；這一步沒有新增或刪除任何連結，只是把圖重畫成習慣的二元樹樣子。把整張圖順時針轉約 45 度，原本往下的線（B 到 E、D 到 G）變成左子節點；原本橫向的兄弟線（B 到 C、C 到 D、E 到 F）變成右子節點：

        B
       / \
      E   C
       \   \
        F   D
           /
          G

逐一核對每條連結：

這個例子中，B 的右子樹是由第二、三棵樹轉換而來的，因為 B 有兄弟 C。各棵樹的根 B、C、D 用右線串成一條往右下延伸的鏈，每棵樹自己的子節點則掛在各自根的左邊。

反過來說，如果只轉換一棵樹，根節點沒有兄弟，轉出來的二元樹，根一定沒有右子樹。

只有一棵樹也值得轉換，因為一般樹的每個節點，子節點數量不固定。用 C 寫節點結構時，很難決定要準備幾個子節點指標：準備太少不夠用，準備太多又會有大量 NULL 浪費空間。轉成二元樹後，每個節點固定只要兩個指標，不論原本的分支度是多少都能存下，也能直接套用二元樹的走訪方法。

以前一節的樹為例，根 A 有 3 個子節點，本身不是二元樹。轉換後每個節點最多只有兩個子節點，而且 A 沒有右子樹：

    原本的樹                轉換後
        A                    A
     /  |  \                /
    B   C   D              B
   / \      |             / \
  E   F     G            E   C
                          \   \
                           F   D
                              /
                             G

仔細比對會發現，A 的左子樹正好就是前面森林 B、C、D 轉出來的二元樹。這也呼應前一節的觀察：把樹根 A 拿掉，剩下的就是那座森林。

小結

把一棵樹的根節點刪掉，根底下的各棵子樹就形成一座森林；反過來，替森林加上一個共同的根，又會變回一棵樹。一般樹和森林的節點，子節點數量都不固定，不容易直接存進記憶體。轉成二元樹的關鍵，是讓兩個指標換上新的意義：左指標指向第一個子節點，右指標指向下一個兄弟，並把森林中各棵樹的根也當成兄弟。手算時依序連兄弟、剪子線、轉 45 度；其實步驟 2 做完時左右就已經決定，轉 45 度只是畫成習慣的二元樹樣子。轉換之後，每個節點固定只需要兩個指標，可以沿用二元樹的節點結構與走訪方法，但要記得右指標代表的是原本的兄弟關係。

今日重點：

• 刪除一棵樹的根節點，會得到一座森林，樹的數量等於原本根節點的分支度。
• 森林轉二元樹時，左指標指向第一個子節點，右指標指向下一個兄弟。
• 森林中各棵樹的根也互相視為兄弟，所以第二棵以後的樹會掛在第一棵樹根的右子樹。
• 手算步驟是連兄弟、剪子線（每個節點只留最左邊子節點的線）、轉 45 度。
• 只轉換一棵樹時，根沒有兄弟，轉出來的二元樹根一定沒有右子樹。
• 不論原本分支度多大，轉換後每個節點都只需要兩個指標。

下一篇會認識累堆（heap）：一種用完整二元樹表示、能快速取出最大或最小值的結構。