地特三等申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
給定一個以一維陣列 A[i]所表示的二元樹（binary tree）如下：（每小題 5 分，共 30 分） i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[i]: T S U B O G _ _ _ _ P X _ _ _
給定一個以一維陣列 A[i]所表示的二元樹（binary tree）如下：（每小題 5 分，共 30 分） i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[i]: T S U B O G _ _ _ _ P X _ _ _
📝 此題為申論題，共 6 小題
小題 (一)
請問該樹樹高為何？
思路引導 VIP
判斷陣列表示的二元樹樹高，需先找出陣列中存放有效資料的最大索引值，再利用完全二元樹的層次特性推算。索引值落在 $2^{k-1}$ 至 $2^k-1$ 區間，即表示在第 k 層。
小題 (二)
請列舉該樹所有葉節點（leaf node）。
思路引導 VIP
看到陣列表示的二元樹，首要回想其索引對應規則：若節點索引為 i，則其左子節點為 2i，右子節點為 2i+1。找出所有本身非空，且其左右子節點皆為空（標示為 _ 或超出陣列範圍）的節點，即為葉節點。
小題 (三)
A[i]所代表的節點之左子節點（left-child node）應在陣列 A[.]的那一個位置？請寫出公式。
思路引導 VIP
看到二元樹以一維陣列表示且索引從 1 開始時，應立即聯想到完全二元樹（Complete Binary Tree）的陣列儲存特性。利用其層序走訪的數學性質，節點 i 的左子節點索引必為 2i，右子節點為 2i + 1。
小題 (四)
請寫出該樹之後序遍歷（Postorder Traversal）結果。
思路引導 VIP
先利用一維陣列表示二元樹的規則（節點 i 的左子節點為 2i，右子節點為 2i+1）還原出二元樹的結構。接著套用後序遍歷（Postorder Traversal）「左子樹 → 右子樹 → 樹根」的順序進行走訪即可得出答案。
小題 (五)
請寫出該樹之前序遍歷（Preorder Traversal）結果。
思路引導 VIP
看到一維陣列表示的二元樹，首先要聯想到節點索引的數學關係：節點 i 的左子節點必為 2i，右子節點必為 2i+1。先根據此規則在紙上畫出真實的樹狀結構，最後再套用前序遍歷「根節點→左子樹→右子樹」的口訣依序寫出答案。
小題 (六)
請寫出該樹之中序遍歷（Inorder Traversal）結果。
思路引導 VIP
看到一維陣列表示二元樹，第一步先利用「節點 i 的左子點為 2i、右子點為 2i+1」的規則還原出樹狀圖結構。第二步再針對畫出的二元樹，嚴格執行中序遍歷「左子樹 → 樹根 → 右子樹」的走訪順序即可求出正確解答。