複選題
16. 在二元樹結構中，假設樹的高度為 3，則此樹的節點個數可 能為
(A) 15
(B) 4
(C) 3
(D) 32
(E) 10

【解題思路】

本題的關鍵一句話：

農會採用的高度（height）＝從根到最深葉節點的「邊數」

因此：

• 高度 = 3
  → 有 3 條邊
  → 代表 4 層（levels：0,1,2,3）

所以一棵高度 3 的二元樹：

1. 最少節點數：
   就長成鏈狀（一路往下）
   → 4 個節點（1→1→1→1）
   → 選項 B

2. 最多節點數：
   長成滿二元樹（每層都放滿）
   → 1 + 2 + 4 + 8 = 15
   → 選項 A

3. 中間所有介於最少 4 與最多 15 之間的數都可能出現
   → 10 也在 4～15 之間
   → 選項 E

因此答案：A、B、E

【逐一破題】

(A) 15
→ 高度 3 的滿二元樹（1 + 2 + 4 + 8 = 15）
→ 有可能（屬最大情況）

(B) 4
→ 長成一條鏈狀時（最少情況）
→ 有可能

(C) 3
→ 高度 3 表示至少需要 4 個節點
→ 不可能

(D) 32
→ 高度 3 不可能到這麼多節點
→ 不可能

(E) 10
→ 介於 4～15 之間
→ 有可能

【延伸知識】

高度（邊數）＝h 的二元樹：

• 層數 = h + 1

• 最少節點 = h + 1

• 最多節點 = 2^(h+1) − 1

本題 h = 3：

• 層數 = 4

• 最少 = 3+1 = 4

• 最多 = 2^(3+1) − 1 = 15

中間所有整數通通有可能 → 包括 10。

【記憶技巧】

一句話：

高度（邊數）= h → 節點介於 h+1 到 2^(h+1)-1。

【常見錯誤】

1. 把高度誤解為「層數」→ 會得到 3～7

2. 以為節點數固定，其實高度固定時節點是「範圍」

3. 沒注意農會採「邊數」定義