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

此时再插入 16 和 13：

4. 二叉搜索树的查找

从根开始比较：

• 若 x 比根的值大，则往右边查找。
• 若 x 比根的值小，则往左边查找。
• 最多查找高度次，走到空节点还没找到，说明该值不存在。

如果不支持插入相等值，找到 x 即可返回；如果支持插入相等值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

遍历方式包括前序（根左右）、中序（左根右）、后序（左右根）。

5. 二叉搜索树的删除

首先查找元素是否在树中，如果不存在则返回 false。如果存在，根据要删除的结点 N 的孩子情况分四种处理：

1. 要删除结点 N 左右孩子均为空。
2. 要删除的结点 N 左孩子为空，右孩子不为空。
3. 要删除的结点 N 右孩子为空，左孩子不为空。
4. 要删除的结点 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 的搜索场景实现的二叉搜索树支持修改 value，但是不支持修改 key，修改 key 会破坏搜索树性质。

简单举例：

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

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

7.1 key 模型代码实现

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

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

// 去重版 set
namespace twg {
    template<class K>
    struct BSTnode {
        K _key;
        BSTnode* left;
        BSTnode* right;

        BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
    };

    template<class K>
    class set {
        typedef BSTnode<K> Node;
    public:
        bool Insert(const K& key) {
            if (_root == nullptr) {
                _root = new Node(key);
            }
            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 true; // 已存在
                }
            }
            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) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    if (cur->left == nullptr) {
                        if (parent == nullptr) {
                            _root = cur->right;
                        } else if (parent->left == cur) {
                            parent->left = cur->right;
                        } else {
                            parent->right = cur->right;
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }
                        if (parent->left == cur) {
                            parent->left = rightMin;
                        } else {
                            parent->right = rightMin;
                        }
                        rightMinf->left = rightMin->right;
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;
                        delete cur;
                        return true;
                    }
                }
            }
            cout << "没有该节点" << endl;
            return false;
        }

        bool Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (key < cur->_key) {
                    cur = cur->left;
                } else if (key > cur->_key) {
                    cur = cur->right;
                } else {
                    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;
    };
}

// 模拟 unordered_set 即不去重版
namespace Twg {
    template<class K>
    struct BSTnode {
        K _key;
        BSTnode* left;
        BSTnode* right;

        BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
    };

    template<class K>
    class set {
        typedef BSTnode<K> Node;
    public:
        bool Insert(const K& key) {
            if (_root == nullptr) {
                _root = new Node(key);
                return true;
            }
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key <= cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else {
                    parent = cur;
                    cur = cur->right;
                }
            }
            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) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    if (cur->left == nullptr) {
                        if (parent == nullptr) {
                            _root = cur->right;
                        } else if (parent->left == cur) {
                            parent->left = cur->right;
                        } else {
                            parent->right = cur->right;
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }
                        if (parent->left == cur) {
                            parent->left = rightMin;
                        } else {
                            parent->right = rightMin;
                        }
                        rightMinf->left = rightMin->right;
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;
                        delete cur;
                        return true;
                    }
                }
            }
            cout << "没有该节点" << endl;
            return false;
        }

        bool Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (key < cur->_key) {
                    cur = cur->left;
                } else if (key > cur->_key) {
                    cur = cur->right;
                } else {
                    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 代码实现

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

namespace twg {
    template<class K, class V>
    struct BSTnode {
        K _key;
        V _val;
        BSTnode* left;
        BSTnode* right;

        BSTnode(const K& key, const V& val) : _key(key), _val(val), left(nullptr), right(nullptr) {}
    };

    template<class K, class V>
    class map {
        typedef BSTnode<K, V> Node;
    public:
        map() = default;
        ~map() { Destory(_root); }

        map(const map<K, V>& a) {
            _root = Copy(a._root);
        }

        map<K, V>& operator=(map<K, V> a) {
            std::swap(_root, a._root);
            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) {
                if (key <= cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else {
                    parent = cur;
                    cur = cur->right;
                }
            }
            cur = new Node(key, val);
            if (cur->_key <= parent->_key) {
                parent->left = cur;
            } else {
                parent->right = cur;
            }
            return true;
        }

        bool Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (key < cur->_key) {
                    cur = cur->left;
                } else if (key > cur->_key) {
                    cur = cur->right;
                } else {
                    return true;
                }
            }
            return false;
        }

        bool Erase(const K& key) {
            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 {
                    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;
                        return true;
                    } else {
                        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;
                        return true;
                    }
                }
            }
            cout << "没有该节点，删除失败" << endl;
            return false;
        }

        V& operator[](const K& key) {
            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;
                }
            }
            cur = new Node(key, V());
            if (parent == nullptr) {
                _root = cur;
            } else {
                if (key < parent->_key) parent->left = cur;
                else parent->right = cur;
            }
            return cur->_val;
        }

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

    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;
        }

        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、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单的数据存储需求。