【数据结构】二叉搜索树 C++ 简单实现：增删查改全攻略

二叉搜索树（Binary Search Tree, BST） 的 C++ 简单实现
包含最常见的增、删、查、改操作，以及一些常用辅助函数。

以下代码尽量写得清晰、结构化，适合学习与理解。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// BST 节点定义
struct Node {
    int val;
    Node* left;
    Node* right;

    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
private:
    Node* root;

    // 辅助函数：递归插入
    Node* insertHelper(Node* node, int val) {
        if (node == nullptr) {
            return new Node(val);
        }
        if (val < node->val) {
            node->left = insertHelper(node->left, val);
        } else if (val > node->val) {
            node->right = insertHelper(node->right, val);
        }
        // 相等时可以选择不插入（或覆盖/计数，此处选择不插入）
        return node;
    }

    // 辅助函数：查找节点（返回节点指针）
    Node* findHelper(Node* node, int val) {
        if (node == nullptr || node->val == val) {
            return node;
        }
        if (val < node->val) {
            return findHelper(node->left, val);
        } else {
            return findHelper(node->right, val);
        }
    }

    // 辅助函数：找最小值节点（用于删除时找后继）
    Node* findMin(Node* node) {
        while (node && node->left) {
            node = node->left;
        }
        return node;
    }

    // 辅助函数：删除节点（递归版）
    Node* removeHelper(Node* node, int val) {
        if (node == nullptr) {
            return nullptr;
        }

        if (val < node->val) {
            node->left = removeHelper(node->left, val);
        } else if (val > node->val) {
            node->right = removeHelper(node->right, val);
        } else {
            // 找到要删除的节点
            // 情况1：没有子节点（叶子）
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                return nullptr;
            }
            // 情况2：只有一个子节点
            else if (node->left == nullptr) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                Node* temp = node->left;
                delete node;
                return temp;
            }
            // 情况3：有两个子节点 → 用右子树的最小节点替换
            else {
                Node* successor = findMin(node->right);
                node->val = successor->val;           // 复制值
                node->right = removeHelper(node->right, successor->val); // 删除后继
            }
        }
        return node;
    }

    // 辅助函数：中序遍历（验证 BST 是否正确）
    void inorderHelper(Node* node) {
        if (node == nullptr) return;
        inorderHelper(node->left);
        cout << node->val << " ";
        inorderHelper(node->right);
    }

    // 销毁整棵树（析构函数调用）
    void destroyTree(Node* node) {
        if (node == nullptr) return;
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }

public:
    BinarySearchTree() : root(nullptr) {}

    ~BinarySearchTree() {
        destroyTree(root);
    }

    // 插入
    void insert(int val) {
        root = insertHelper(root, val);
    }

    // 查找（是否存在）
    bool find(int val) {
        return findHelper(root, val) != nullptr;
    }

    // 查找并返回节点指针（用于修改值）
    Node* findNode(int val) {
        return findHelper(root, val);
    }

    // 删除
    void remove(int val) {
        root = removeHelper(root, val);
    }

    // 修改某个节点的值（先查找再修改）
    bool update(int oldVal, int newVal) {
        Node* node = findNode(oldVal);
        if (node == nullptr) {
            return false;
        }
        // 先删除旧值，再插入新值（最安全，避免破坏 BST 性质）
        remove(oldVal);
        insert(newVal);
        return true;
    }

    // 中序遍历（应该输出有序序列）
    void inorder() {
        cout << "中序遍历: ";
        inorderHelper(root);
        cout << endl;
    }

    // 层序遍历（调试用）
    void levelOrder() {
        if (!root) return;
        queue<Node*> q;
        q.push(root);
        cout << "层序遍历: ";
        while (!q.empty()) {
            Node* node = q.front(); q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl;
    }

    // 判断是否为空
    bool empty() const {
        return root == nullptr;
    }

    // 获取根节点值（仅用于调试）
    int getRootVal() const {
        return root ? root->val : -1;
    }
};

// 测试代码
int main() {
    BinarySearchTree bst;

    // 插入测试
    vector<int> arr = {50, 30, 70, 20, 40, 60, 80, 15, 25, 35, 45};
    for (int x : arr) {
        bst.insert(x);
    }

    cout << "插入后：" << endl;
    bst.inorder();      // 应该有序
    bst.levelOrder();

    // 查找
    cout << "\n查找 40: " << (bst.find(40) ? "存在" : "不存在") << endl;
    cout << "查找 100: " << (bst.find(100) ? "存在" : "不存在") << endl;

    // 修改（把 40 改为 42）
    cout << "\n修改 40 → 42: " << (bst.update(40, 42) ? "成功" : "失败") << endl;
    bst.inorder();

    // 删除
    cout << "\n删除 30：" << endl;
    bst.remove(30);
    bst.inorder();

    cout << "\n删除 70（有两个孩子）：" << endl;
    bst.remove(70);
    bst.inorder();

    cout << "\n删除 15（叶子节点）：" << endl;
    bst.remove(15);
    bst.inorder();

    return 0;
}

快速记忆要点（面试/刷题常用）

操作	时间复杂度（平均）	时间复杂度（最坏）	备注
查找	O(log n)	O(n)	最坏退化为链表
插入	O(log n)	O(n)	同上
删除	O(log n)	O(n)	两个孩子的情况最复杂
中序遍历	O(n)	O(n)	天然有序

常见面试追问方向

1. 如何判断一棵二叉树是否是 BST？（中序遍历是否严格递增）
2. 如何求 BST 的第 k 小元素？（中序遍历计数 / 记录子树大小）
3. BST 如何转成双向链表？（中序遍历 + 指针调整）
4. 如何在 BST 中找最近公共祖先？（类似二叉树 LCA，但利用大小关系更快）
5. 如何实现一个支持重复元素的 BST？（在 Node 中加 count 字段）

需要哪一部分再展开讲解（比如删除两种写法对比、平衡 BST 引出 AVL/红黑树、BST 转链表代码等），可以直接告诉我～