數據結構考研真題：n個節點深度為n的二叉樹形態計數

題目

具有 n 個節點且深度也為 n 的二叉樹有多少種？

答案

2^(n-1) 種

詳細推導

結構約束分析

• n個節點，深度為n → 樹必須是一條「鏈」
• 根節點深度1，每層最多1個節點，共n層
• 除根節點外，每個節點必須是其父節點的左孩子或右孩子

遞推關係

n=1: 只有根節點          → 1種 = 2^0
n=2: 根 + 左/右孩子       → 2種 = 2^1
n=3: 根 + 孩子 + 孫子     → 4種 = 2^2
...
n:   根 + (n-1)個非根節點 → 2^(n-1) 種

數學證明

1. 根節點位置固定，無選擇
2. 剩餘 n-1 個節點，每個節點有 2 種選擇：作為父節點的左孩子 或 右孩子
3. 根據乘法原理：2 × 2 × ... × 2 (n-1 次) = 2^(n-1)

圖形化展示 (n=3)

    根           根           根           根
   /            \            /            \
  2             2           2             2
 /              \          /              \
3               3         3               3
左左           右右       左右           右左

相關考點擴展

解題技巧總結

1. 極值條件 (節點數=深度) → 推導結構約束
2. 識別遞歸/組合本質 → 建立計數模型
3. 驗證小數值 (n=1,2,3) → 歸納通項公式
4. 注意根節點特殊性 → 指數為 n-1 而非 n