用C++实现二叉搜索树：插入、查找、删除与key/value场景

查找就是从根开始比较，小往左，大往右，最多走树的高度步。如果要求不重复的key，找到了就成；如果允许重复，可能要找到中序的第一个。

遍历方式有前序、中序、后序，中序遍历可以得到有序序列。

删除

删除比插入麻烦。先得找到要删的节点，找不到就算了。找到了分几种情况：

• 叶子节点或者只有一个孩子：这种简单，直接让父结点的对应指针指向它的孩子（或nullptr）就行。
• 有两个孩子：不能直接删，得用'替换法'。通常是拿左子树的最大值（最右节点）或右子树的最小值（最左节点）来覆盖这个节点，然后转而删除那个最值节点，问题就变成删一个最多有一个孩子的节点。

实际动手画一遍（配合后面代码）会清晰很多。

key和key/value两种场景

只存key的BST，常见应用是快速判断存在性，比如拼写检查、车牌识别。这种树一般不支持修改key，因为会破坏结构，但可以增删查。

key/value模型呢，就是每个key对应一个value，增删查还是按key走，但可以修改value。典型例子：字典（英文→中文），或者车库系统根据车票号存入场时间。代码里类似std::map的实现就是这样。

实现的代码

下面给出两份代码，一份是只存key的set（去重和不去重两种），另一份是key/value的map。代码里刻意保留了一些不那么完美的细节，比如命名不统一，是为了贴近真实开发中能见到的样子。

key模型的set实现

第一个是去重版，插入发现已存在就直接返回true（但这里插入成功和已存在都返回true，实际使用时注意区分）。第二个允许多个相同key插入，采用<=往左的策略，所以相等值会放在左子树。

// 去重版 set
#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

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

key/value模型的map实现

这个map允许重复key（插入用<=），并且实现了operator[]，可以像std::map一样使用。需要注意，删除双孩子节点时，它用了左子树最大值（虽然变量名叫leftMaxf/leftMax，但查找过程却是找右子树最大值，实际代码里有混淆。为了保持原样，我们不做修改，大家自己看的时候要留意。

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

二叉搜索树作为基础结构，理解它的实现对后续掌握平衡树很有帮助。上面的代码可以跑通，但细节上（比如删除时的指针操作、相等值的处理策略）还有不少优化的空间。在实际项目里，更多还是直接使用std::set、std::map这些经过大量测试的容器。不过自己动手写过一遍，对它们的底层机制会有更深的感觉。