手把手實作二元搜尋樹：從節點設計到插入/查找/刪除/中序遍歷完整 C++ 模板

二元搜尋樹核心性質

對任一節點：左子樹所有鍵值 < 節點鍵值 < 右子樹所有鍵值。平均操作複雜度 O(log n)，最壞退化為 O(n)（單支鏈狀），平衡樹（AVL/紅黑樹）可保證最壞 O(log n)。

逐步建構完整模板

Step 1：節點結構

template <class T>
class TreeNode {
public:
    TreeNode() : lson(NULL), rson(NULL), freq(1) {}
    T data;
    unsigned int freq;      // 重複鍵值計數
    TreeNode *lson, *rson;  // 左/右子節點
};

Step 2：類別介面宣告

template <class T>
class BST {
private:
    TreeNode<T> *root;
    void insertpri(TreeNode<T>* &node, T x);
    TreeNode<T>* findpri(TreeNode<T>* node, T x);
    void Deletepri(TreeNode<T>* &node, T x);
    void insubtree(TreeNode<T>* node);
public:
    BST() : root(NULL) {}
    void insert(T x);
    TreeNode<T>* find(T x);
    void Delete(T x);
    void traversal(); // 中序輸出有序序列
};

Step 3：插入 — 遞歸定位 + 計數

void BST<T>::insertpri(TreeNode<T>* &node, T x) {
    if (!node) { node = new TreeNode<T>(); node->data = x; return; }
    if (x < node->data) insertpri(node->lson, x);
    else if (x > node->data) insertpri(node->rson, x);
    else ++node->freq; // 相等計數
}

Step 4：查找 — 遞歸比對

TreeNode<T>* BST<T>::findpri(TreeNode<T>* node, T x) {
    if (!node) return NULL;
    if (x < node->data) return findpri(node->lson, x);
    if (x > node->data) return findpri(node->rson, x);
    return node;
}

Step 5：刪除 — 三種情況處理

void BST<T>::Deletepri(TreeNode<T>* &node, T x) {
    if (!node) return;
    if (x < node->data) Deletepri(node->lson, x);
    else if (x > node->data) Deletepri(node->rson, x);
    else {
        if (node->lson && node->rson) { // 兩個孩子：右子樹最小值取代
            TreeNode<T>* temp = node->rson;
            while (temp->lson) temp = temp->lson;
            node->data = temp->data;
            node->freq = temp->freq;
            Deletepri(node->rson, temp->data); // 遞歸刪除後繼節點
        } else { // 0 或 1 個孩子
            TreeNode<T>* temp = node;
            node = node->lson ? node->lson : node->rson;
            delete temp;
        }
    }
}

優化思考：上述刪除兩遍走訪右子樹，可嘗試單次遞歸同時完成「找後繼」與「刪除後繼」。

Step 6：中序遍歷 — 產出有序序列

void BST<T>::insubtree(TreeNode<T>* node) {
    if (!node) return;
    insubtree(node->lson);
    cout << node->data << ' '; // 重複值按 freq 輸出多次
    insubtree(node->rson);
}

懶惰刪除替代方案

節點保留只標記刪除，避免分配/釋放開銷，適合刪除頻率低、重複插入高場景；代價是樹高增長、查找變慢。

進階學習路徑

掌握 BST 後，建議依序攻克：AVL 樹（嚴格平衡）→ 伸展樹（適應性訪問）→ 紅黑樹（工程落地標準，STL map/set 底層）。