C++ 實現二叉搜索樹 (BST) 完整教程：插入、刪除、查找與遍歷

節點結構與樹類模板

template <typename T>
struct BinaryNode {
    T element;
    BinaryNode* left;
    BinaryNode* right;
    
    BinaryNode(const T& e, BinaryNode* l = nullptr, BinaryNode* r = nullptr)
        : element(e), left(l), right(r) {}
};

template <typename T>
class BinarySearchTree {
public:
    BinarySearchTree() : root(nullptr) {}
    ~BinarySearchTree() { makeEmpty(); }
    
    // 公有介面
    const T& findMin() const;
    const T& findMax() const;
    bool contains(const T& x) const;
    bool isEmpty() const { return root == nullptr; }
    void printTree() const;          // 中序遍歷輸出
    void insert(const T& x);
    void remove(const T& x);
    void makeEmpty();
    
private:
    BinaryNode<T>* root;
    
    // 私有遞歸輔助函數
    void insert(const T& x, BinaryNode<T>*& t) const;
    void remove(const T& x, BinaryNode<T>*& t) const;
    BinaryNode<T>* findMin(BinaryNode<T>* t) const;
    BinaryNode<T>* findMax(BinaryNode<T>* t) const;
    bool contains(const T& x, BinaryNode<T>* t) const;
    void printTree(BinaryNode<T>* t) const;
    void makeEmpty(BinaryNode<T>*& t) const;
};

二、核心操作實現詳解

1. 查找最小值 / 最大值

利用 BST 性質：最小值在最左葉節點，最大值在最右葉節點。

// 遞歸版 findMin
template <typename T>
BinaryNode<T>* BinarySearchTree<T>::findMin(BinaryNode<T>* t) const {
    if (t == nullptr) return nullptr;
    if (t->left == nullptr) return t;
    return findMin(t->left);
}

// 迭代版 findMax（面試常考非遞歸寫法）
template <typename T>
BinaryNode<T>* BinarySearchTree<T>::findMax(BinaryNode<T>* t) const {
    if (t == nullptr) return nullptr;
    while (t->right != nullptr) t = t->right;
    return t;
}

// 公有介面
template <typename T>
const T& BinarySearchTree<T>::findMin() const {
    if (isEmpty()) throw runtime_error("Tree is empty");
    return findMin(root)->element;
}

2. 包含判斷 contains

template <typename T>
bool BinarySearchTree<T>::contains(const T& x, BinaryNode<T>* t) const {
    if (t == nullptr) return false;
    if (x < t->element) return contains(x, t->left);
    if (x > t->element) return contains(x, t->right);
    return true;  // 找到
}

3. 插入操作 insert

template <typename T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>*& t) const {
    if (t == nullptr) {
        t = new BinaryNode<T>(x, nullptr, nullptr);
    } else if (x < t->element) {
        insert(x, t->left);
    } else if (x > t->element) {
        insert(x, t->right);
    }
    // 相等不處理（忽略重複）
}

4. 刪除操作 remove —— 核心難點

刪除節點 t 需分三種情況處理（參考下圖）：

1. 葉節點（無子節點）：直接 delete，父節點對應指標置 nullptr
2. 單子節點：用子節點替換被刪節點位置
3. 雙子節點：核心技巧——在右子樹中找最小值節點（或左子樹最大值），用其鍵值覆蓋當前節點，遞歸刪除右子樹中的最小值節點（該節點必屬於情況 1 或 2）

template <typename T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>*& t) const {
    if (t == nullptr) return;  // 未找到
    
    if (x < t->element) {
        remove(x, t->left);
    } else if (x > t->element) {
        remove(x, t->right);
    } else {  // 找到目標節點 t
        if (t->left != nullptr && t->right != nullptr) {  // 情況 3：雙子節點
            t->element = findMin(t->right)->element;      // 用右子樹最小值替換
            remove(t->element, t->right);                 // 刪除右子樹中該最小值節點
        } else {  // 情況 1 或 2：至多一個子節點
            BinaryNode<T>* old = t;
            t = (t->left != nullptr) ? t->left : t->right;  // 子節點頂替
            delete old;
        }
    }
}

5. 中序遍歷輸出 printTree

template <typename T>
void BinarySearchTree<T>::printTree(BinaryNode<T>* t) const {
    if (t != nullptr) {
        printTree(t->left);
        cout << t->element << " ";
        printTree(t->right);
    }
}

6. 清空樹 makeEmpty（後序遍歷釋放）

template <typename T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>*& t) const {
    if (t != nullptr) {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
        t = nullptr;
    }
}

三、完整可編譯測試程式

#include <iostream>
#include <stdexcept>
using namespace std;

// ... 上述 BinarySearchTree 完整實現 ...

int main() {
    BinarySearchTree<int> bst;
    
    // 插入測試
    vector<int> data = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};
    for (int v : data) bst.insert(v);
    
    cout << "中序遍歷 (有序): ";
    bst.printTree();  // 10 20 25 30 35 40 45 50 60 70 80
    cout << endl;
    
    cout << "最小值: " << bst.findMin() << endl;  // 10
    cout << "最大值: " << bst.findMax() << endl;  // 80
    cout << "包含 35: " << bst.contains(35) << endl;  // 1
    cout << "包含 99: " << bst.contains(99) << endl;  // 0
    
    // 刪除測試
    bst.remove(20);  // 葉節點
    bst.remove(30);  // 單子節點 (左子 25)
    bst.remove(50);  // 雙子節點 (根節點)
    
    cout << "刪除 20,30,50 後: ";
    bst.printTree();  // 10 25 35 40 45 60 70 80
    cout << endl;
    
    return 0;
}

四、複雜度分析

h 為樹高。平衡時 h ≈ log₂n，極端有序插入退化為鏈表 h = n。

五、工程化增強建議

1. 智慧指標管理記憶體 (C++11)

template <typename T>
struct Node {
    T element;
    unique_ptr<Node> left, right;
    Node(const T& e) : element(e) {}
};

// 遞歸函數改用 unique_ptr& 參數，無需手動 delete

2. 迭代器支援範圍 for

// 實現 begin()/end() 返回 inorder_iterator
// 支援 range-based for: for (auto v : bst) cout << v;

3. 重複鍵值處理策略

• 計數器：int count; 节點存儲重複次數
• 多路樹：允許重複鍵值進右子樹（或左）
• 忽略/覆蓋/報錯：視業務而定

4. 平衡樹演進方向

BST 非自平衡，實際工程請使用：

• std::map/std::set：紅黑樹實現，標準庫現成
• AVL 樹：嚴格平衡，查找密集場景
• 紅黑樹：統計性能優，寫入友好，STL 底層
• Treap / Splay / B+ 樹：特定場景優化

六、面試高頻考點總結

1. BST 性質驗證：中序遍歷遞增、遞歸檢查 min < node < max
2. 第 K 小元素：中序遍歷計數、或節點增維 size 域 O(log n)
3. 最近公共祖先 (LCA)：利用 BST 性質單次遍歷 O(h)
4. 兩節點和為目標值：雙指針中序遍歷（正向+逆向迭代器）
5. 修復交換的兩節點：中序遍歷找逆序對
6. 序列化/反序列化：前序+特殊標記、或層序

七、總結

二叉搜索樹以其優雅的遞歸結構、O(log n) 平均效能、簡單直觀的實現，成為資料結構教學與工程基礎的核心。本文提供的完整模板實現涵蓋所有核心操作，重點闡述了刪除操作的三種情況處理邏輯與遞歸/迭代雙實現風格。理解 BST 是通往 AVL、紅黑樹、B+ 樹等進階平衡樹的必經之路。建議讀者：

1. 手寫完整實現並通過測試用例驗證
2. 對比遞歸與迭代版本，理解棧幀與指標操作的等價性
3. 嘗試用 unique_ptr 重寫記憶體管理
4. 學習 std::map 底層紅黑樹實現（GCC libstdc++ / LLVM libc++ 源碼）

代碼倉庫建議：建立個人資料結構庫，持續重構優化，面試與實戰兩不誤。