高考申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
給定二元樹（binary tree）如右圖，樹高為 4 且共有 7 個節點。 （一）請寫出該樹之後序遍歷（postorder traversal）結果。（5 分） （二）若以陣列 A[1..15]實作該二元樹，請列舉陣列 A[1..15]的內容。（5 分） （三）若要將數值 x 設為或取代 A[i]（任一 1 ≤ i ≤ 7）所代表的節點之右子節點（right child node）的內容，令 x 會被放入陣列中 A[j]的位置。請以 j、i 表示，寫出 j 位置之公式。（5 分） （四）若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿二元樹（full binary tree），請問最少各需加入幾個新節點？（5 分）
給定二元樹（binary tree）如右圖，樹高為 4 且共有 7 個節點。 （一）請寫出該樹之後序遍歷（postorder traversal）結果。（5 分） （二）若以陣列 A[1..15]實作該二元樹，請列舉陣列 A[1..15]的內容。（5 分） （三）若要將數值 x 設為或取代 A[i]（任一 1 ≤ i ≤ 7）所代表的節點之右子節點（right child node）的內容，令 x 會被放入陣列中 A[j]的位置。請以 j、i 表示，寫出 j 位置之公式。（5 分） （四）若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿二元樹（full binary tree），請問最少各需加入幾個新節點？（5 分）
📝 此題為申論題，共 6 小題
小題 (一)
請寫出該樹之後序遍歷（postorder traversal）結果。（5 分）
思路引導 VIP
解題應先根據圖形精確判斷各節點的「左、右子樹」從屬關係（例如從連線斜率判斷 S 只有右子節點 O）。確認樹狀結構後，套用後序遍歷「左子樹 → 右子樹 → 樹根（L-R-D）」的遞迴規則，分段求出左右子樹的遍歷順序後再合併即可。
小題 (二)
若以陣列 A[1..15]實作該二元樹，請列舉陣列 A[1..15]的內容。（5 分）
思路引導 VIP
- 先確認以一維陣列實作二元樹的規則：若父節點位於陣列索引 i，則其左子節點位於 2i，右子節點位於 2i+1。
- 仔細觀察圖形連線方向以判別左右子節點（向左下為左子節點，向右下為右子節點）。
小題 (三)
若要將數值 x 設為或取代 A[i]（任一 1 ≤ i ≤ 7）所代表的節點之右子節點（right child node）的內容，令 x 會被放入陣列中 A[j]的位置。請以 j、i 表示，寫出 j 位置之公式。（5 分）
思路引導 VIP
本題測驗二元樹以一維陣列實作（循序表示法）時，父子節點間的索引計算關係。考生只需回憶當陣列起始索引為 1 時，左、右子節點對應的索引公式（左：2i，右：2i+1）即可迅速作答。
小題 (四)
若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿二元樹（full binary tree），請問最少各需加入幾個新節點？（5 分）
思路引導 VIP
解題核心在於先透過陣列表示法（1-based index）確認現有各節點的確切位置，找出最大索引值與樹高。接著依據「完整二元樹（陣列索引連續無空缺）」與「完滿二元樹（各階層全滿，即完美二元樹）」的定義，推算出各自所需的總節點數，最後扣除原始節點數即可得解。
小題 (五)
請寫出該樹之前序遍歷（Preorder Traversal）結果。
思路引導 VIP
考生看到一維陣列表示的二元樹，第一步應立刻聯想其索引對應規則：節點 $i$ 的左子節點為 $2i$，右子節點為 $2i+1$。依此規則先在紙上畫出真實的樹狀結構，最後再依據前序遍歷『根節點 $\rightarrow$ 左子樹 $\rightarrow$ 右子樹』的順序讀取節點即可輕鬆取分。
小題 (六)
請寫出該樹之中序遍歷（Inorder Traversal）結果。
思路引導 VIP
解題首要步驟是根據一維陣列表示法還原二元樹結構，記住陣列索引 i 的左子節點為 2i、右子節點為 2i+1。在草稿紙上畫出清晰的樹狀圖後，依循「左子樹→根節點→右子節點」的順序進行中序遍歷（Inorder Traversal）即可得出正確結果。