C++ 二叉搜索树：原理与增删查实现详解

Node* find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key)
            cur = cur->_left;
        else if (val > cur->_key)
            cur = cur->_right;
        else
            break; // 命中
    }
    return cur;
}

2.2. 插入节点

插入时需要保持'左 < 根 < 右'的性质。流程分为两步：先找位置，再插入。

注意两点：

1. 二叉搜索树通常不允许重复键值，若已存在则直接返回 false。
2. 需要记录父节点 pre，以便在遍历到空指针时，知道新节点应该挂在哪一边。

bool insert(const K& val) {
    // 空树情况
    if (_root == nullptr) {
        _root = new Node(val);
        return true;
    }

    Node* cur = _root;
    Node* curPre = nullptr; // 记录父节点

    while (cur) {
        if (val == cur->_key)
            return false; // 重复值，不插入
        else if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else {
            curPre = cur;
            cur = cur->_right;
        }
    }

    // 此时 cur 为空，curPre 是待插入位置的父节点
    Node* pNew = new Node(val);
    if (val < curPre->_key)
        curPre->_left = pNew;
    else
        curPre->_right = pNew;

    return true;
}

2.3. 删除节点

删除是最复杂的部分，需要分三种情况处理，同时保证删除后树的结构依然合法。

1. 叶子节点：直接删除。
2. 有一个孩子：用孩子替换当前节点。
3. 有两个孩子：不能直接删除，需要用替代节点覆盖当前节点的值，然后删除替代节点。通常选择右子树的最小节点（或左子树的最大节点）作为替代。

这里以选择右子树最小节点为例：

1. 找到右子树最小节点 rightMin。
2. 将 rightMin 的值覆盖到待删除节点 cur。
3. 删除 rightMin 节点（此时 rightMin 最多只有一个右孩子，简化了删除逻辑）。

bool erase(const K& val) {
    if (_root == nullptr)
        return false;

    Node* cur = _root;
    Node* curPre = nullptr;

    // 1. 查找待删除节点
    while (cur) {
        if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            curPre = cur;
            cur = cur->_right;
        } else {
            break; // 命中
        }
    }

    if (cur == nullptr)
        return false;

    // 2. 处理删除逻辑
    // 情况 1 & 2: 0 个或 1 个孩子
    if (cur->_left == nullptr || cur->_right == nullptr) {
        Node* curNext = cur->_left ? cur->_left : cur->_right;

        if (cur != _root) {
            if (curPre->_left == cur)
                curPre->_left = curNext;
            else
                curPre->_right = curNext;
        } else {
            _root = curNext;
        }
        delete cur;
    }
    // 情况 3: 两个孩子
    else {
        // 找右子树最小节点
        Node* rightMin = cur->_right;
        Node* rightMinPre = cur;
        while (rightMin->_left) {
            rightMinPre = rightMin;
            rightMin = rightMin->_left;
        }

        // 覆盖值
        cur->_key = rightMin->_key;

        // 删除 rightMin (此时 rightMin 最多只有右孩子)
        Node* rightMinNext = rightMin->_right;
        if (rightMinPre->_left == rightMin)
            rightMinPre->_left = rightMinNext;
        else
            rightMinPre->_right = rightMinNext;

        delete rightMin;
    }

    return true;
}

3. 完整实现代码

下面是完整的头文件实现，包含了析构函数和中序遍历辅助函数，方便调试。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

namespace BSTKey {
    template<class K>
    struct BSTNode {
        BSTNode<K>* _left;
        BSTNode<K>* _right;
        K _key;

        BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {}
    };

    template<class K>
    class BSTree {
    public:
        typedef BSTNode<K> Node;

        BSTree() : _root(nullptr) {}

        ~BSTree() {
            destroy(_root);
            _root = nullptr;
        }

        Node* find(const K& val) {
            Node* cur = _root;
            while (cur) {
                if (val < cur->_key)
                    cur = cur->_left;
                else if (val > cur->_key)
                    cur = cur->_right;
                else
                    break;
            }
            return cur;
        }

        bool insert(const K& val) {
            if (_root == nullptr) {
                _root = new Node(val);
                return true;
            }

            Node* cur = _root;
            Node* curPre = nullptr;
            while (cur) {
                if (val == cur->_key)
                    return false;
                else if (val < cur->_key) {
                    curPre = cur;
                    cur = cur->_left;
                } else {
                    curPre = cur;
                    cur = cur->_right;
                }
            }

            Node* pNew = new Node(val);
            if (val < curPre->_key)
                curPre->_left = pNew;
            else
                curPre->_right = pNew;
            return true;
        }

        bool erase(const K& val) {
            if (_root == nullptr)
                return false;

            Node* cur = _root;
            Node* curPre = nullptr;
            while (cur) {
                if (val < cur->_key) {
                    curPre = cur;
                    cur = cur->_left;
                } else if (val > cur->_key) {
                    curPre = cur;
                    cur = cur->_right;
                } else {
                    break;
                }
            }

            if (cur == nullptr)
                return false;

            if (cur->_left == nullptr || cur->_right == nullptr) {
                Node* curNext = cur->_left ? cur->_left : cur->_right;
                if (cur != _root) {
                    if (curPre->_left == cur)
                        curPre->_left = curNext;
                    else
                        curPre->_right = curNext;
                } else {
                    _root = curNext;
                }
                delete cur;
            } else {
                Node* rightMin = cur->_right;
                Node* rightMinPre = cur;
                while (rightMin->_left) {
                    rightMinPre = rightMin;
                    rightMin = rightMin->_left;
                }

                cur->_key = rightMin->_key;

                Node* rightMinNext = rightMin->_right;
                if (rightMinPre->_left == rightMin)
                    rightMinPre->_left = rightMinNext;
                else
                    rightMinPre->_right = rightMinNext;

                delete rightMin;
            }
            return true;
        }

        void inOrder() {
            _inOrder(_root);
            cout << endl;
        }

    private:
        Node* _root;

        void destroy(Node* root) {
            if (root == nullptr)
                return;
            destroy(root->_left);
            destroy(root->_right);
            delete root;
        }

        void _inOrder(Node* root) {
            if (root == nullptr)
                return;
            _inOrder(root->_left);
            cout << root->_key << " ";
            _inOrder(root->_right);
        }
    };

    void testBST() {
        BSTree<int> bst;
        vector<int> arr = { 8, 3, 10, 1, 6, 14, 5, 7, 13 };

        cout << "=== 创建二叉搜索树 ===\n";
        for (const auto& e : arr) bst.insert(e);
        cout << "中序遍历结果：";
        bst.inOrder();

        cout << "=== 查找数据 ===\n";
        cout << "查找 14: " << (bst.find(14) ? "存在" : "不存在") << endl;
        cout << "查找 28: " << (bst.find(28) ? "存在" : "不存在") << endl;

        cout << "=== 删除数据 ===\n";
        cout << "删除前：";
        bst.inOrder();
        bst.erase(6); // 删除有两个孩子的节点
        cout << "删除 6 后：";
        bst.inOrder();
        bst.erase(1); // 删除叶子节点
        cout << "删除 1 后：";
        bst.inOrder();
    }
}

4. 二叉搜索树的应用

4.1. K 模型

只存储 Key，用于判断某个元素是否存在。例如拼写检查器，将词库构建为 BST，查询单词是否在树中即可。

4.2. KV 模型

每个 Key 对应一个 Value，即键值对。例如英汉词典（英文->中文）、车牌号->停留时间统计等。

改造后的节点结构如下：

template<class K, class V>
struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
    // ... 构造函数略
};

通过这种方式，我们可以轻松实现单词频率统计等功能：遇到单词先查找，若存在则计数加一，否则插入并初始化为 1。

二叉搜索树的核心价值在于利用有序性换取了高效的操作性能。但在实际使用中需要注意，如果插入的数据本身是有序的，BST 会退化成链表，导致性能下降至 O(n)。这也是后续学习 AVL 树、红黑树等平衡二叉搜索树的动机所在——它们通过自平衡机制维持树的高度，兼顾了简洁性与稳定性。