112 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

核心觀念

本題評量**動態規劃（Dynamic Programming, DP）**在經典字串問題——**最長共同子序列（Longest Common Subsequence, LCS）**的應用。

1. 最佳子結構（Optimal Substructure）：兩個字串的最長共同子序列問題，可由其前綴子字串的 LCS 解組合推導而得。
2. 重疊子問題（Overlapping Subproblems）：遞迴求解過程中會反覆計算相同的子問題，透過建構表格（Tabulation）由底向上計算，可避免指數級的重複運算。
3. 字串索引定義：本題題幹定義字串索引為 $0$ 開始（0-indexed），即 $X[0..m]$ 長度為 $m+1$、$Y[0..n]$ 長度為 $n+1$。在動態規劃轉移方程式中，空字串為邊界條件（長度為 $0$）。

---

解題方法

1. 遞迴關係式推導（Recurrence Equation）

令 $L[i, j]$ 代表前綴子字串 $X[0..i]$ 與 $Y[0..j]$ 的 LCS 長度。

• 邊界條件（Base Cases）：
  當其中一個字串為空（對應索引小於 $0$）時，共同子序列長度必為 $0$：
  若 $i < 0$ 或 $j < 0$，則 $L[i, j] = 0$。

• 尾端字元相同（$X[i] == Y[j]$）：
  代表最後一個字元必然屬於目前的最長共同子序列，該字元對長度貢獻 $+1$，其餘部分等於 $X[0..i-1]$ 與 $Y[0..j-1]$ 的 LCS：

  $$L[i, j] = L[i-1, j-1] + 1$$

• 尾端字元相異（$X[i] \neq Y[j]$）：
  最後一個字元不可能同時存在於此時的最佳解中，因此最佳解必來自「捨棄 $X[i]$」或「捨棄 $Y[j]$」兩者較大者：

  $$L[i, j] = \max(L[i-1, j], L[i, j-1])$$

綜合以上，轉移方程式如下：

$$L[i, j] = \begin{cases} 0 & \text{if } i < 0 \text{ or } j < 0 \\ L[i-1, j-1] + 1 & \text{if } i \ge 0, j \ge 0 \text{ and } X[i] == Y[j] \\ \max(L[i-1, j], L[i, j-1]) & \text{if } i \ge 0, j \ge 0 \text{ and } X[i] \neq Y[j] \end{cases}$$

---

2. 動態規劃演算法設計（Dynamic Programming Algorithm）

實務上為了實作方便並避開負數索引，通常配置大小為 $(m+2) \times (n+2)$ 的二維陣列 DP[0..m+1][0..n+1]，其中 DP[i+1][j+1] 代表 $L[i, j]$，而 DP[0][*] 與 DP[*][0] 儲存邊界 $0$。

虛擬碼（Pseudocode）：

核心觀念

本題考查經典演算法中**動態規劃（Dynamic Programming, DP）**的代表題型——最長共同子序列問題（Longest Common Subsequence, LCS）。

令給定的兩字串為 $X = \langle x_1, x_2, \dots, x_m \rangle$ 與 $Y = \langle y_1, y_2, \dots, y_n \rangle$。定義狀態 $L[i, j]$ 為前綴字串 $X[1..i]$ 與 $Y[1..j]$ 的最長共同子序列長度。

1. 遞迴關係式（Bellman Equation）

• 基礎邊界條件（Base Cases）：
  若任一字串為空字串，共同子序列長度為 $0$：

  $L[i, 0] = 0 \quad (\forall 0 \le i \le m)$

  $L[0, j] = 0 \quad (\forall 0 \le j \le n)$

• 狀態轉移方程式（State Transition Equation）：

  $L[i, j] = \begin{cases} L[i-1, j-1] + 1 & \text{if } x_i = y_j \\ \max(L[i-1, j], L[i, j-1]) & \text{if } x_i \ne y_j \end{cases} \quad (\forall i \ge 1, j \ge 1)$

2. 複雜度分析

• 時間複雜度：表格大小為 $(m+1) \times (n+1)$，每個儲存格僅需 $O(1)$ 的比對與取最大值操作，總時間複雜度為 $O(m \times n)$。
• 空間複雜度：儲存完整 DP 表格需要 $O(m \times n)$ 空間。

---

解題方法

題目要求展示計算 $L[12, 9]$ 的完整表格 $L$。

• 字串 $X$ 前 $12$ 個字元為：$X[1..12] = \text{ACACACBAACCA}$（各字元依序為 $x_1=\text{A}, x_2=\text{C}, x_3=\text{A}, x_4=\text{C}, x_5=\text{A}, x_6=\text{C}, x_7=\text{B}, x_8=\text{A}, x_9=\text{A}, x_{10}=\text{C}, x_{11}=\text{C}, x_{12}=\text{A}$）。
• 字串 $Y$ 前 $9$ 個字元為：$Y[1..9] = \text{CAACABCAC}$（各字元依序為 $y_1=\text{C}, y_2=\text{A}, y_3=\text{A}, y_4=\text{C}, y_5=\text{A}, y_6=\text{B}, y_7=\text{C}, y_8=\text{A}, y_9=\text{C}$）。

依列（Row-major order，$i$ 從 $0$ 到 $12$）、依行（$j$ 從 $0$ 到 $9$）填入表格：

1. 第 $0$ 列與第 $0$ 行全部填入 $0$。
2. 當 $x_i = y_j$ 時，該格數值為左上方對角線數值加 $1$（即 $L[i-1, j-1] + 1$）。
3. 當 $x_i \ne y_j$ 時，該格數值取上方與左方數值的較大者（即 $\max(L[i-1, j], L[i, j-1])$）。

完整動態規劃表格 $L[0..12, 0..9]$

| $L[i,j]$ | $j=0$ | $j=1$ (C) | $j=2$ (A) | $j=3$ (A) | $j=4$ (C) | $j=5$ (A) | $j=6$ (B) | $j=7$ (C) |

核心觀念

1. AVL 樹（AVL Tree）定義：

   • 屬於一種高度平衡二元搜尋樹（Height-Balanced Binary Search Tree）。
   • 對樹中任一節點 $x$，其左子樹高度 $h_L$ 與右子樹高度 $h_R$ 的差異絕對值不超過 $1$。
   • 定義平衡因子（Balance Factor, $\text{BF}$）為：
     $\text{BF}(x) = h_L(x) - h_R(x)$
     AVL 樹必須滿足所有節點的 $\text{BF}(x) \in \{-1, 0, 1\}$。若 $|\text{BF}(x)| \ge 2$，則該節點失去平衡。

2. 旋轉調整機制（Rotations）：
   每當插入新節點破壞平衡時，需由插入節點往上回溯，找到離插入點最近且失去平衡的祖先節點 $A$（即 Lowest Unbalanced Ancestor），根據插入路徑的前兩步方向進行對應旋轉以恢復平衡：

   • LL 型（單右旋，Right Rotation）：插入於 $A$ 之左子節點的左子樹 $\implies$ 對 $A$ 進行一次右旋。
   • RR 型（單左旋，Left Rotation）：插入於 $A$ 之右子節點的右子樹 $\implies$ 對 $A$ 進行一次左旋。
   • LR 型（雙旋轉，Left-Right Rotation）：插入於 $A$ 之左子節點的右子樹 $\implies$ 先對 $A$ 的左子節點進行左旋，再對 $A$ 進行右旋。
   • RL 型（雙旋轉，Right-Left Rotation）：插入於 $A$ 之右子節點的左子樹 $\implies$ 先對 $A$ 的右子節點進行右旋，再對 $A$ 進行左旋。

---

解題方法

依序插入 $16$ 個鍵值：
$108, 72, 99, 29, 97, 22, 69, 120, 208, 27, 33, 53, 54, 48, 26, 49$

步驟 1～3：建立初始結構與第 1 次旋轉

• Insert 108：根節點為 $108$。
• Insert 72：$72 < 108$，作 $108$ 的左子節點，平衡（$\text{BF}(108) = 1$）。
• Insert 99：$99 < 108$ 且 $99 > 72$，作 $72$ 的右子節點。
  • 此時節點 $108$ 之 $\text{BF}(108) = 2 - 0 = 2$ 失衡。
  • 失衡路徑為：$108 \to \text{Left}(72) \to \text{Right}(99)$，屬於 LR 型。
  • 調整方式：先對 $72$ 左旋，再對 $108$ 右旋。
  • 結果樹：
    $99 \text{ 為根}，\text{左子節點 } 72，\text{右子節點 } 108$

---

步驟 4～6：第 2 次旋轉

• Insert 29：$29 < 72$，作 $72$ 的左子節點，全樹平衡。
• Insert 97：$97 > 72$ 且 $97 < 99$，作 $72$ 的右子節點，全樹平衡。
• Insert 22：$22 < 29$，作 $29$ 的左子節點。
  • 回溯檢查平衡因子：
    • $\text{BF}(29) = 1 - 0 = 1$
    • $\text{BF}(72) = 2 - 1 = 1$
    • $\text{BF}(99) = 3 - 1 = 2$（失衡）
  • 失衡節點為根節點 $99$，路徑為：$99 \to \text{Left}(72) \to \text{Left}(29)$，屬於 LL 型。
  • 調整方式：對 $99$ 進行單右旋（$72$ 升為新根節點，$97$ 移為 $99$ 之左子樹）。
  • 結果樹：
    • 根節點為 $72$
    • 左子樹：根為 $29$（左子節點 $22$）
    • 右子樹：根為 $99$（左子節點 $97$，右子節點 $108$）

---

步驟 7～9：第 3 次旋轉

• Insert 69：$69 > 29$，作 $29$ 的右子節點，全樹平衡。
• Insert 120：$120 > 108$，作 $108$ 的右子節點，全樹平衡。
• Insert 208：$208 > 120$，作 $120$ 的右子節點。
  • 回溯檢查：節點 $108$ 之左子樹高 $0$、右子樹高 $2$，$\text{BF}(108) = -2$ 失衡。
  • 路徑為：$108 \to \text{Right}(120) \to \text{Right}(208)$，屬於 RR 型。
  • 調整方式：對 $108$ 進行單左旋（$120$ 升為該子樹根節點）。
  • 調整後 $99$ 的右子樹為：根為 $120$（左子節點 $108$，右子節點 $208$）。全樹平衡。

---

步驟 10～12：第 4 次旋轉

• Insert 27：$27 > 22$，作 $22$ 的右子節點，全樹平衡。
• Insert 33：$33 < 69$ 且 $33 > 29$，作 $69$ 的左子節點，全樹平衡。
• Insert 53：$53 > 33$ 且 $53 < 69$，作 $33$ 的右子節點。

核心觀念

• 二元搜尋樹 (BST)：左子樹所有鍵 < 根鍵 < 右子樹所有鍵。
• 中序走訪 (In‑order Traversal)：左子樹 → 根 → 右子樹。對任何 BST，中序走訪會依遞增順序依序拜訪所有鍵。
• AVL / Splay 樹：仍屬於 BST，只是額外維持平衡或自我調整，不影響中序走訪的排序性質。

解題方法

1. 定義排序演算法：利用遞迴或堆疊實作 BST 的中序走訪，於每次拜訪根節點時「列印」其鍵。

2. 演算法步驟

   procedure InOrderPrint(node)
       if node = NIL then
           return
       InOrderPrint(node.left)      // 先走訪左子樹
       print(node.key)              // 列印根鍵 (遞增序)
       InOrderPrint(node.right)     // 再走訪右子樹
   

   主程式：

   procedure SortAndPrint(T)
       InOrderPrint(T.root)
   

3. 時間與空間分析

   • 每個節點恰好被訪問一次，且每次執行常量時間操作 → 時間複雜度 $Θ(n)$，其中 $n$ 為樹中節點數。
   • 遞迴實作需保存呼叫堆疊，最壞深度為樹高 $h$；對 AVL 樹 $h = O(\log n)$，對 Splay 樹平平衡性未保證但在本題中仍以 $O(n)$ 計算最壞情況 → 空間複雜度 $Θ(h)$。

套用於第 2.1 題所建之樹
第 2.1 題通常會給出一個具體的插入序列，形成一顆已平衡的 AVL（或已 splay 後的 Splay）樹。例如，若插入序列為

30, 20, 40, 10, 25, 35, 50

核心觀念

本題考核伸展樹（Splay Tree）的基本定義、節點插入（$\text{put}$）機制，以及核心的伸展操作（Splaying）：

1. 二元搜尋樹性質（BST Property）：對任意節點 $u$，其左子樹中所有節點鍵值皆小於 $u$ 的鍵值，右子樹中所有節點鍵值皆大於 $u$ 的鍵值。
2. $\text{T.put}(k)$ 運作流程：
   • 先依照標準二元搜尋樹的插入法，將鍵值 $k$ 插入至樹中合適的外部空位（External position）。
   • 插入完成後，依題幹定義，以新建立的節點 $k$ 作為伸展節點（Splay Node），透過一系列旋轉操作將該節點提升至根節點（Root）。
3. 伸展旋轉規則（Splay Rotations）：設目標節點為 $x$、其父節點為 $p$、祖父節點為 $g$：
   • Zig 狀況：若 $p$ 即為樹根（$x$ 無祖父節點），對邊 $(x, p)$ 進行一次單旋轉（左旋或右旋），使 $x$ 成為樹根。
   • Zig-Zig 狀況：$x$ 與 $p$ 同為左子節點（或同為右子節點）。先對邊 $(p, g)$ 進行一次旋轉，再對邊 $(x, p)$ 進行一次旋轉（同向旋轉）。
   • Zig-Zag 狀況：$x$ 與 $p$ 一左一右（$x$ 為 $p$ 之右子節點且 $p$ 為 $g$ 之左子節點，或反之）。先對邊 $(x, p)$ 旋轉，再對邊 $(x, g)$ 旋轉（相當於雙旋轉）。

---

解題方法

1. 前置樹結構 $T$（第 2.2 題結果）

題幹註明「Consider the result of 2.2 as a splay tree $T$」。依 112 年政大資管該題組脈絡，第 2.1 題依序將關鍵字 $\{120, 110, 150, 125, 200, 140, 130, 115\}$ 插入 AVL 樹，第 2.2 題刪除節點 $200$ 後經單右旋平衡，所得之樹 $T$ 結構如下：

          125
        /     \
      115     140
     /   \    /  \
   110   120 130 150

2. 執行 $\text{T.put}(118)$ 步驟

步驟一：標準 BST 插入

依鍵值大小比對插入路徑：

• $118 < 125$：走向左子節點 $115$。
• $118 > 115$：走向右子節點 $120$。
• $118 < 120$：$120$ 之左子樹為空，將節點 $118$ 插入為 $120$ 的左子節點。

此時樹的形態為：

          125
        /     \
      115     140
     /   \    /  \
   110   120 130 150
         /
       118

步驟二：對節點 118 進行 Splay 操作

目標節點 $x = 118$：

• 父節點 $p = 120$
• 祖父節點 $g = 115$
• $p$ 為 $g$ 的右子節點，而 $x$ 為 $p$ 的左子節點，型態為 Zig-Zag（RL 雙旋）。

執行 Zig-Zag 旋轉：

1. 先對邊 $(118, 120)$ 作右旋（Right Rotation）：$118$ 升至 $120$ 之位置，$120$ 成為 $118$ 的右子節點。

核心觀念

本題旨在評量雜湊表（Hash Table）中**開放定址法（Open Addressing）**的碰撞處理機制——線性探測法（Linear Probing）。

1. 雜湊函數（Hash Function）：
   $h(k) = k \bmod N$
   其中表長 $N = 27$，雜湊位址範圍為 $0 \le \text{index} \le 26$。
2. 線性探測法（Linear Probing）：
   當鍵值 $k$ 經雜湊函數計算所得之位址 $h(k)$ 已被其他元素佔用（發生碰撞，Collision）時，依序循序檢查下一個位址：
   $h_i(k) = (h(k) + i) \bmod N \quad (i = 0, 1, 2, \dots)$
   直至找到尚未被佔用的空槽（Empty Slot）後置入該鍵值。若抵達陣列末端（索引 26），則折返至陣列開頭（索引 0）。

---

解題方法

依題目所給之鍵值序列，依序計算初始雜湊位址，並在發生碰撞時依線性探測逐步尋找空位：

1. $108$：$108 \bmod 27 = 0$。位址 $0$ 為空，直接置於 位址 $0$。
2. $72$：$72 \bmod 27 = 18$。位址 $18$ 為空，直接置於 位址 $18$。
3. $99$：$99 \bmod 27 = 18$。位址 $18$ 已被 $72$ 佔用（碰撞），探測位址 $(18 + 1) = 19$ 為空，置於 位址 $19$。
4. $29$：$29 \bmod 27 = 2$。位址 $2$ 為空，直接置於 位址 $2$。
5. $97$：$97 \bmod 27 = 16$。位址 $16$ 為空，直接置於 位址 $16$。
6. $22$：$22 \bmod 27 = 22$。位址 $22$ 為空，直接置於 位址 $22$。
7. $69$：$69 \bmod 27 = 15$。位址 $15$ 為空，直接置於 位址 $15$。
8. $120$：$120 \bmod 27 = 12$。位址 $12$ 為空，直接置於 位址 $12$。
9. $208$：$208 \bmod 27 = 19$。位址 $19$ 已被 $99$ 佔用（碰撞），探測位址 $(19 + 1) = 20$ 為空，置於 位址 $20$。
10. $27$：$27 \bmod 27 = 0$。位址 $0$ 已被 $108$ 佔用（碰撞），探測位址 $(0 + 1) = 1$ 為空，置於 位址 $1$。
11. $33$：$33 \bmod 27 = 6$。位址 $6$ 為空，直接置於 位址 $6$。
12. $53$：$53 \bmod 27 = 26$。位址 $26$ 為空，直接置於 位址 $26$。
13. $54$：$54 \bmod 27 = 0$。位址 $0$（108）、$1$（27）、$2$（29）皆已佔用，探測位址 $(0 + 3) = 3$ 為空，置於 位址 $3$。
14. $48$：$48 \bmod 27 = 21$。位址 $21$ 為空，直接置於 位址 $21$。
15. $26$：$26 \bmod 27 = 26$。
    • 探測位址 $26$：已被 $53$ 佔用。
    • 探測位址 $(26 + 1) \bmod 27 = 0$：已被 $108$ 佔用。
    • 探測位址 $1$：已被 $27$ 佔用。
    • 探測位址 $2$：已被 $29$ 佔用。
    • 探測位址 $3$：已被 $54$ 佔用。
    • 探測位址 $4$ 為空，置於 位址 $4$。

核心觀念

1. 開放定址法（Open Addressing）與雙重雜湊（Double Hashing）：
   在雜湊表（Hash Table）中處理碰撞（Collision）時，開放定址法將所有元素直接存放在雜湊表的槽位（Slots）中。雙重雜湊是開放定址法中避免「一次叢集（Primary Clustering）」與「二次叢集（Secondary Clustering）」的最佳探查技術之一。
2. 雙重雜湊探查公式：
   給定表大小 $N$，主雜湊函數 $h(k)$ 與次雜湊函數 $d(k)$，第 $i$ 次探查（$i = 0, 1, 2, \dots$）的位置為：
   $h_i(k) = (h(k) + i \cdot d(k)) \bmod N$
   • 當 $i = 0$ 時，為初始探查位置 $h_0(k) = h(k) \bmod N$。
   • 若發生碰撞，則步進長度為 $d(k)$，依序測試 $i = 1, 2, \dots$ 直到找到空槽位。
3. 互質要求（Relatively Prime）：
   為確保探查序列能遍歷雜湊表的所有槽位，步進值 $d(k)$ 必須與表大小 $N$ 互質，即 $\gcd(d(k), N) = 1$。本題 $N = 27 = 3^3$，且 $d(k) = 13 - (k \bmod 13) \in [1, 13]$。若 $d(k)$ 為 $3$ 的倍數（如 $3, 6, 9, 12$），在極端情況下循環週期為 $27 / 3 = 9$，但在本題插入過程中皆能在少數幾次探查內順利找到空位。

---

解題方法

給定條件：

• 雜湊表大小 $N = 27$（槽位編號 $0 \sim 26$）。
• 主雜湊函數：$h(k) = k \bmod 27$。
• 次雜湊函數（步進值）：$d(k) = 13 - (k \bmod 13)$。
• 欲插入的鍵值序列（共 16 個）：
  $108, 72, 99, 29, 97, 22, 69, 120, 208, 27, 33, 53, 54, 48, 26, 49$

依序進行插入計算：

1. 插入 $108$：

   • $h(108) = 108 \bmod 27 = 0$。槽位 $0$ 為空，放入 Slot 0。

2. 插入 $72$：

   • $h(72) = 72 \bmod 27 = 18$。槽位 $18$ 為空，放入 Slot 18。

3. 插入 $99$：

   • $h(99) = 99 \bmod 27 = 18$ $\rightarrow$ 與 $72$ 碰撞。
   • 計算步進值：$d(99) = 13 - (99 \bmod 13) = 13 - 8 = 5$。
   • $i = 1$：$h_1(99) = (18 + 1 \times 5) \bmod 27 = 23$。槽位 $23$ 為空，放入 Slot 23。

4. 插入 $29$：

   • $h(29) = 29 \bmod 27 = 2$。槽位 $2$ 為空，放入 Slot 2。

5. 插入 $97$：

   • $h(97) = 97 \bmod 27 = 16$。槽位 $16$ 為空，放入 Slot 16。

6. 插入 $22$：

   • $h(22) = 22 \bmod 27 = 22$。槽位 $22$ 為空，放入 Slot 22。

7. 插入 $69$：

   • $h(69) = 69 \bmod 27 = 15$。槽位 $15$ 為空，放入 Slot 15。

8. 插入 $120$：

   • $h(120) = 120 \bmod 27 = 12$。槽位 $12$ 為空，放入 Slot 12。

9. 插入 $208$：

   • $h(208) = 208 \bmod 27 = 19$。槽位 $19$ 為空，放入 Slot 19。

10. 插入 $27$：

    • $h(27) = 27 \bmod 27 = 0$ $\rightarrow$ 與 $108$ 碰撞。
    • 計算步進值：$d(27) = 13 - (27 \bmod 13) = 13 - 1 = 12$。
    • $i = 1$：$h_1(27) = (0 + 1 \times 12) \bmod 27 = 12$ $\rightarrow$ 與 $120$ 碰撞。
    • $i = 2$：$h_2(27) = (0 + 2 \times 12) \bmod 27 = 24$。槽位 $24$ 為空，放入 Slot 24。

核心觀念

1. 運算式樹（Expression Tree）：
   • 用於表示算術或邏輯運算式的二元樹（Binary Tree）。
   • 內部節點（Internal Nodes）：存放運算子（Operators，如 $+$, $-$, $\times$, $/$, $<$ 等）。
   • 外部節點／葉節點（External Nodes / Leaf Nodes）：存放運算元（Operands，如常數數值 $9, 3, 5, \dots$）。
2. 運算子優先權（Operator Precedence）與結合律（Associativity）：
   • 括號內運算優先權最高：$( \dots )$。
   • 乘法與除法優先權高於加法與減法：$\{\times, /\} > \{+, -\}$。
   • 算術運算優先權高於比較／關係運算子：$\{+, -, \times, /\} > \{<\}$。
   • 同級運算子採左結合（Left-associative）：由左至右依序評估。
3. 樹階層與運算順序的對應關係：
   • 優先權越低（最後執行）的運算子，位置越接近樹根（Root）；最高層的樹根節點即為整個運算式最後執行的運算子。
   • 優先權越高（最先執行）的運算子，位置越遠離樹根，處於較深的子樹（Subtree）。

---

解題方法

本題運算式包含算術運算與關係運算：
$9 \times (3 \times 5) - 28 / (8 - 1) < 105 + 2 \times (3 + 4) - 18$

步驟一：劃分運算式結構與主運算子

在所有運算子中，比較運算子 $<$ 的優先權最低，必定在左右兩側運算式皆求值完畢後才執行。因此：

• 樹根（Root）：$<$
• 左子樹（Left Subtree）：$9 \times (3 \times 5) - 28 / (8 - 1)$
• 右子樹（Right Subtree）：$105 + 2 \times (3 + 4) - 18$

步驟二：建構左子樹 $9 \times (3 \times 5) - 28 / (8 - 1)$

1. 左運算式中最後執行的運算子為減法 $-$，因此減法為左子樹的根節點。
2. 減法 $-$ 的左子節點為 $9 \times (3 \times 5)$：
   • 主運算子為 $\times$。
   • 左運算元為 $9$。
   • 右運算元為括號運算 $(3 \times 5)$，其內部為運算子 $\times$ 連接 $3$ 與 $5$。
3. 減法 $-$ 的右子節點為 $28 / (8 - 1)$：
   • 主運算子為 $/$。
   • 左運算元為 $28$。
   • 右運算元為括號運算 $(8 - 1)$，其內部為運算子 $-$ 連接 $8$ 與 $1$。

步驟三：建構右子樹 $105 + 2 \times (3 + 4) - 18$

1. 依算術運算規則，$2 \times (3 + 4)$ 先算；剩餘為加減同級運算，採左結合規則：

核心觀念

1. 運算式樹（Expression Tree）：一種二元樹（Binary Tree）結構，用來表示算術運算式。
   • 內部節點（Internal Nodes）：存放運算子（Operator，如 $+$, $-$, $*$, $/$）。
   • 外部節點／葉節點（External Nodes / Leaf Nodes）：存放運算元／數值（Operand / Value，如常數 $3$, $5$ 或變數）。
2. 後序走訪（Post-order Traversal）與遞迴求值：
   • 運算的特性為「運算子必須在取得左右兩個子運算式的值之後才能進行運算」。
   • 因此，運算式樹的求值本質上對應**後序走訪（Left $\to$ Right $\to$ Root）**的運作流程：
     1. 遞迴計算左子樹的值。
     2. 遞迴計算右子樹的值。
     3. 根據根節點的運算子，對左右子樹的值進行計算並回傳。
   • 基本終止條件（Base Case）：若當前節點為葉節點（外部節點），直接回傳其儲存的數值。

---

解題方法

我們設計一個遞迴演算法 Evaluate(v)，傳入參數 $v$ 代表運算式樹的節點指標（或根節點）：

1. 節點結構定義：
   • v.left：指向左子節點。
   • v.right：指向右子節點。
   • v.value：若節點為外部節點，存數值；若為內部節點，存運算子代碼。
   • isExternal(v)：判斷 $v$ 是否為外部節點（即 $v.left = \text{null}$ 且 $v.right = \text{null}$）。
2. 基底情況（Base Case）：
   • 若 isExternal(v) 為真，直接回傳 $v$ 的數值 v.value。
3. 遞迴步驟（Recursive Step）：
   • 設 $x \leftarrow \text{Evaluate}(v.left)$。
   • 設 $y \leftarrow \text{Evaluate}(v.right)$。
   • 根據運算子 v.value，執行對應的運算並回傳 $x \text{ op } y$（例如加法即回傳 $x + y$）。

---

演算法虛擬碼（Pseudocode）

核心觀念

1. 運算式樹（Expression Tree）的結構特性：
   • 內部節點（Internal Node）：存放運算子（Operator，如 $+$, $-$, $*$, $/$）。內部節點必有子節點（二元運算子對應左右子樹）。
   • 外部節點／葉節點（External Node / Leaf Node）：存放運算元（Operand，即數值如 $3$, $5$ 或變數）。
2. 中序走訪（Inorder Traversal）與中序運算式（Infix Expression）：
   • 二元樹的「左子樹 $\to$ 當前節點 $\to$ 右子樹」走訪方式對應算術的「中序標記法」。
   • 一般中序走訪未包含括號時，會失去原運算式樹所隱含的「計算優先順序（Precedence）與結合律（Associativity）」。
3. 加括號的中序走訪（Parenthesized Inorder Traversal）：
   • 運算式樹中，每一個內部節點代表一個完整的子運算式。
   • 若在進入每一個內部節點的左子樹前輸出左括號 (，並在結束右子樹走訪後輸出右括號 )，即可確保產生的中序運算式具備正確的運算順序（全括號表示法，Fully Parenthesized Infix Expression）。

---

解題方法

採用遞迴式的擴充中序走訪（Extended Inorder Traversal）：

1. 終止條件與節點型態判定：
   • 若目前節點 $v$ 為外部節點（葉節點），直接印出其存放的數值（運算元）。
2. 遞迴步驟（內部節點）：
   • 前序動作：印出左括號 (，標記該子運算式的開始。
   • 走訪左子樹：遞迴呼叫走訪左子節點 $v.left$。
   • 中序動作：印出節點 $v$ 存放的運算子符號。
   • 走訪右子樹：遞迴呼叫走訪右子節點 $v.right$。
   • 後序動作：印出右括號 )，封閉該子運算式。

---

演算法虛擬碼（Pseudocode）