二叉排序樹（BST）核心操作全解析：插入、刪除、查找與構建

定義與性質

二叉排序樹（BST）或為空樹，或滿足：左子樹鍵值 < 根 < 右子樹鍵值，且左右子樹皆為 BST。中序遍歷遞增有序。

節點結構

struct Node { short key; Node *lchild, *rchild; };

插入與構建

遞歸插入：空樹創建節點；鍵值小往左，大往右，相等忽略。構建函數循環讀入鍵值調用插入，以 '?' 結束。

刪除節點（三種情況）

1. 葉子節點：父節點對應指針置 NULL，free。
2. 單分支：父節點指向該分支，free。
3. 雙分支：找左子樹最大（或右子樹最小）節點替代，刪除該替代節點（轉化為情況 1/2）。代碼採用左子樹最右節點。

查找

遞歸比較鍵值，相等返回，小往左，大往右，空返回 NULL。平均 O(log n)，最壞 O(n)。

性能分析

查找長度取決於樹高。平衡時 ASL ≈ log₂ n；退化為鏈表時 ASL = n。頻繁插刪場景優於有序數組二分查找（插刪 O(n)）。

總結

BST 是動態查找表的基礎結構，掌握插入、刪除（特別是雙分支替代邏輯）、查找三大操作，並理解其平均/最壞性能差異，是數據結構核心考點。