有四個節點的二元樹連接圖(connected binary tree)結構中,樹的高度有可能為
A1
B2正確答案
C3正確答案
D4
E5
答案與詳解
B、C
正確答案
4個節點的二元樹，若高度定義為「邊數(層數-1)」，最平衡高度為2，最歪斜高度為3，故選2與3。
為什麼答案是 B、C
當樹最平衡時(如完全二元樹)，4個節點會佔據3層，高度(邊數)為3-1=2。
考點：高度下限考點：最平衡高度考點：最歪斜高度考點：層數與邊數混淆
載入中…
完整詳解
Pro · 無限重點 4個節點的二元樹，若高度定義為「邊數(層數-1)」，最平衡高度為2，最歪斜高度為3，故選2與3。
秒殺技巧
N個節點二元樹，高度(邊數)最小為 floor(log2(N))，最大為 N-1。帶入 N=4，最小為2，最大為3。逐選項分析
A高度下限✕
高度為1(邊數)代表最多2層，僅能容納1至3個節點(根1+子2)，無法容納4個節點。
B最平衡高度✓ 正確
當樹最平衡時(如完全二元樹)，4個節點會佔據3層，高度(邊數)為3-1=2。
C最歪斜高度✓ 正確
當樹最歪斜時(呈鏈狀)，4個節點會佔據4層，高度(邊數)為4-1=3。
D層數與邊數混淆✕ 陷阱
高度為4(邊數)代表有5層，至少需要5個節點才能構成鏈狀樹，4個節點無法達到。
E高度上限✕
高度為5(邊數)代表有6層，至少需要6個節點，4個節點絕對無法達到此高度。
N個節點二元樹的高度範圍 (高度=邊數)
| 樹的形態 | 層數 | 高度(邊數) | 節點數(N=4)範例 |
|---|---|---|---|
| 最平衡(完全二元樹) | floor(log2(N)) + 1 | floor(log2(N)) | 層數3, 高度2 |
| 最歪斜(鏈狀樹) | N | N - 1 | 層數4, 高度3 |
陷阱提醒
樹的「高度」有兩種定義：邊數(根為0)與層數(根為1)。本題正解為2和3，顯然是採用「邊數」定義。若誤用層數定義會錯選3和4，務必先從選項反推題目採用的定義！