複選題
11. 有四個節點的二元樹連接圖(connected binary tree)結構中，樹的高度有可能為
(A)1
(B)2
(C)3
(D)4
(E)5

【解題思路】

關鍵觀念只有兩個：

1. 本題的「樹的高度」＝根到最深葉節點的「邊數」
   （不是層數）

2. 四個節點的二元樹，可能的高度介於：
   最矮（最平衡）＝2
   最深（退化成鏈）＝3

原因如下：

【觀念 1：高度＝邊數】

高度 2 代表：
根 → 子 → 孫
共走 2 條邊。

高度 3 代表：
根 → 子 → 孫 → 曾孫
共走 3 條邊。

【觀念 2：四個節點的二元樹可能最矮長相】

四個節點要盡可能放得平衡，最矮可以是高度 = 2：

最深路徑只有兩條邊："root → child → child"
→ 高度可能為 2（選 B）

【觀念 3：四個節點的二元樹可能最深長相】

若樹長成一條鏈，則高度 = 3：

從根到最深葉節點走了 3 條邊
→ 高度可能為 3（選 C）

【為什麼其他選項不可能？】

(A) 1
→ 只有 1 條邊時最多只有 2 個節點，不足以放 4 個節點。

(D) 4
→ 需要 5 個節點才能有 4 條邊，但題目只有 4 個節點。

(E) 5
→ 更不可能，至少要 6 個節點。

【延伸知識】

一般化：

n 個節點的二元樹高度可能介於：

• 最小高度 = ⌈log₂(n+1)⌉ − 1（邊數）

• 最大高度 = n − 1

對 n = 4：

• 最小高度 = ⌈log₂(5)⌉ − 1 = 3 − 1 = 2

• 最大高度 = 4 − 1 = 3

完全符合本題。

【記憶技巧】

一句話秒記：

四節點二元樹，高度一定介於 2 和 3 之間。

【常見錯誤】

1. 把「層數」當「高度」來算（會得 3～4）

2. 忽略本題高度定義是「邊數」

3. 以為二元樹一定要左右平均（其實不必）