二、樹相關的填空題
1.對于一個具有 n 個結點的二叉樹，當它為一棵 ________ 二叉樹時，具有最小高度，即為 ________；當它為一棵單支樹時具有最大高度，即為 ________。
2.對于一個具有 n 個結點的二叉樹，當它存儲在二叉鏈表中時，其指針字段的總數為 ________ 個，其中 ________ 個用于鏈接孩子結點; _______ 個空閑。
3.一棵深度為 k 的滿二叉樹的結點總數為 ________，
一棵深度為 k 的完全二叉樹的結點總數的最小值為 ________，最大值為 ________。
4. 由三個結點構成的二叉樹，共有 ________ 種不同的結構。

---

答案分析：

我們來逐條分析這些填空題的正確答案，并給出詳細的解釋。

第1題：

對于一個具有 n 個結點的二叉樹，當它為一棵 ________ 二叉樹時，具有最小高度，即為 ________；當它為一棵單支樹時具有最大高度，即為 ________。

? 答案：

滿二叉樹，????$?{\log }_2(n+1)?$，????n

🔍 解釋：

• 最小高度出現在完全填滿的情況下，也就是滿二叉樹（Full Binary Tree）。

  • 滿二叉樹每一層都填滿了節點。
  • 高度 $ h $ 的滿二叉樹最多有 $ 2^h - 1 $ 個節點；
  • 所以對于 n 個節點來說，最小高度為滿足 $ 2^{h} - 1 \geq n $ 的最小 h，即：
    $$h=?{\log }_2(n+1)?$$

• 最大高度出現在單支樹（退化成鏈表）的情況下，每個節點只有一個孩子，所以高度為 n。

第2題：

對于一個具有 n 個結點的二叉樹，當它存儲在二叉鏈表中時，其指針字段的總數為 ________ 個，其中 ________ 個用于鏈接孩子結點，________ 個空閑。

? 答案：

2n，????n - 1，????n + 1

🔍 解釋：

• 每個節點有兩個指針域（左孩子和右孩子），共 2n 個指針；
• 除了根節點外，每個節點都被一個指針所指向，所以只有 n - 1 個指針被使用；
• 因此，空指針數 = 總指針數 - 使用的指針數 = 2n - (n - 1) = n + 1

第3題：

一棵深度為 k 的滿二叉樹的結點總數為 ________，
一棵深度為 k 的完全二叉樹的結點總數的最小值為 ________，最大值為 ________。

? 答案：

$2^k?1$，????$2^{k?1}$，????$2^k?1$

🔍 解釋：

• 滿二叉樹：每層都填滿，總節點數是：
  $$2^0+2^1+?+2^{k?1}=2^k?1$$
• 完全二叉樹：最后一層可以不滿，但必須從左到右連續填充；
  • 最小情況：只有最后一層有一個節點，其余層都是滿的，即：
    $$2^{k?1}$$
  • 最大情況：就是滿二叉樹的情況，即：
    $$2^k?1$$

第4題：

由三個結點構成的二叉樹，共有 ________ 種不同的結構。

? 答案：

5

🔍 解釋：

這是求不同形態的二叉樹數量的問題。
對于 n 個節點的不同結構的二叉樹數目，是一個經典的卡特蘭數問題。

• 卡特蘭數公式：
  $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$
• 當 n = 3 時：
  $$C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=\frac{1}{4}\times 20=5$$

? 五種不同結構（形態）如下（根節點設為 A，左子樹、右子樹用 B、C 表示）：
結構 1：

    A/B/
C

A 只有左孩子 B
B 只有左孩子 C
結構 2：

A/B\C

A 只有左孩子 B
B 只有右孩子 C
結構 3：

A/ \B   C

A 有兩個孩子：B（左），C（右）
結構 4：

A\B/C

A 只有右孩子 B
B 只有左孩子 C
結構 5：

    A\B\C

A 只有右孩子 B
B 只有右孩子 C
?? 總結：
結構編號 圖形表示

1 A → B → C（全左單支）
2 A → B ←→ C（B 右子節點）
3 A 有兩個孩子 B 和 C（完整層次）
4 A → (右) B → (左) C
5 A → (右) B → (右) C（全右單支）

🧠 補充說明：

• 每一種結構都代表了不同的拓撲形態。
• 雖然結點名可以任意改變，但在不考慮名字的情況下，只有這5種互不相同的二叉樹結構。
• 注意區分“結構不同”與“中序/先序遍歷順序不同”，這里是根據形狀來判斷的。

? 最終完整答案匯總如下：

題號	填空內容	正確答案
1	對于一個具有 n 個結點的二叉樹，當它為一棵 ________ 二叉樹時，具有最小高度，即為 ________；當它為一棵單支樹時具有最大高度，即為 ________。	滿，???$?{\log }_2(n+1)?$，???n
2	其指針字段的總數為 ________ 個，其中 ________ 個用于鏈接孩子結點，________ 個空閑。	2n，???n - 1，???n + 1
3	滿二叉樹的結點總數為 ________，完全二叉樹的結點總數的最小值為 ________，最大值為 ________。	$2^k?1$，???$2^{k?1}$，???$2^k?1$
4	由三個結點構成的二叉樹，共有 ________ 種不同的結構。	5