上一篇最後提到：如果我們只看一種走訪結果，通常無法確定一棵二元樹長什麼樣子。那反過來問，如果手上有兩種走訪結果，能不能把原本的樹畫回來？如果節點資料不重複，選用前序加中序，或中序加後序，就能決定唯一的一棵二元樹。

我們先用一個實際例子把樹還原出來；後半段則介紹走訪最經典的應用之一：用二元樹表示算式的二元運算樹。

為什麼兩種走訪就能決定一棵樹

還原二元樹靠的是 Day 15 整理過的兩個特性：

1. 找根：前序（DLR）的第一個一定是根；後序（LRD）的最後一個一定是根。
2. 切左右：中序（LDR）裡，根的左邊全部屬於左子樹，右邊全部屬於右子樹。

前序或後序負責告訴我們「誰是根」，中序負責告訴我們「哪些節點在左、哪些在右」。切出左右子樹後，每一棵子樹同樣有自己的前序和中序，再對子樹重複一樣的步驟，直到子樹是空的為止。這又是 Day 15 看過的遞迴想法。

這個方法有一個前提：節點資料不能重複。如果中序裡有兩個 A，就可能無法判斷根對應哪一個，因而無法保證唯一還原。

實際還原：前序 ABCDEF、中序 BCAEDF

已知一棵二元樹的走訪結果：

前序（DLR）：A B C D E F
中序（LDR）：B C A E D F

下面每一步都用方括號 [ ] 標出這一步找到的根，用 | 標出在中序裡切開的位置。

步驟 1：找出整棵樹的根。 前序第一個是 A，所以 A 是根。在中序裡找到 A，把它左右切開：

前序：[A] B C D E F
中序：B C | [A] | E D F

              A
            /   \
          /       \
       (B C)    (E D F)

左子樹有 B、C 兩個節點，右子樹有 E、D、F 三個節點；括號表示這兩棵子樹還沒還原。

步驟 2：還原左子樹。 左子樹有 2 個節點，所以前序在 A 之後的 2 個，就是左子樹的前序。前序第一個是 B，所以 B 是這棵子樹的根；在中序裡，B 的左邊沒有節點，右邊是 C：

前序：[B] C
中序：[B] | C

              A
            /   \
          /       \
         B      (E D F)
          \
           C

所以 B 沒有左子節點，C 是 B 的右子節點。

步驟 3：還原右子樹。 前序剩下的 D E F 就是右子樹的前序。前序第一個是 D，所以 D 是根；中序裡 E 在 D 的左邊、F 在 D 的右邊：

前序：[D] E F
中序：E | [D] | F

              A
            /   \
          /       \
         B         D
          \       / \
           C     E   F

所以 E 是 D 的左子節點、F 是右子節點。到這裡所有節點都放好了，這就是還原出來的整棵樹。我把三個步驟也整理在同一張圖中：

可以把這棵樹再走訪一次來驗算：前序是 A B C D E F、中序是 B C A E D F，和題目給的一致。它的後序則是 C B E F D A，等一下會用到。

換成中序加後序

中序加後序的做法完全相同，只是「找根」改成看後序的最後一個。用同一棵樹來試：

後序（LRD）：C B E F D A
中序（LDR）：B C A E D F

1. 後序最後一個是 A，所以 A 是根；中序切成左邊 B C、右邊 E D F。
2. 左子樹有 2 個節點，所以後序前 2 個 C B 是左子樹的後序。最後一個 B 是根；中序 B C 裡 C 在 B 的右邊，所以 C 是 B 的右子節點。
3. 後序接下來的 E F D 是右子樹的後序。最後一個 D 是根；中序 E D F 裡 E 在左、F 在右。

得到的樹和前面完全一樣，如果畫出來不一樣的話代表有地方可能畫錯囉。

常見誤解：前序加後序也可以

前序和後序都只能幫忙「找根」，沒有一個能負責「切左右」。Day 15 用過的兩棵樹就是反例：

左邊的樹        右邊的樹
    A               A
   /                 \
  B                   B

兩棵樹的前序都是 A B，後序也都是 B A。一般二元樹允許節點只有一個子節點；只拿前序和後序，就無法判斷這個子節點在左邊還是右邊，因此無法保證唯一還原。對這類沒有額外結構限制的二元樹，可以搭配中序來確定左右位置。

二元運算樹：為什麼要用樹表示算式

平常寫算式時，要靠運算子優先順序（先乘除後加減，同級由左到右）和括號才能知道先算哪裡。我們用這個範例來講解：

A + B / C - (D + E)

它的計算順序是：

1. 除法優先，先算 B / C；括號裡的 D + E 也要先算。
2. 再算 A 加上 B / C 的結果。
3. 最後用前一步的結果減掉 D + E。

如果拿掉括號，寫成 A + B / C - D + E，運算元和運算子的排列順序完全相同，意思卻變成「減掉 D 之後再加上 E」，而不是減掉 D + E。例如代入 A = 2、B = 6、C = 3、D = 1、E = 4，原本的算式是 2 + 2 - 5 = -1，拿掉括號後卻是 2 + 2 - 1 + 4 = 7。

可見這種寫法的計算順序並沒有直接寫在式子上，而是要靠優先順序和括號推出來。我們看算式時會一眼掃過整個式子，自然套用這些規則；但程式通常從左到右逐字讀取，讀到 A + B 時還不能馬上相加，因為後面接著 / C，B 要先和 C 相除；讀到 - 之後又遇到括號，得先算完括號裡的內容。程式必須一邊把前面的內容記住、一邊往後看，還要配對括號，處理起來相當麻煩。

**二元運算樹（binary expression tree）**把「計算的先後」改用樹的上下層來表示：

• 運算子（+、-、*、/）放在內部節點，它的左、右子樹分別是左運算元和右運算元。
• 運算元（數字或變數）放在葉節點。
• 一個運算子要等左右子樹都算出結果，才能計算自己；也就是說，下層的運算一定比它上方的運算先算。

A + B / C - (D + E) 的二元運算樹如下，注意 / 是除法節點，不是連線：

            -
          /   \
        +       +
       / \     / \
      A   /   D   E
         / \
        B   C

對照前面的計算順序：除法 / 在左邊 + 的下面，所以要先算；左邊的 + 要等 B / C 算好，才能把 A 加上去；右邊的 + 就是括號裡的 D + E；根節點 - 在最上層，最後才把左右兩邊的結果相減。樹的結構本身已經記錄了計算順序，不再需要括號，也不必另外記優先順序，這就是使用二元運算樹的理由。

這裡的四則運算都有兩個運算元，剛好對應二元樹的左、右兩個位置，所以二元樹很適合表示這類算式。

三種走訪對應三種算式寫法

對二元運算樹做 Day 15 的三種走訪，會得到三種算式寫法：

中序式就是平常習慣的寫法，但直接走訪會把括號弄丟：得到的 A + B / C - D + E 正是前面說過意思不同的那個算式。所以用中序輸出時，要在每個運算子的子樹外面補上括號，寫成 ((A + (B / C)) - (D + E))。這樣每一層都有括號，最外層也會多一組，雖然比平常手寫的多，但計算順序一定正確。

前序式和後序式則不需要括號，只要照順序讀就能算出唯一的結果。以後序式 A B C / + D E + - 為例，從左往右讀：遇到運算元先記下來，遇到運算子就拿最近記下的兩個值計算，再把結果記回去。先拿出的值是右運算元，後拿出的才是左運算元；所以遇到 / 時，先拿出 C、再拿出 B，計算的是 B / C。「最近記下的先拿出來」正是 Day 10 堆疊的 LIFO 特性，所以後序式很適合用堆疊計算。

而在運算樹上求值，就是一次後序走訪：先算出左子樹的值、再算出右子樹的值，最後才套用目前節點的運算子。

運算樹只要一種走訪就能還原

前半段說過，一般二元樹要「前序加中序」或「中序加後序」才能還原。運算樹比較特別：只要有前序式或後序式其中一個就夠了，因為每個節點的身分很明確：運算子一定有 2 個子節點，運算元一定是葉節點。例如從左往右讀後序式 A B C / + D E + -，遇到運算元就先記下，遇到運算子就把最近記下的兩個組成一棵子樹（較晚記下的是右子樹），讀完就能得到原本那棵樹。

只有不含括號的中序式，無法保證還原出原本的運算樹：A + B / C - D + E 依一般的運算子優先順序與同級由左到右的規則，仍能建立一棵樹，但它表示的算式與原本的 A + B / C - (D + E) 不同。若保留完整括號，就能還原原本的運算樹。另外，這棵樹有兩個 +，資料重複，前半段「前序加中序」的方法也無法直接套用。

小結

只看一種走訪結果通常無法確定樹的形狀。若節點資料不重複，前序加中序或中序加後序就能還原唯一的二元樹：前序的第一個或後序的最後一個負責找出根，中序負責以根為界切出左右子樹，再對每棵子樹重複同樣的步驟。一般二元樹可能有只有一個子節點的節點，因此前序加後序無法保證分辨左右。二元運算樹則是走訪的實際應用：它用樹的上下層記錄計算順序，讓算式不再需要括號；前序、中序、後序走訪分別得到前序式、中序式和後序式，而求值本身就是一次後序走訪。對寫程式來說，由走訪結果還原樹的想法，可以用來檢查程式建出的樹有沒有接錯，也是把樹存成序列、之後再建回來的基礎；運算樹則出現在計算機、試算表公式和編譯器裡，程式要先把算式整理成類似的樹狀結構，才知道該先算哪裡。

今日重點：

• 前序加中序、或中序加後序，可以決定唯一的一棵二元樹；前提是節點資料不重複。
• 前序第一個、後序最後一個都是根；中序中根的左邊是左子樹、右邊是右子樹。
• 還原時先找根、再切左右，對每棵子樹重複同樣步驟，直到子樹為空，這是遞迴的過程。
• 對沒有額外結構限制的一般二元樹，前序加後序無法保證唯一還原，因為只有一個子節點時無法分辨它在左或在右。
• 二元運算樹的運算子在內部節點、運算元在葉節點；運算子要等下方的子樹都算完才計算，因此不需要括號。
• 對運算樹做前序、中序、後序走訪，分別得到前序式、中序式、後序式；中序式要補括號才能保留原本的計算順序。
• 在運算樹上求值就是後序走訪：先算左右子樹，再套用目前節點的運算子。
• 在本篇只有二元運算子的範例中，運算子都有 2 個子節點、運算元都是葉節點，所以前序式或後序式其中一個就能還原運算樹；中序式須保留括號才能還原原本那棵樹。

下一篇會認識引線二元樹：二元樹裡有許多 left、right 指標是 NULL，看看如何利用這些空著的指標，讓走訪不必依靠遞迴也能找到下一個節點。