C++ 数据结构：二叉搜索树增删查改实现

类结构

template<class K> class BSTree {
    using Node = BSTNode<K>;
public:
    // ...
private:
    Node* _root = nullptr; // 成员变量
};

说明： 下面实现过程中默认为值不重复的情形。

3.1、插入

思路：

1. 树为空，则直接新增结点，赋值给 root 指针。
2. 树不空，按二叉搜索树性质，用 cur 指针遍历二叉搜索树，用一个 parent 指针记下父亲节点，要插入值 key 比当前节点大往右走，插入值比当前结点小往左走，直到找到空位置，插入新结点。
3. 确定要插入的节点在父亲节点的左边还是右边，即当 _key < parent->_key 则将新节点插入到 parent 的左边，反之则插入到右边。
4. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。但是，要确定相同的值要么都往左边走或者都往右边走。

//-------------------------------代码实现-------------------------------------------------
bool Insert(const K& key) {
    Node* node = new Node(key);
    // 处理空树
    if (_root == nullptr) {
        _root = node;
        return true;
    }
    Node* parent = nullptr; // 记下父亲节点的指针，方便最后连接新节点
    Node* cur = _root; // 遍历二叉搜索树
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 已存在
        }
    }
    // 确定新节点最后的插入位置
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

3.2、中序遍历

根据二叉搜索树的特性，其中序遍历的结果恰好为一个有序序列（升序）。

为了解决函数调用传参的问题，因为中序遍历的参数 _root 是成员变量，在类外面调用无法访问成员变量而无法传参，所以，用子函数方式来实现。

// 中序遍历
void MidOrder() {
    _MidOrder(_root);
}
// 子函数
void _MidOrder(Node* _root) {
    if (_root == nullptr) {
        return;
    }
    _MidOrder(_root->_left);
    cout << _root->_key << " ";
    _MidOrder(_root->_right);
}

3.3、查找

思路：

1. 从根开始比较，查找 val，val 比根的值大则往右边走查找，val 比根值小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在，返回 false。
3. 如果不支持插入相等的值，找到 x 即可返回。

bool 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 {
            return true;
        }
    }
    return false;
}

3.4、删除

思路：

1. 要删除节点 N 的位置有四种情况： a. 结点 N 左右孩子均为空； b. 结点 N 左孩子为空，右孩子结点不为空； c. 结点 N 右孩子位空，左孩子结点不为空； d. 结点 N 左右孩子结点均不为空。
2. 对于左右孩子都为空的情况，我们可以将其放在左孩子为空和右孩子为空的情况中处理。即将上面四种情况重新分为：左为空；右为空；左右都不为空三种。
3. 对于左为空，要删除节点 N 可能为根结点，则让该节点的右节点作为新的根结点；或者是父节点的左节点，则让父节点的 _left 指针指向节点 N 的右边；或者父节点的右节点，则让父节点的 _right 指针指向节点 N 的左边，右为空类似。

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

bool Erase(const K& val) {
    Node* cur = _root;
    Node* parent = nullptr;
    // 遍历先找到 N 节点
    while (cur) {
        if (val < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            // 找到 N 节点
            // 左为空
            if (cur->_left == nullptr) {
                // 根结点
                if (_root == cur) {
                    _root = _root->_right;
                } else if (parent->_left == cur) {
                    parent->_left = cur->_right;
                } else {
                    parent->_right = cur->_right;
                }
                delete cur;
            }
            // 右为空
            else if (cur->_right == nullptr) {
                // 根结点
                if (_root == cur) {
                    _root = _root->_left;
                } else if (parent->_right == cur) {
                    parent->_right = cur->_left;
                } else {
                    parent->_left = cur->_left;
                }
                delete cur;
            }
            // 左右孩子均不为空
            else {
                Node* replaceParent = cur;
                Node* replace = cur->_right; // 找右子树中最小值的节点 R
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 替换节点 N 与节点 R 的值
                cur->_key = replace->_key;
                if (replace == replaceParent->_left) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;
}

4、key_value 类型二叉搜索树的实现

为什么还有 key_value 类型二叉搜索树呢？对于 map/multimap 容器，映射（Maps）是一种关联容器，它按照特定顺序存储由'键值（key value）'和'映射值（mapped value）'组合而成的元素。

节点结构

与 key 类型相比，只是多了个 _value。

template<class K, class V> struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
    BSTNode(const K& key = 0, const V& value = 0) :_key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

类结构

template<class K, class V> class BSTree {
    using Node = BSTNode<K, V>;
public:
    // ...
private:
    Node* _root = nullptr;
};

说明： 对于 key_value 类型我们实现一下其构造，析构等，除了插入操作与 key 类型有一点不同外，其他操作基本相同，所以我们不再重复解释。

4.1、构造函数

4.1.1 默认构造

// C++11 强制生成默认构造
BSTree() = default;

4.1.2 拷贝构造

// 拷贝构造（深拷贝）
BSTree(const BSTree& tree) {
    _root = copy(tree._root);
}
Node* copy(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    // 前序遍历（递归）
    Node* newroot = new Node(root->_key, root->_value);
    newroot->_left = copy(root->_left);
    newroot->_right = copy(root->_right);
    return newroot;
}

4.2、赋值重载

// 赋值重载 (现代写法)
BSTree& operator=(BSTree tree) {
    swap(_root, tree._root);
    return *this;
}

4.3、析构

// 析构函数
~BSTree() {
    Destroy(_root);
    _root = nullptr;
}
void Destroy(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 后序遍历：防止根结点被释放而找不到左右孩子节点
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
}

4.4、插入

bool Insert(const K& key, const V& value) {
    Node* node = new Node(key, value);
    if (_root == nullptr) {
        _root = node;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

总结

本文主要是简单实现了一下二叉搜索树的最基础的版本，与 set/multiset/map/multimap 底层的数据结构——平衡二叉搜索树有所不同，并没有过多关注底层实现细节，比如 insert，Find 返回值等。只是为了能够加深大家对二叉搜索树的理解，方便后面对平衡二叉树的理解。