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

核心觀念

本題考查**二元樹走訪（Binary Tree Traversal）中的前序走訪（Pre-order Traversal）**之遞迴定義與追蹤應用。

二元樹的前序走訪核心定義為「根節點 $\rightarrow$ 左子樹 $\rightarrow$ 右子樹」（$V \rightarrow L \rightarrow R$）：

1. 拜訪根節點（Visit Root）：輸出當前節點儲存的字串資料。
2. 走訪左子樹（Traverse Left Subtree）：遞迴呼叫前序走訪函式處理左子節點。
3. 走訪右子樹（Traverse Right Subtree）：遞迴呼叫前序走訪函式處理右子節點。

遞迴終止條件（Base Case）為：當節點為空（null）時直接返回。

---

解題方法

1. 遞迴前序走訪演算法（Java 實作）

定義二元樹節點結構 TreeNode 與靜態遞迴方法 preOrderTraversal：

// 二元樹節點定義
class TreeNode {
    String data;
    TreeNode left;
    TreeNode right;

    TreeNode(String data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTreeTraversal {
    // 遞迴前序走訪演算法
    public static void preOrderTraversal(TreeNode node) {
        // Base Case：空節點直接返回
        if (node == null) {
            return;
        }
        
        // 1. 拜訪並印出當前節點儲存的字串
        System.out.print(node.data + " ");
        
        // 2. 遞迴走訪左子樹
        preOrderTraversal(node.left);
        
        // 3. 遞迴走訪右子樹
        preOrderTraversal(node.right);
    }
}

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 為樹中節點總數（本題 $n = 9$）。每個節點均被存取常數次。
• 空間複雜度：$O(h)$，其中 $h$ 為二元樹的高度（本題 $h = 4$）。空間消耗來自系統執行遞迴時呼叫堆疊（Call Stack）的深度。在最差情況（單斜樹）為 $O(n)$，最佳情況（完全平衡樹）為 $O(\log n)$。

---

2. 套用於 Figure 1 之推導步驟

依據原卷 Figure 1，二元樹的階層與父子結構如下：

• 根節點：Computers"R"Us
  • 左子節點：Sales
    • Sales 的左子節點：US（葉節點）

1. 前序走訪（Pre-order Traversal）順序

依據前序走訪（根 $\rightarrow$ 左 $\rightarrow$ 右），Q1 走訪 Figure 1 得到的字串插入順序為：

1. Computers"R"Us (長度 14)
2. Sales (長度 5)
3. US (長度 2)
4. International (長度 13)
5. Asia (長度 4)
6. Canada (長度 6)
7. Manufacturing (長度 13)
8. Laptops (長度 7)
9. Desktops (長度 8)

---

2. Min Heap 優先權排序規則

• 規則 (1)：字串長度越短，優先權越高（越小，越靠近根節點）。
• 規則 (2)：若字串長度相同，依 $Ord$ 編碼由左至右進行字典順序比較（大小關係為 $A < B < \dots < Z < a < b < \dots < z$）。

長度相同的字串比較：

• International (長度 13) 與 Manufacturing (長度 13)；第一個字元 $Ord(\text{'I'}) = 9 < Ord(\text{'M'}) = 13$，因此優先權為：International > Manufacturing。

字串優先權由高至低（小至大）排序為：

$$\text{US} < \text{Asia} < \text{Sales} < \text{Canada} < \text{Laptops} < \text{Desktops} < \text{International} < \text{Manufacturing} < \text{Computers"R"Us}$$

---

3. 逐一插入與堆積調整步驟

以一維陣列 $A[1..9]$ 表示二元堆積（索引 $i$ 的左子節點為 $2i$，右子節點為 $2i+1$）：

1. 插入 Computers"R"Us：
   • $A = [\text{Computers"R"Us}]$
2. 插入 Sales：
   • 插入於 $A[2]$，與 $A[1]$ 比較，長度 $5 < 14$，向上調整（Up-heap）。
   • $A = [\text{Sales}, \text{Computers"R"Us}]$
3. 插入 US：
   • 插入於 $A[3]$，與 $A[1]$ 比較，長度 $2 < 5$，向上調整。
   • $A = [\text{US}, \text{Computers"R"Us}, \text{Sales}]$
4. 插入 International：
   • 插入於 $A[4]$，與父節點 $A[2]$ 比較，長度 $13 < 14$，向上調整。
   • $A = [\text{US}, \text{International}, \text{Sales}, \text{Computers"R"Us}]$
5. 插入 Asia：

核心觀念

本題考查二元樹的「中序走訪」（in-order traversal）。其固定順序為：

$$\text{左子樹} \rightarrow \text{根節點} \rightarrow \text{右子樹}$$

每個節點儲存一個字串，因此走訪時依上述順序依序印出節點中的字串。

解題方法

遞迴演算法如下：

InOrder(node):
    if node ≠ NULL:
        InOrder(node.left)
        print(node.string)
        InOrder(node.right)

若以空樹作為遞迴終止條件，則：

1. 先走訪目前節點的左子樹；
2. 再印出目前節點儲存的字串；
3. 最後走訪目前節點的右子樹。

因此，套用至 Figure 1 時，必須從最左側節點開始，依「左、根、右」順序逐一列出字串。

一、 Q3 中序走訪（In-order Traversal）輸出序列

依左子樹 $\rightarrow$ 根節點 $\rightarrow$ 右子樹之順序走訪 Figure 1，其輸出序列為：
$\text{US, Sales, Asia, International, Canada, Computers"R"Us, Laptops, Manufacturing, Desktops}$

---

二、 鍵值排序規則與屬性長度

AVL Tree 的排序規則與 Q2 相同：

1. 長度優先：字串長度較短者，其鍵值較小（排在左側）。
2. 長度相同時以字元編碼（Ord）字典序比較：從左至右比較，首個不同字元之 $\text{Ord}$ 值較小者，其鍵值較小。
   • 其中 $\text{Ord("A")}=1 \dots \text{Ord("Z")}=26$，$\text{Ord("a")}=27 \dots \text{Ord("z")}=52$，$\text{Ord("\"")}=0$。

各字串鍵值之長度與排序基準如下：

• $\text{US}$ (長度 2)
• $\text{Asia}$ (長度 4)
• $\text{Sales}$ (長度 5)
• $\text{Canada}$ (長度 6)
• $\text{Laptops}$ (長度 7)
• $\text{Desktops}$ (長度 8)
• $\text{International}$ (長度 13) 與 $\text{Manufacturing}$ (長度 13)：首字 $\text{Ord("I")} = 9 < \text{Ord("M")} = 13$，故 $\text{International} < \text{Manufacturing}$。
• $\text{Computers"R"Us}$ (長度 14)

---

三、 AVL Tree 逐一插入與旋轉步驟

1. 插入 US

US

2. 插入 Sales

因 $\text{US} < \text{Sales}$，插入右子樹：

US
  \
  Sales

3. 插入 Asia

因 $\text{US} < \text{Asia} < \text{Sales}$，插入為 $\text{Sales}$ 的左子樹：

  US (BF = -2)
    \
    Sales (BF = 1)
    /
  Asia (BF = 0)

• 旋轉：根節點 $\text{US}$ 失衡（$\text{BF} = -2$），其插入路徑為右偏後左偏（RL），在 $\text{US}$ 處執行 RL 雙旋轉：
  1. 對 $\text{Sales}$ 進行右旋轉。
  2. 對 $\text{US}$ 進行左旋轉。
• 旋轉後結果：

    Asia
   /    \
  US    Sales

4. 插入 International

因 $\text{Asia} < \text{Sales} < \text{International}$，插入至 $\text{Sales}$ 的右子樹：

    Asia
   /    \
  US    Sales
          \
          International

5. 插入 Canada

因 $\text{Asia} < \text{Sales} < \text{Canada} < \text{International}$，插入至 $\text{International}$ 的左子樹：

    Asia (BF = -1)
   /    \
  US    Sales (BF = -2)
          \
          International (BF = 1)
          /
        Canada (BF = 0)

核心觀念

Post-order traversal（後序走訪）遵循：

$$\text{左子樹} \rightarrow \text{右子樹} \rightarrow \text{根節點}$$

因此，每個節點必須等其左、右子樹都走訪完成後，才輸出該節點儲存的字串。

解題方法

遞迴演算法如下：

PostOrder(node):
    if node == NULL:
        return

    PostOrder(node.left)
    PostOrder(node.right)
    print(node.string)

套用到 Figure 1 時，依序執行：

資料不足說明

題目所需的「Q5 取得的字串插入順序」、「Figure 1 的二元樹」及「Ord encoding 定義」未提供；目前附圖內容為物理化學考卷，並非本題的二元樹。因此無法唯一計算每個字串的實際雜湊位置與最終雜湊表。以下給出可直接套用的定案解法。

核心觀念

本題考查：

1. 二元樹走訪結果作為字串插入順序。
2. 字串雜湊值的計算。
3. 雙重雜湊（double hashing）處理碰撞。
4. 雜湊表大小為 $13$，索引為 $0$ 至 $12$。

對每個字串 $s$：

$$\operatorname{HashCode}(s)=\sum_{c\in s}\operatorname{Ord}(c)$$

初始位置：

$$H(s)=\operatorname{HashCode}(s)\bmod 13$$

探查步距：

$$D(s)=11-\bigl(\operatorname{HashCode}(s)\bmod 11\bigr)$$

第 $i$ 次探查位置：

$$P_i=(H(s)+iD(s))\bmod 13,\qquad i=0,1,2,\ldots$$

其中 $i=0$ 是第一次嘗試的位置。

解題方法

先依 Q5 指定的二元樹走訪方式取得字串順序，記為：

$$s_1,s_2,\ldots,s_n$$

接著依序處理每個字串。

對任一字串 $s$：

1. 計算字串雜湊碼

將字串中每個字元的 Ord 值相加：

$$K=\operatorname{HashCode}(s)$$

2. 計算初始位置與步距

$$H=K\bmod 13$$ $$D=11-(K\bmod 11)$$

3. 依序探查

計算：

$$P_0=H$$ $$P_1=(H+D)\bmod 13$$ $$P_2=(H+2D)\bmod 13$$

依此類推，直到找到空格為止。每次插入都必須保留完整探查序列。

4. 填入雜湊表