從零手寫二叉搜索樹（C++）：封裝、插入、刪除、查找與遍歷完整實現

二叉搜索樹（BST）是基礎且重要的動態數據結構，滿足「左子樹鍵值 < 根節點 < 右子樹鍵值」特性。本文從節點定義出發，逐步封裝出功能完整的 searchTree 類，提供 insert、erase、find、size 等標準接口，並詳細剖析最複雜的 刪除操作 四種情況處理邏輯。

節點與樹類設計

class TreeNode {
public:
    int value;
    TreeNode *left, *right, *parent;
    TreeNode() : value(0), left(nullptr), right(nullptr), parent(nullptr) {}
};

class SearchTree {
    int treeSize;
    TreeNode* root;
public:
    SearchTree(const int& value);           // 構造函數：創建根節點
    int insert(const int& value);           // 插入，成功返回0
    int erase(const int& value);            // 刪除，成功返回0
    TreeNode* find(const int& value);       // 查找，失敗返回NULL
    int size() const { return treeSize; }   // 節點數
    TreeNode* rootNode() { return root; }   // 獲取根節點（供遍歷）
};

核心操作實現

查找 find

從根節點開始，值小則走左，大則走右，直到找到或遇到 NULL。

TreeNode* SearchTree::find(const int& value) {
    TreeNode* curr = root;
    while (curr) {
        if (curr->value > value) curr = curr->left;
        else if (curr->value < value) curr = curr->right;
        else return curr;
    }
    return nullptr;
}

插入 insert

邏輯同查找，但需記錄父節點 par 與下降方向 direct（0左/1右），以便在空位處掛接新節點並維護 parent 指針。

int SearchTree::insert(const int& value) {
    TreeNode *curr = root, *par = root;
    int direct = -1;
    while (curr) {
        par = curr;
        if (curr->value > value) { curr = curr->left; direct = 0; }
        else if (curr->value < value) { curr = curr->right; direct = 1; }
        else return 1; // 值已存在
    }
    curr = new TreeNode(); curr->value = value;
    if (direct == 0) par->left = curr;
    else par->right = curr;
    curr->parent = par;
    treeSize++;
    return 0;
}

刪除 erase —— 核心難點

刪除後必須保持 BST 特性。根據被刪節點左右子樹情況分四類處理，核心是找到替代節點填補空位：

// 情況4核心邏輯（節選）
TreeNode* replace = curr->right;
if (replace->left == nullptr) { // 右子節點無左子樹，自身即替代
    replace->left = curr->left;
    if (curr->left) curr->left->parent = replace;
} else { // 沿右子節點左子鏈到底
    TreeNode* replacePar = replace;
    while (replace->left) { replacePar = replace; replace = replace->left; }
    replacePar->left = replace->right;           // 替代節點右子樹上移
    if (replace->right) replace->right->parent = replacePar;
    replace->left = curr->left; curr->left->parent = replace;
    replace->right = curr->right; curr->right->parent = replace;
}
// 最後：父節點指向replace，更新replace->parent，delete curr，treeSize--

測試驗證

void output(TreeNode* node) { // 中序遍歷輸出（應有序）
    if (node) { output(node->left); cout << node->value << "-"; output(node->right); }
}

int main() {
    SearchTree tree(100);
    for (int i = 0; i < 20; i++) tree.insert(rand() % 200);
    cout << "Size: " << tree.size() << endl;
    tree.erase(41);
    output(tree.rootNode()); // 輸出應為升序
    return 0;
}

總結

• 封裝隱藏指針操作細節，對外提供簡潔接口。
• 刪除操作通過「分類討論+替代節點」策略，保證結構完整性。
• 中序遍歷驗證 BST 有序性；內存視圖可直觀觀察指針關係。