C++ 二叉搜索树

由于二叉搜索树涉及到节点资源的开辟、拷贝、删除，所以这里我们需要自己写拷贝构造、赋值重载、析构函数。默认构造一般不满足我们的需求，所以看情况是否要写。而这里由于我们需要写拷贝构造（一种特殊的默认构造），所以这里一定要手写默认规则（可以缺省值）。

2.1.2.1 二叉搜索树的基本结构

template<class K> class BSTree {
    typedef BSTreeNode<K> Node;
private:
    Node* _root = nullptr;
};

2.1.2.2 二叉搜索树的默认构造

// 默认函数两种方法
// 方法 1 - 前面定义有缺省值 /*BSTree() { }*/
// 方法二
BSTree() = default;

2.1.2.3 二叉搜索树的拷贝构造

前面的链式结构的树的拷贝需要递归完成（即使用了递归），所以访问私有成员（在类外面调用该函数会出错）。而这个函数的实现过程仅供内部使用，所以这里应该定义一个私有函数，在定义一个公有函数来调用对应的私有函数。

public:
    // 拷贝构造
    BSTree(const BSTree<K>& t) {
        _root = Copy(t._root);
    }
private:
    Node* Copy(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* copy = new Node(root->_key); // 修复：深拷贝创建新节点
        copy->_left = Copy(root->_left);
        copy->_right = Copy(root->_right);
        return copy;
    }

2.1.2.4 二叉搜索树的赋值重载

public:
    // 赋值重载
    BSTree<K>& operator=(const BSTree<K>& t) {
        swap(_root, t._root);
        return *this;
    }

2.1.2.5 二叉搜索树的析构

public:
    // 析构函数
    ~BSTree() {
        Destroy(_root);
    }
private:
    void Destroy(Node* root) {
        if (root == nullptr) {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

2.2 二叉搜索树的插入

2.2.1 二叉搜索树的插入整体思路

1. 树为空，则直接新增结点，赋值给 root 指针。
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 注意：如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）【这里我们不讲，一般不用】

2.2.2 二叉搜索树的插入代码实现

// 1 插入数据 - 不支持插入已有数据
bool Insert(const K& key) {
    // 树为空，则直接新增结点，赋值给 root 指针
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }
    // 由于二叉搜索树的特征，所以要先找到插入的位置；
    // 由于要改变节点直接之间的指向关系，所以要定义两个变量
    // 一个变量用于遍历，一个用于储存要插入位置的父节点，方便改变节点之间的指向关系
    Node* cur = _root; // 用于遍历
    Node* parent = nullptr; // 用于储存要插入位置的父节点
    while (cur) {
        if (cur->_key < key) // 插入值比当前结点大往右走
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key) // 插入值比当前结点小往左走
        {
            parent = cur;
            cur = cur->_left;
        }
        else // 找到插入位置
        {
            return false;
        }
    }
    cur = new Node(key);
    // 要判断插入的是当前节点的左子节点还是右子节点
    if (parent->_key < key) {
        parent->_right = cur;
    }
    else {
        parent->_left = cur;
    }
    return true;
}

2.3 二叉搜索树的查找

2.3.1 二叉搜索树的查找整体思路

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

2.3.2 二叉搜索树的查找代码实现

// 2 查找数据
bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key) // 从根开始比较，查找 x，x 比根的值大则往右边查找
        {
            cur = cur->_right;
        }
        else if (cur->_key > key) // x 比根值小则往左边查找
        {
            cur = cur->_left;
        }
        else {
            return true; // 找到返回
        }
    }
    return false; // 走到到空，还没找到，这个值不存在。
}

2.4 二叉搜索树的删除（最难）

2.4.1 二叉搜索树删除的整体思路

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

• 情况一：问题：要删除结点 x 左右孩子均为空。解决办法：把 x 结点的父亲对应孩子指针指向空，直接删除 x 结点。
• 情况二：问题：要删除的结点 x 左孩子位空，右孩子结点不为空。解决办法：把 x 结点的父亲对应孩子指针指向 x 的右孩子，在直接删除 x 结点。
• 情况三：问题：要删除的结点 x 右孩子位空，左孩子结点不为空。解决办法：把 x 结点的父亲对应孩子指针指向 x 的左孩子，在直接删除 x 结点。
• 情况四（最复杂）：问题：要删除的结点 x 左右孩子结点均不为空。解决办法：无法直接删除 x 结点，因为 x 的两个孩子无处安放，只能用替换法删除。找 x 左子树的值最大结点 R（最右结点）或者 x 右子树的值最小结点 R（最左结点）替代 x，因为这两个结点中任意一个，放到 x 的位置，都满足二叉搜索树的规则。替代 x 的意思就是 x 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

总结：情况 1 可以当成 2 或者 3 处理，效果是一样的。

2.4.2 二叉搜索树删除的代码实现

// 删除数据
bool Erase(const K& key) {
    // 先找到要删除的节点的位置
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        }
        else {
            // 找到了，准备删除数据
            // 分为三种情况
            // 1 左孩子为空，左右孩子为空可以一起处理
            if (cur->_left == nullptr) {
                if (cur == _root) // 要删除的节点就是根节点，直接改变根节点的指向即可
                {
                    _root = cur->_right;
                }
                else {
                    // 要删除的节点不是根节点，要判断要删除的节点
                    // 是其父节点的左孩子还是右孩子，方便改变节点直接的指向关系
                    if (cur == parent->_left) {
                        parent->_left = cur->_right;
                    }
                    else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur; // 删除要删除的结点
            }
            else if (cur->_right == nullptr) // 右孩子为空
            {
                if (cur == _root) // 要删除的节点就是根节点，直接改变根节点的指向即可
                {
                    _root = cur->_left;
                }
                else {
                    // 要删除的节点不是根节点，要判断要删除的节点
                    // 是其父节点的左孩子还是右孩子，方便改变节点直接的指向关系
                    if (cur == parent->_left) {
                        parent->_left = cur->_left;
                    }
                    else {
                        parent->_right = cur->_left;
                    }
                }
                delete cur; // 删除要删除的结点
            }
            else {// 有两孩子 - 两种处理方法这里使用找右子数中最小值节点
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                // 找到右子树中值最小的节点
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                swap(minRight->_key, pMinRight->_key);
                if (pMinRight->_left == minRight) {
                    pMinRight->_left = minRight->_right;
                }
                else {
                    pMinRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    return false; // 未找到
}

2.5 二叉搜索树的排序（使用中序遍历）

由于使用到了中序遍历即使用了递归，所以访问私有成员（在类外面调用该函数会出错），所以这里应该定义一个私有函数，在定义一个公有函数来调用对应的私有函数。

代码实现：

// 排序 - 利用其特点这里可以使用中序遍历
// 由于使用到了中序遍历即使用了递归，所以访问私有成员（在类外面调用该函数回出错）
void InOrder() // 定义一个公有函数来调用对应的私有函数
{
    _InOrder(_root);
    cout << endl;
}
private:
void _InOrder(Node* root) // 定义一个私有函数
{
    if (root == nullptr) {
        return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

三、二叉搜索树增删查排序的整体代码实现

namespace key {
template<class K> struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;
    BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) { }
};

template<class K> class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 默认函数
    /*BSTree() { }*/
    BSTree() = default;
    // 2 拷贝构造
    BSTree(const BSTree<K>& t) {
        _root = Copy(t._root);
    }
    // 赋值重载
    BSTree<K>& operator=(const BSTree<K>& t) {
        swap(_root, t._root);
        return *this;
    }
    // 析构函数
    ~BSTree() {
        Destroy(_root);
    }
    // 1 插入数据 - 不支持插入已有数据
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        Node* cur = _root; // 用于遍历
        Node* parent = nullptr; // 用于储存要插入位置的父节点
        while (cur) {
            if (cur->_key < key) // 插入值比当前结点大往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) // 插入值比当前结点小往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else // 找到插入位置
            {
                return false;
            }
        }
        cur = new Node(key);
        // 要判断插入的是当前节点的左子节点还是右子节点
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }
    // 2 查找数据
    bool Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) // 从根开始比较，查找 x，x 比根的值大则往右边查找
            {
                cur = cur->_right;
            }
            else if (cur->_key > key) // x 比根值小则往左边查找
            {
                cur = cur->_left;
            }
            else {
                return true; // 找到返回
            }
        }
        return false; // 走到到空，还没找到，这个值不存在。
    }
    // 删除数据
    bool Erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                // 找到了，准备删除数据
                // 分为三种情况
                // 1 左孩子为空
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    }
                    else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_right;
                        }
                        else {
                            parent->_right = cur->_right;
                        }
                    }
                    delete cur;
                }
                else if (cur->_right == nullptr) // 右孩子为空
                {
                    if (cur == _root) {
                        _root = cur->_left;
                    }
                    else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_left;
                        }
                        else {
                            parent->_right = cur->_left;
                        }
                    }
                    delete cur;
                }
                else {// 有两孩子 - 两种处理方法这里使用找右子数中最小值节点
                    Node* pMinRight = cur;
                    Node* minRight = cur->_right;
                    // 找到右子树中值最小的节点
                    while (minRight->_left) {
                        pMinRight = minRight;
                        minRight = minRight->_left;
                    }
                    swap(minRight->_key, pMinRight->_key);
                    if (pMinRight->_left == minRight) {
                        pMinRight->_left = minRight->_right;
                    }
                    else {
                        pMinRight->_right = minRight->_right;
                    }
                    delete minRight;
                }
                return true;
            }
        }
        return false;
    }
    // 排序 - 利用其特点这里可以使用中序遍历
    // 由于使用到了中序遍历即使用了递归，所以访问私有成员（在类外面调用该函数回出错）
    void InOrder() // 定义一个公有函数来调用对应的私有函数
    {
        _InOrder(_root);
        cout << endl;
    }
private:
    void _InOrder(Node* root) // 定义一个私有函数
    {
        if (root == nullptr) {
            return;
        }
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }
    void Destroy(Node* root) {
        if (root == nullptr) {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    Node* Copy(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* copy = new Node(root->_key);
        copy->_left = Copy(root->_left);
        copy->_right = Copy(root->_right);
        return copy;
    }
private:
    Node* _root = nullptr;
};
}

四、Key 和 (Key, Value) 结构

4.1 Key 和 (Key, Value) 结构搜索二叉树的定义

上面我们实现的二叉搜索树，节点中只储存了一个值 (Key)，Key 称为关键码，关键码即为需要搜索到的值，使用这种搜索二叉树只需要判断 Key 是否存在。Key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 Key 破坏搜索树结构了（性质）。

这里还有一种搜索二叉树：(Key, Value) 结构的二叉搜索树：

每一个关键码还是 Key，但是每一个关键码都有与之对应的值 Value，Value 可以任意类型对象。所以树的结构中（结点）除了需要存储 Key 还要存储对应的 Value，注意增/删/查还是以 Key 为关键字在二叉搜索树的规则下操作，这里不支持修改 Key，支持修改 Value。

4.2 (Key, Value) 结构搜索二叉树的实现

namespace key_value {
template<class K, class V> struct BSTreeNode {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key; // 中文
    V _value; // 英文
    BSTreeNode(const K& key, const V& value) :_left(nullptr), _right(nullptr), _key(key), _value(value) {}
};

template<class K, class V> class BSTree {
    typedef BSTreeNode<K, V> Node;
public:
    // 强制生成
    BSTree() = default;
    // 拷贝构造
    BSTree(const BSTree<K, V>& t) {
        _root = Copy(t._root);
    }
    // 赋值重载
    BSTree<K, V>& operator=(const BSTree<K, V>& t) {
        swap(_root, t._root);
        return *this;
    }
    ~BSTree() {
        Destory(_root);
        _root = nullptr;
    }
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;
            }
        }
        cur = new Node(key, value);
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                cur = cur->_left;
            }
            else {
                return cur;
            }
        }
        return nullptr;
    }
    bool Erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                // 准备删除
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    }
                    else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_right;
                        }
                        else {
                            parent->_right = cur->_right;
                        }
                    }
                    delete cur;
                }
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    }
                    else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_left;
                        }
                        else {
                            parent->_right = cur->_left;
                        }
                    }
                    delete cur;
                }
                else // 两个孩子
                {
                    Node* pMinRight = cur;
                    Node* minRight = cur->_right;
                    while (minRight->_left) {
                        pMinRight = minRight;
                        minRight = minRight->_left;
                    }
                    swap(cur->_key, minRight->_key);
                    if (pMinRight->_left == minRight) {
                        pMinRight->_left = minRight->_right;
                    }
                    else {
                        pMinRight->_right = minRight->_right;
                    }
                    delete minRight;
                }
                return true;
            }
        }
        return false;
    }
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
private:
    void _InOrder(Node* root) {
        if (root == nullptr) {
            return;
        }
        _InOrder(root->_left);
        cout << _key << ":" << _value << endl;
        _InOrder(root->_right);
    }
    void Destory(Node* root) {
        if (root == nullptr) {
            return;
        }
        Destory(root->_left);
        Destory(root->_right);
        delete root;
    }
    Node* Copy(Node* root) {
        if (root == nullptr) return nullptr;
        Node* copy = new Node(root->_key, root->_value);
        copy->_left = Copy(root->_left);
        copy->_right = Copy(root->_right);
        return copy;
    }
private:
    Node* _root = nullptr;
};
}

五、二叉搜索树 Key 和 Key/Value 使用场景

5.1 二叉搜索树 Key 使用场景

• 场景 1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
• 场景 2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

5.2 二叉搜索树 Key/Value 使用场景

• 场景 1：简单中英互译字典，树的结构中（结点）存储 Key（英文）和 Value（中文），搜索时输入英文，则同时查找到了英文对应的中文。
• 场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
• 场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则 ++ 单词对应的次数。