高考申論題
114年
[資訊處理] 資料結構
第 一 題
📖 題組：
二元搜尋樹（binary search tree）是一種常見的資料結構。
二元搜尋樹（binary search tree）是一種常見的資料結構。
📝 此題為申論題，共 4 小題
小題 (一)
請將 50, 30, 70, 20, 40, 60, 80 依序插入一個二元搜尋樹，然後再從該二元樹刪除 50，並畫出每個數字放入或刪除後的二元搜尋樹。（10 分）
思路引導 VIP
掌握二元搜尋樹（BST）的兩大原則：插入時遵循「左小右大」；刪除度數為 2 的節點時，須找「左子樹的最大值（前驅）」或「右子樹的最小值（後繼）」進行替換。繪圖時須一步一步呈現，並在刪除步驟中明確寫出替換依據以獲取高分。
小題 (二)
以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪除 40，請顯示該陣列的變化。（5 分）
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
A(i) 40 30 70 10 -- 50 90 -- 20 -- -- -- 60 80 -- -- --
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
A(i) 40 30 70 10 -- 50 90 -- 20 -- -- -- 60 80 -- -- --
思路引導 VIP
首先根據陣列索引規則（左子節點為 2i，右子節點為 2i+1）還原出二元搜尋樹的結構。接著應用二元搜尋樹的刪除規則，刪除具有兩個子節點的根節點 40 時，可選擇以『左子樹最大值』或『右子樹最小值』來遞補，最後計算遞補後各節點的新索引位置並寫出陣列變化。
小題 (三)
以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪除 30，請顯示該陣列的變化。（5 分）
思路引導 VIP
看到此題，應先聯想以一維陣列表示二元樹的索引規則：若節點位於 A[i]，其左子節點為 A[2i]，右子節點為 A[2i+1]。接著套用二元搜尋樹 (BST) 刪除節點的三種情況（無子節點、單一子節點、雙子節點），對應計算出陣列中需要被修改或清空的索引位置。
小題 (四)
以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，請列舉可依序插入的五個數值，使得該二元樹成為完整二元樹（full binary tree）。（10 分）
思路引導 VIP
作答此題需先釐清「完整二元樹 (Full Binary Tree)」的定義（國考常指節點數為 2^h-1 的完美二元樹）。接著依據二元搜尋樹「左 < 根 < 右」的性質，推導出應插入的數值範圍，並透過控制插入順序，確保新節點能正確落於陣列的特定索引位置。若遇考卷漏印初始陣列，應主動假設合理情境並詳列推導步驟以爭取分數。
二元搜尋樹操作
💡 依左小右大原則維護結構，並以特定規則進行節點刪除與陣列映射。
🔗 BST 刪除兩子節點處理鏈
- 1 定位節點 — 尋找欲刪除之目標節點並確認其具有左右子節點
- 2 尋找替補 — 找尋左子樹最大值 (Predecessor) 或右子樹最小值
- 3 數值置換 — 將替補節點的數值複製到欲刪除之目標節點位置
- 4 移除替補 — 刪除原替補節點位置，此點必為葉點或僅有一子
↓
↓
↓
🔄 延伸學習：延伸學習：學習如何透過旋轉 (Rotation) 維持 AVL 樹的平衡。
