二元樹基礎 (Binary Tree)#

資料結構的演進#

從線性到非線性的演化過程：

單向連結串列 → 雙向連結串列 → 樹 → 圖
   (1個next)     (prev+next)   (多個指標)  (可有環)

關鍵理解：

• 連結串列是特殊的樹（沒有分叉）
• 樹是特殊的圖（沒有環）

二元樹核心術語#

二元樹的分類學#

「二元樹」只是統稱，依照節點填滿的方式還可以細分。下面三種名稱在面試與教科書裡經常出現，務必分清楚：

三者的關係是：完美 ⊆ 完全，完美 ⊆ 完滿，但完全與完滿彼此並不互相包含。

完全二元樹特別重要：因為它「由左到右、由上到下」緊密填入、中間不留空洞，節點與陣列索引可以一一對應（節點 i 的左右子為 2i+1、2i+2），不需要任何指標。這正是 堆 (Heap) 能直接用陣列實作的原因。

面試常見的致命假設：

• 不要預設一棵樹是完美的——大多數題目給的是任意形狀的二元樹，分析複雜度時請以最差情況（退化成鏈）為準。
• 不要看到「樹」就假設它是二元搜尋樹 (BST)。除非題目明說有序，否則不能依賴左小右大的性質。

卡特蘭數：n 個節點能組成幾種二元樹？#

給定 n 個不同節點，能組合出多少種結構不同的二元樹？用遞迴的角度想最自然：

1. 先選一個節點當根。
2. 剩下的 n − 1 個節點要分給左右子樹：若左子樹放 k 個，右子樹就放 n − 1 − k 個。
3. 左子樹有 S(k) 種長法、右子樹有 S(n − 1 − k) 種長法，兩者獨立，相乘。
4. 把 k 從 0 枚舉到 n − 1 全部加起來，就是總數。

$$ S(n) = \sum_{k=0}^{n-1} S(k)\cdot S(n-1-k), \qquad S(0) = 1 $$

這個遞迴式的解，正是大名鼎鼎的卡特蘭數 (Catalan number) $C_n$。

有趣的是，許多看起來毫不相關的問題，最後算出來的答案都是同一串卡特蘭數：

• 凸多邊形的三角剖分有幾種；
• n 對括號的合法組合有幾種；
• n 個元素的合法出入棧序列有幾種；
• n 個節點的二元樹有幾種。

它們之所以同解，是因為背後都是「選一個分界點、把問題拆成獨立的左右兩半再相乘相加」這同一個遞迴骨架。能看出這層問題等價性，正是 演算法思維總綱 裡「把問題抽象成已知模型」的最佳練習。

二元搜尋樹 (BST)#

定義#

BST 必須滿足：

1. 左子樹所有節點值 < 根節點值
2. 右子樹所有節點值 > 根節點值
3. 左右子樹也必須是 BST（遞迴定義）

常見誤區：不能只比較直接子節點！必須確保整個子樹都滿足條件。

複雜度分析#

退化問題：依序插入 1,2,3,4,5 會使 BST 退化成連結串列，效率降為 O(n)。

解決方案：平衡二元樹#

• AVL 樹：嚴格平衡，左右子樹高度差 <= 1
• 紅黑樹：近似平衡，實作較簡單，工程常用

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}