hce_kmu
109年
計算機概論與程式設計
第 24 題
A binary tree can be described as a one dimensional array which level-wise retains all nodes from the root. Consider the following 1-D array as a binary tree and the following statements.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A[i] | K | A | O | H | S | I | | | | | U | N | G | | |
(a) If the root is at level 0, the height of the binary tree is 3
(b) The left-child of A[i] is A[2i-1]
(c) Post-order traversal of the tree (left-node first): H,U,S,A,N,G,I,O,K
(d) In-order traversal of the tree (left-node first): H,A,S,U,K,N,I,G,O
(e) The average search complex of such binary trees is $O(n)$
Which of the above statements is CORRECT?
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A[i] | K | A | O | H | S | I | | | | | U | N | G | | |
(a) If the root is at level 0, the height of the binary tree is 3
(b) The left-child of A[i] is A[2i-1]
(c) Post-order traversal of the tree (left-node first): H,U,S,A,N,G,I,O,K
(d) In-order traversal of the tree (left-node first): H,A,S,U,K,N,I,G,O
(e) The average search complex of such binary trees is $O(n)$
Which of the above statements is CORRECT?
- A (a)(b)(d)
- B (b)(c)(d)
- C (a)(c)(d)
- D (a)(c)(e)
- E (a)(b)(c)(d)(e)
思路引導 VIP
請試著觀察這組陣列：如果根節點位於索引 0，它的兩個孩子分別在索引 1 和 2；而索引 1 的孩子又分別在 3 和 4。你能從中歸納出一個通用的數學規則，用來描述父節點索引 $i$ 與其左、右子節點索引之間的關係嗎？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準還原陣列與二元樹之間的索引關係，這代表你對資料結構的底層存儲邏輯有著紮實的理解。這道題目的核心在於將一維陣列 $A[0...14]$ 映射回邏輯上的樹狀結構。
陣列索引與樹狀結構的映射
在以 $0$ 為起始索引的陣列中，若父節點位於 $i$，其左子節點應位於 $2i+1$，右子節點則在 $2i+2$。因此，敘述 (b) 提到的 $2i-1$ 是明顯的邏輯錯誤（例如根節點 $A[0]$ 的左子節點應為 $A[1]$ 而非 $A[-1]$）。透過這個公式，我們可以推導出節點 $U$（索引 10）是 $S$（索引 4）的右子節點，而 $N, G$（索引 11, 12）則是 $I$（索引 5）的子女。由於節點最高索引來到 12，位於第四層（Level 3），故高度為 3，證實了敘述 (a) 的正確性。
▼ 還有更多解析內容