C++ 二叉搜索树详解：增删查改与 key/value 场景实现

有这些数据的二叉搜索树：

此时再插入 16

此时再插入 13

4. 二叉搜索树的查找

从根开始比较，查找 x，x 比根的值大则往右边查找，x 比根值小则往左边查找最多查找高度次，走到到空，还没找到，这个值不存在。如果不支持插入相等的值，找到 x 即可返回。如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

如下图，查找 3，要找到 1 的右孩子的那个 3。

前序：根左右 中序：左根右 后序：左右根

5. 二叉搜索树的删除

过程： 首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。 如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

要删除结点 N 左右孩子均为空 要删除的结点 N 左孩子位空，右孩子结点不为空 要删除的结点 N 右孩子位空，左孩子结点不为空 要删除的结点 N 左右孩子结点均不为空

但其实代码实现上可以划分为两种情况：

没有孩子和只有一个孩子视为一种情况，因为可以将没有孩子视作只有一个孩子 只不过这个孩子是 nullptr 罢了 有两个孩子

以下是具体的解决方案：

第一种情况：以只有右孩子为例子，把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点。没有孩子时 N 结点的父亲对应孩子的指针指向 nullptr 符合逻辑。

第二种情况：无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 R(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点。

手绘图举例

6. 二叉搜索树 key 和 key/value 使用场景

6.1 key 搜索场景：

只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。

简单举例：

车牌抬杆识别系统，判断车牌字符是否存在（后台将车牌号录入搜索二叉树） 检查一篇英文文章是否有错（词典录入二叉树） 编译器的语法检查（将库，自定义，关键词放入二叉树）

总之 key 的搜索二叉树一般用于快速查询数据是否存在。

6.2 key/val 搜索场景

每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速找到 key 对应的 value。key/value 的搜索场景实现的二叉搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value。

简单举例：

检查中英文互译系统（key 即 英文，value 即中文） 商场车库系统（收费自助类，通过存车票号，和入场时间计算租金） 读取一篇文章中英文出现的次数

7. 二叉搜索树的实现代码

7.1 key 模型代码实现

这里的 set 不是完全 set 的底层封装 本代码只是二叉搜索树 key 模型的实现代码

#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

// 去重版 set
namespace twg {
    //set -> ket 模型
    //搜索二叉树节点
    template<class K>
    struct BSTnode {
        //数据 K _key;
        //根值 BSTnode* left;
        //左孩子 BSTnode* right;
        //右孩子
        //构造
        BSTnode(const K& key = K()) { _key = key; left = nullptr; right = nullptr; }
        K _key;
        BSTnode* left;
        BSTnode* right;
    };

    //单参数的去重搜索二叉树容器 - > set
    template<class K>
    class set {
        typedef BSTnode<K> Node;
    public:
        //增删查
        //set and unoredered_set 不支持改 （会破坏结构）
        //增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现
        bool Insert(const K& key) {
            //在二叉搜索树的规则下 查询 新加入的节点的位置
            //能循环 尽量不 递归 这里采用双指针循环的方法
            //判断是否为空树
            if (_root == nullptr) {
                //新加入的节点为根节点
                _root = new Node(key);
            }
            //双指针 从根节点出发寻找合适位置
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    //该节点在 cur 的左子树处
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    //该节点在 cur 的右子树处
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    //key == cur->_key 即相同节点 直接跳过
                    return true;
                }
            }
            //当 cur 为空时 即新节点的位置找到了
            cur = new Node(key);
            //链接
            //判断子相对父的位置
            if (parent->right == nullptr) {
                //链接
                parent->right = cur;
            }
            else {
                parent->left = cur;
            }
            return true;
        }

        //删
        bool Erase(const K& key) {
            //查询当前数据在哪个地方
            //双指针 从根节点出发寻找合适位置
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    //该节点在 cur 的左子树处
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    //该节点在 cur 的右子树处
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    //key == cur->_key 即相同节点 找到该位置
                    //删除
                    //根绝删除节点的孩子个数 执行不同的删除逻辑
                    //0~1 个孩子的代码实现可以合并
                    //即可以把 0 个孩子看成 1 个空孩子
                    //假设只有右孩子
                    if (cur->left == nullptr) {
                        //删除根节点
                        if (parent == nullptr) {
                            _root = cur->right;
                        }
                        //删除局部节点
                        //将 cur 的右孩子链接成为 parent 的孩子
                        if (parent->left == cur) {
                            parent->left = cur->right;
                        }
                        else {
                            parent->right = cur->right;
                        }
                        delete cur;
                        //删除节点
                        cur = nullptr;
                        return true;
                    }
                    else {
                        //有两个孩子
                        //替代法
                        //这里以右子树的最小孩子替代 cur 为例
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        //最小孩子一定在右子树的最左节点处（不一定为叶子节点）
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }
                        //调整链接关系
                        //调整 parent 的链接关系
                        if (parent->left == cur) {
                            parent->left = rightMin;
                        }
                        else {
                            parent->right = rightMin;
                        }
                        //调整 rightMinp 的链接关系
                        rightMinf->left = rightMin->right;
                        //rightMin 不一定为叶子节点
                        //调整替换节点的父子链接关系
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;
                        //删除节点
                        delete cur;
                        cur = nullptr;
                        return true;
                    }
                }
            }
            cout << "没有该节点 " << endl;
            return false;
        }

        //查
        bool Find(const K& key) {
            //双指针 从根节点出发寻找合适位置
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    //该节点在 cur 的左子树处
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    //该节点在 cur 的右子树处
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    //key == cur->_key 即相同节点 直接跳过
                    return true;
                }
            }
            //没找到
            return false;
        }

        void Inorder() {
            assert(_root);
            inorder(_root);
        }
    private:
        //中序遍历
        void inorder(const Node* root) {
            //递归出口
            if (root == nullptr)
                return;
            //左根右
            inorder(root->left); //左子树
            cout << root->_key << endl;
            inorder(root->right);
        }
        Node* _root = nullptr; //根节点
    };
}

7.2 key/val 代码实现

二叉搜索树 key/val 模型代码实现

#pragma once
//key/val 模型的实现
#include <iostream>
using namespace std;

namespace twg {
    //key/val 节点
    template<class K, class V>
    struct BSTnode //其实就是 pair
    {
        //数据 K _key;
        //V _val;
        //BSTnode* left;
        //左孩子 BSTnode* right;
        //右孩子
        //构造函数
        BSTnode(const K& key, const V& val):_key(key),_val(val),left(nullptr),right(nullptr){}
        K _key;
        V _val;
        BSTnode* left;
        BSTnode* right;
    };

    // key/val 模型 容器 map
    template<class K, class V>
    class map {
        typedef BSTnode<K, V> Node;
    public:
        //默认成员函数
        //显示默认构造
        map() = default;
        //C++11 引用 告诉编译器帮我生成一个默认构造函数
        /*map() { _root = nullptr; }*/
        //拷贝构造
        map(const map<K, V>& a) {
            //递归式深拷贝
            _root = Copy(a._root);
        }
        //析构函数
        ~map() {
            Destory(_root);
        }
        //赋值
        map<K, V>& operator=(map<K, V> a) {
            std::swap(_root, a._root); //现代式写法 a 是临时拷贝对象 出了函数会自动析构
            return *this;
        }

        //增删查改
        //增
        bool Insert(const K& key, const V& val) {
            //先寻找位置
            //判断是否为空树
            if (_root == nullptr) {
                //新节点为根节点
                _root = new Node(key, val);
                return true;
            }
            //双指针循环
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                //根据 key 找
                if (key <= cur->_key) {
                    //新节点的位置在左子树处
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    //新节点的位置在右子树处
                    parent = cur;
                    cur = cur->right;
                }
            }
            //找到了 新节点的位置
            cur = new Node(key, val);
            //链接父子
            if (cur->_key <= parent->_key) {
                //新节点为 parent 的左孩子
                parent->left = cur;
            }
            else {
                //新节点为 parent 的右孩子
                parent->right = cur;
            }
            return true;
        }

        //遍历
        void Inorder() {
            _inorder(_root);
            cout << endl;
        }

        //查 根据 key
        bool Find(const K& key) {
            //双指针 从根节点出发寻找合适位置
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    //该节点在 cur 的左子树处
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    //该节点在 cur 的右子树处
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    //key == cur->_key 即相同节点 直接跳过
                    return true;
                }
            }
            //没找到
            return false;
        }

        //删除
        bool Erase(const K& key) {
            //先找
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                //根据 key 找
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    //找到了
                    //根据孩子的个数 执行不同的删除逻辑
                    //0~1 个孩子代码实现上相同
                    //可将叶子节点 视作只有一个空孩子
                    //假设只有右孩子
                    if (cur->right != nullptr) {
                        //判断该节点是否为根节点
                        if (parent == nullptr) {
                            //该节点为根节点
                            //右子树成为新的根节点
                            _root = cur->right;
                        }
                        //删除的是子树上的节点
                        else {
                            if (parent->left == cur) {
                                parent->left = cur->right;
                            }
                            else {
                                parent->right = cur->right;
                            }
                        }
                        //删除节点
                        delete cur;
                        cur = nullptr;
                        return true;
                    }
                    //有两个孩子
                    //替换法
                    //以 左子树的最大孩子为替代 不一定为叶子节点
                    Node* leftMax = cur->right;
                    Node* leftMaxf = cur;
                    while (leftMax->right) {
                        leftMaxf = leftMax;
                        leftMax = leftMax->right;
                    }
                    //找到了替换节点
                    //调整链接
                    cur->_val = leftMax->_val;
                    cur->_key = leftMax->_key;
                    leftMaxf->right = leftMax->left;
                    //删除节点
                    delete leftMax;
                    leftMax = nullptr;
                    return true;
                }
            }
            //删除失败
            cout << "没有该节点，删除失败" << endl;
            return false;
        }

        //改
        V& operator[](const K& key) {
            // 1. 查找键，若存在则返回对应值的引用
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                }
                else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                }
                else {
                    // 找到键，返回值的引用
                    return cur->_val;
                }
            }
            // 2. 键不存在，插入新节点（值用默认构造）
            cur = new Node(key, V());
            // 插入默认值（如 int 默认 0）
            if (parent == nullptr) {
                // 空树，新节点作为根
                _root = cur;
            }
            else {
                // 链接到父节点的左/右子树
                if (key < parent->_key)
                    parent->left = cur;
                else
                    parent->right = cur;
            }
            // 3. 返回新插入节点的值的引用
            return cur->_val;
        }

    private:
        //函数
        Node* Copy(const Node* root) {
            //递归出口
            if (root == nullptr)
                return nullptr;
            Node* newNode = new Node(root->_key, root->_val);
            newNode->left = Copy(root->left); //拷贝左子树
            newNode->right = Copy(root->right); //拷贝右子树
            return newNode;
        }

        void Destory(Node* root) {
            //递归出口
            if (root == nullptr)
                return;
            //递归式析构
            //先析构左右子树
            Destory(root->left);
            Destory(root->right);
            //析构根
            delete root;
            //核心  root =nullptr;
        }

        //遍历
        void _inorder(const Node* root) {
            //递归出口
            if (root == nullptr)
                return;
            //中序遍历
            _inorder(root->left); //左子树
            cout << root->_key << ": " << root->_val << endl; //根值
            _inorder(root->right); //右子树
        }

        //数据
        Node* _root = nullptr; //根节点
    };
}

结语

二叉搜索树的'左小右大'特性的背后，是高效数据查询的核心逻辑 —— 它既弥补了二分查找的插入删除短板，也为后续平衡树（AVL、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。