高考申論題
107年
[工業行政] 計算機概論
第 四 題
請分別以陣列表示法（array representation）及鏈結表示法（linked representation）來表示圖一所示之二元樹（binary tree)。（20 分）
圖一
S
/ \
T U
/ \
W X
圖一
S
/ \
T U
/ \
W X
📝 此題為申論題
思路引導 VIP
- 觀察圖形確認左右子樹關係：依據圖一連線方向的幾何位置，T、U為S的左、右子節點；W、X的連線由左上至右下，分別位於T、U的右下方，故判定皆為右子節點。
- 陣列表示法（Array Representation）：套用二元樹陣列索引公式（Root=1, Left=2i, Right=2i+1），計算各節點位置，空缺的左子樹位置補 NULL。
🤖
AI 詳解
AI 專屬家教
【破題】本題測驗二元樹（Binary Tree）之基本資料結構實作概念，需依據圖示之幾何連線方向準確判斷左、右子節點，並運用陣列索引公式與節點指標結構進行表示。 【論述】 一、陣列表示法（Array Representation）
▼ 還有更多解析內容
二元樹實作表示法
💡 掌握陣列索引公式 (2i, 2i+1) 與鏈結指標結構之差異。
| 比較維度 | 陣列表示法 (Array) | VS | 鏈結表示法 (Linked) |
|---|---|---|---|
| 定位方式 | 父子關係靠索引公式計算 | — | 靠指標直接指向記憶體位址 |
| 空間利用 | 稀疏樹會造成大量空間浪費 | — | 需額外存指標，但節點動態配置 |
| 優點 | 隨機存取速度快、省指標空間 | — | 方便插入與刪除、不受樹形限制 |
💬陣列適合完全二元樹（如 Heap）；鏈結適合一般或動態變動的樹。
