C++ 數據結構：二叉搜索樹完整實現（增刪查遍歷）

BST 定義與性質

二叉搜索樹：左子樹鍵值 < 根 < 右子樹鍵值，左右子樹亦為 BST。支持 O(h) 查找/插入/刪除 (h 為樹高)。

核心操作實現

節點結構

struct Node {
    int key;
    Node *left, *right;
    Node(int k): key(k), left(nullptr), right(nullptr) {}
};

查找

Node* search(Node* root, int key) {
    if (!root || root->key == key) return root;
    return key < root->key ? search(root->left, key) : search(root->right, key);
}

插入

Node* insert(Node* root, int key) {
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root; // 忽略重複鍵
}

刪除（三種情況）

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) root->left = deleteNode(root->left, key);
    else if (key > root->key) root->right = deleteNode(root->right, key);
    else { // 找到目標
        if (!root->left) { Node* t=root->right; delete root; return t; }
        if (!root->right) { Node* t=root->left; delete root; return t; }
        // 兩子皆在：找後繼者（右子樹最小）
        Node* succ = root->right;
        while (succ->left) succ = succ->left;
        root->key = succ->key;
        root->right = deleteNode(root->right, succ->key);
    }
    return root;
}

三種遍歷（遞歸 + 非遞歸棧）

// 遞歸
void inorder(Node* root) { if(root){ inorder(root->left); cout<key; inorder(root->right); } }

// 非遞歸中序（棧）
void inorderIter(Node* root) {
    stack st; Node* cur=root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur=cur->left; }
        cur=st.top(); st.pop(); cout<key; cur=cur->right;
    }
}

完整可運行程序

包含菜單驅動測試：插入、查找、刪除、三種遍歷輸出、樹形顯示、銷毀釋放內存。

性能與優化

• 平均情況 O(log n)，最壞 O(n)（退化為鏈表）
• 平衡樹（AVL、紅黑、Treap、Splay）保證 O(log n) 最壞情況
• 實際工程推薦用 `std::set`/`std::map`（紅黑樹實現）

BST 是數據結構教學核心，理解其遞歸性質與指針操作，是掌握樹類數據結構的基石。