C++ 二叉搜索树详解：概念、实现与应用

强制生成默认构造 BSTree() = default

在上面完整的代码中，BSTree() 默认构造函数是通过以下代码定义的：

BSTree() = default;

= default 的作用：

• 生成默认构造函数：当我们写 BSTree() = default; 时，编译器会为类自动生成一个默认的构造函数。它的行为等价于一个空的用户定义构造函数，但由编译器自动完成。
• 为什么用 = default：显式告诉编译器生成默认构造函数，表示我们明确需要这个默认的构造行为。避免用户误以为我们忘记定义构造函数。保持代码简单，同时遵守编译器生成的高效实现。

为什么需要显式生成默认构造函数？

BSTree 类包含一个私有成员变量 _root：

Node* _root = nullptr;

• 原因 1: 明确默认构造需求 如果没有声明任何构造函数，编译器会自动生成默认构造函数，且会将 _root 初始化为 nullptr（因为你用了类内初始化 Node* _root = nullptr;）。但如果你显式定义了其他构造函数（比如拷贝构造、赋值重载），编译器将不再自动生成默认构造函数。为避免丢失默认构造函数的功能，就需要显式使用 = default;。
• 原因 2: 保持代码的可读性与语义 通过显式声明 BSTree() = default;，代码更直观地表明：'这个类的默认构造行为是由编译器生成的，我没有进行额外的修改。'

= default 和手动定义的区别

如果不使用 = default 而是手动定义默认构造函数：

BSTree():_root(nullptr){}

行为与 = default 等价，但显式手动定义不如 = default 简洁。

= default 的好处包括：

1. 让编译器自动生成，减少代码量和维护负担。
2. 避免意外错误，例如忘记初始化成员变量。

适用场景

使用 = default 常见于以下场景：

1. 需要默认构造函数，但有其他特殊构造函数：如果定义了其他构造函数（如拷贝构造、移动构造等），而仍需要默认构造函数，必须显式声明它。
2. 需要提高代码语义的清晰度：即使编译器会自动生成默认构造函数，显式 = default 更直观。

赋值运算符重载函数

BSTree<K>& operator=(const BSTree<K>& t) {
    swap(_root, t._root);
    return *this;
}
// 传统深拷贝写法。也很好
// BSTree<K>& operator =(const BSTree<K>& t) {
//     tree1 = tree2
//     if (this != &t) {
//         Destroy(_root); // 清空 tree1 树里的节点，树还在，但是空树
//         _root = Copy(t._root); // 把 tree2 里的节点深拷贝到 tree1
//     }
//     return *this; // 返回 tree1；
// }

赋值重载 swap 写法详解

这种写法很高效，节省资源，一定要掌握！！！

我们通过一个详细的例子来说明写法二（swap 方式）中的每一步，以及各个变量（如 this 和 t）的变化。

代码回顾

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    BSTree<K>& operator=(BSTree<K> t) {
        swap(_root, t._root);
        return *this;
    }
private:
    Node* _root = nullptr;
};

假设情景 假设有两个二叉搜索树对象 tree1 和 tree2，它们的树结构如下：

• tree1：树的根节点为 _root = 5。
• tree2：树的根节点为 _root = 10。

现在我们要将 tree1 赋值为 tree2，即 tree1 = tree2;。

初始状态

• tree1._root：指向 5 节点。
• tree2._root：指向 10 节点。

接下来我们逐步讲解赋值运算符 tree1 = tree2; 的执行过程。

第一步：函数调用时，创建临时副本 t

BSTree<K>& operator=(BSTree<K> t)

• 当 tree1 = tree2; 发生时，tree2 作为参数传递给 BSTree<K> t，因此会调用 复制构造函数，为 t 创建一个 tree2 的副本。
• 在此过程中，t._root 指向了 tree2 的根节点（即 10），但 t 是一个独立的对象，内存完全独立于 tree2。

变量状态：

• this：指向 tree1，this->_root = 5。
• t._root：指向 tree2 的副本，即根节点为 10。

第二步：执行 swap

swap(_root, t._root);

这里使用的是标准库中的 std::swap 函数。该函数的核心是交换两个对象的值，具体步骤如下：

1. 创建临时变量 temp：temp 保存 this->_root（即 tree1 的 _root），此时 temp = 5。
2. 将 t._root 赋给 this->_root：此时 this->_root 指向 t._root 的值（即 10），也就是 tree2 的根节点。
3. 将 temp 赋给 t._root：最后，t._root 变为 5，即之前 tree1 的根节点。

swap 操作结束后，tree1 和 t 的根节点已经交换。

变量状态：

• this->_root：现在指向 10，即 tree2 的根节点。
• t._root：现在指向 5，即 tree1 原来的根节点。

第三步：返回当前对象（链式调用支持）

return *this;

• operator= 函数返回当前对象，即 tree1，此时 tree1._root = 10。
• t 是传递进来的临时变量，会在函数结束时自动销毁。由于 t._root 现在指向的是 5（即 tree1 原来的根节点），当 t 离开作用域时，其析构函数会被调用，自动释放 5 这个节点及其子树（如果有）。

最终结果

• tree1：现在拥有 tree2 的树结构，根节点为 10。
• tree2：原来的结构不变，仍然指向 10，但由于我们是通过副本 t 操作，tree2 本身不会受到影响。
• 旧的 tree1 的树（即以 5 为根的树）：在 t 的生命周期结束时，随着 t 的析构函数被调用，旧的 tree1 树被销毁。

关键点总结：

1. 临时副本：通过传值的方式，将 tree2 的副本传递给 t，t 独立于 tree2。
2. 高效的 swap：swap 交换了 tree1 和 t 的根节点指针，而不是深拷贝整个树，效率更高。
3. 资源管理：由于 t 是传入的临时变量，赋值过程结束后 t 会被自动销毁，释放旧的 tree1 的内存，避免了手动 Destroy 的麻烦。
4. 链式赋值：return *this 支持链式调用，如 tree1 = tree2 = tree3;。

这种 swap 的写法，简洁、高效，并且通过临时对象 t 自动管理资源，是现代 C++ 中推荐的写法。

传统深拷贝写法中为什么需要 return *this?

为什么返回 *this？即使 tree1 的内存已被释放？

1. 释放的只是原树的节点，树本身仍然存在 调用 Destroy(_root) 时，仅释放了 tree1 原有的节点内存，但 tree1 本身（即当前对象）仍然存在。_root 只是一个指针成员变量，而非整个 tree1 对象的内存。 例如：

   • 如果 tree1 原本有数据，它们会被 Destroy 清空，变成一个空树（_root == nullptr）。
   • 然后通过 Copy(t._root)，重新构造 tree1 的数据结构，使其变得与 tree2 相同。 最终，tree1 并没有被销毁，而是被重建。

2. 返回值的意义：支持链式赋值 返回 *this 是赋值运算符的标准设计，用于支持链式赋值。链式赋值允许连续的赋值操作，如：

   BSTree<int> a, b, c; a = b = c;
   

   • 流程：
     1. b = c 执行后，返回 b 的引用。
     2. 然后将 b 的引用作为参数传递给 a = b。 如果不返回 *this，链式赋值将无法工作。

3. 为什么不是返回销毁的内容？ Destroy(_root) 只是清空了树的原有数据，tree1 的对象本身还存在。返回 *this 是返回当前对象的引用，表示赋值操作完成，当前对象的状态被更新为目标对象的状态。 例如：

   BSTree<int> tree1, tree2; // 假设 tree1 有旧的节点，tree2 是目标树
   tree1 = tree2;
   

   在 tree1 = tree2 过程中：

   1. 清空 tree1 的原节点，但 tree1 本身还在。
   2. 将 tree2 的数据复制到 tree1。
   3. 返回 tree1 的引用，表示 tree1 现在是 tree2 的深拷贝。

4. 示意图说明 初始状态：

   • tree1：包含若干节点，_root 指向一棵树。
   • tree2：包含若干节点，_root 指向另一棵树。 操作后：
   • Destroy(_root) 释放 tree1 的所有节点，_root 变成 nullptr。
   • Copy(t._root) 创建一棵新的树，将 tree2 的节点深拷贝到 tree1。
   • tree1 现在与 tree2 的内容一致。 链式赋值：

   a = b = c;
   

   等效于：

   b = c; // b 变为 c 的拷贝
   a = b; // a 变为 b 的拷贝 (实际上 a 也变为 c 的拷贝)
   

   每次赋值后，*this 返回当前对象的引用供下一个操作使用。

析构函数 ~BSTree()

~BSTree() { Destroy(_root); }

中序遍历 InOrder()

void InOrder() {
    _InOrder(_root);
    cout << endl;
}

void _InOrder(Node* root) {
    if (root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

InOrder() 为何这样设计？

InOrder() 函数设计的目的是为了封装实现细节，让用户只需调用接口函数即可完成对二叉树的中序遍历，而不必了解树的内部数据结构。这种设计的优势在于以下几点：

1. 隐藏内部实现细节 在代码中，InOrder() 调用了一个私有的辅助递归函数 _InOrder(Node* root)：

   void InOrder() { _InOrder(_root); cout << endl; }
   

   用户只需要调用 tree.InOrder() 就可以触发中序遍历，输出节点值，而不需要知道：

   • 树的节点结构 (BSTreeNode<K> 的定义)。
   • 遍历的逻辑细节。
   • 遍历需要从根节点 _root 开始。 这种封装遵循了面向对象编程中的封装原则，屏蔽了用户不需要知道的复杂实现。

2. 简化用户操作 对于用户来说，他们关心的是功能，而非具体实现。用户只需要：

   tree.InOrder();
   

   而不需要自己写出复杂的递归逻辑去遍历树，例如：

   void InOrderManual(BSTreeNode<int>* root) {
       if (!root) return;
       InOrderManual(root->_left);
       cout << root->_key << " ";
       InOrderManual(root->_right);
   }
   

   封装之后，用户无需处理树的节点指针，也不用理解递归过程，降低了使用门槛。

3. 降低错误概率 让用户直接访问和操作树的内部结构（如 _root 指针）可能导致以下问题：

   • 不小心破坏了树的完整性（如误修改了 _root 或其他节点的子指针）。
   • 错误遍历逻辑：用户可能误用树的节点指针，造成逻辑混乱。 通过只暴露 InOrder() 方法，用户无法直接接触内部的 _root 或树节点，减少了误操作的风险。

4. 增强代码的可维护性和扩展性 如果以后需要修改中序遍历的实现（例如加入线程或并行化），我们只需改动私有的 _InOrder() 方法，而无需修改 InOrder() 或影响用户代码。 用户调用 InOrder() 的方式保持不变，代码改动对外透明。这种设计符合模块化设计的思想。

三、查找、插入

1. 查找

• 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
• 最多查找高度次，走到到空，还没找到，这个值不存在

另外需要注意的是： ① 最大元素一定是在树的最右分枝的端结点上。 ② 最小元素一定是在树的最左分枝的端结点上。

// find 函数。用 k，关键字的意思
bool Find(const K& key) {
    Node* cur = _root; // 从根节点开始查找
    // _root 是存储在 BSTree 类中的成员变量，它指向树的根节点。通过这个指针，你可以访问整个树。
    while (cur) {
        if (cur->_key < key) {
            cur = cur->_right;
        } else if (cur->_key > key) {
            cur = cur->_left;
        } else {
            return true;
        }
    }
    return false;
}

2. 插入

1. 特殊情况处理： 如果树是空的（即 root == nullptr），那么直接把要插入的元素作为根节点插入即可。
2. 基本规则：
   • 因为是二叉搜索树，所以不能插入重复元素。
   • 插入的元素一定会成为某个叶子节点（即没有子节点的位置）。
3. 具体操作思路：
   • 从根节点开始定义一个指针变量 cur 来遍历树，初始时 cur = root。
   • 如果插入的值比当前节点的值小，就向左子树移动；如果插入的值比当前节点的值大，就向右子树移动。
   • 在移动时，还需要定义另一个变量 parent 记录当前节点的'父节点'，也就是 cur 移动前的位置。这样，当找到一个空位时，知道应该插入在 parent 的左子树还是右子树。
4. 最后一步：
   • 当 cur 移动到空位置（即 cur == nullptr）时，根据 parent 的位置决定插入新元素：
     • 如果插入的值小于 parent 的值，插入到 parent 的左子树；
     • 如果插入的值大于 parent 的值，插入到 parent 的右子树。
   • 这样就完成了插入操作。

// 插入
// 类的成员函数（如 Insert）中，成员变量 (_root) 是直接可见的，无需通过参数传递。
// 这是因为成员函数默认会操作类的当前实例。
bool Insert(const K& key) {
    // Node* cur = new Node(key); // 这里的 new 后面加什么还是不太清楚。New 的用法忘了，及时复习。
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }
    // 关键：保存父节点
    Node* parent = nullptr;
    // Node* cur = root; // 错误写法
    Node* cur = _root; // 不是 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; // 重复了，树里面已经有了 key。插入不了。
        }
    }
    // 此时 cur 为空，为待插入的位置
    // cur = new Node(key); // 这句又忘了
    // if (parent->_right == nullptr) {
    //     parent->_left = cur;
    // }
    // else {
    //     parent->_left = cur;
    // }
    // 上面的写法是错的。
    // 假如插入 16，此时 parent 为 14，cur 为空，应该判断 key 与 parent 的大小关系，而不是 14 左右子树是否为空。
    // 按照错误逻辑，16 插入到 14 的左子树了
    // 8
    // 3 10
    // 1 6 14
    // cur = new Node(key);
    if (parent->_key < key) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    return true;
}

四、删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点

看起来有待删除节点有 4 种情况，实际情况 a 可以与情况 b 或者 c 合并起来，因此真正的删除过程如下：

• 情况 b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除

• 情况 c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

• 情况 d：在它的右子树中寻找中序下的第一个结点 (关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

• a,b,c 情况——直接删除 将待删除节点的父节点指向待删除节点的孩子节点

• d 情况（要删除的结点有左、右孩子结点） ——替换法删除 先假删除根节点 8.

我们的目标依然是要保证删除结点 8 后，再次中序遍历它，仍不改变其升序的排列方式。那么我们只有用 7 或者 10 来替换 8 原来的位置。

用 7 替换待删除节点

用 10 替换待删除节点

为什么是 7 或者 10 来替换 8 的位置？ 显然，7 与 10 是挨着 8 的，如果用其他元素替换则会打扰其顺序。那 7 和 10 怎么在二叉排序树中找到呢？ 显然，7 在 8 左子树的'最右边'，10 在 8 右子树的'最左边'。根据二叉排序树的插入方式，比 8 小的元素一定在左子树，而我们又要找到比 8 小的最大的数，这样才能保证他们俩在顺序上是挨着的，所以它又会在 8 的左子树的最右边。同理也可以找到 10.

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 {
                    /* 10
                       / \ 
                      5  15
                     / \ 
                    3   7 */
                    // 假如删除，15 是 10 的右，把 15 的右 (空),给 10 的右。
                    // 由此可知：左子节点为空 这部分代码可以解决叶子节点的情况
                    if (cur == parent->_right) {
                        parent->_right = cur->_right;
                    } else {
                        parent->_left = cur->_right;
                    }
                }
                delete cur;
                return true;
            }
            // 右子节点为空:
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (cur == parent->_right) {
                        parent->_right = cur->_left;
                    } else {
                        parent->_left = cur->_left;
                    }
                }
                delete cur;
                return true;
            }
            // 左右子节点均不为空:
            else {
                // 替换法
                Node* rightMinParent = cur;
                Node* rightMin = cur->_right;
                while (rightMin->_left) {
                    rightMinParent = rightMin;
                    rightMin = rightMin->_left;
                }
                cur->_key = rightMin->_key;
                if (rightMin == rightMinParent->_left)
                    rightMinParent->_left = rightMin->_right;
                else
                    rightMinParent->_right = rightMin->_right;
                delete rightMin;
                return true;
            }
        }
    }
    return false;
}

下面一张图也可以帮助理解。

五、性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其平均比较次数为：$log_2 N$

最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其平均比较次数为：$\frac{N}{2}$

六、应用——KV 模型

1. K 模型：K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。 比如：给一个单词 word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为 key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV 模型：每一个关键码 key，都有与之对应的值 Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
3. 统计次数

// 统计词语出现的次数
string strs[] = {"苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果"};
// 统计水果出现的次数
BSTree<string, int> countTree;
for (auto str : strs) {
    auto ret = countTree.Find(str);
    if (ret == NULL) {
        countTree.Insert(str, 1);
    } else {
        ret->_value++;
    }
}
countTree.InOrder();

<K,V>模型代码

namespace key_value {
// ======================
// 二叉搜索树节点结构体
// ======================
template<class K, class V>
struct BSTreeNode {
    // 为了简化书写，用 Node 表示 BSTreeNode<K, V> 类型本身
    typedef BSTreeNode<K, V> Node;
    Node* _left; // 指向左子节点
    Node* _right; // 指向右子节点
    K _key; // 节点存储的键
    V _value; // 节点存储的值
    
    // 构造函数，用来初始化节点的 key 和 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() : _root(nullptr) {}
    
    // 向二叉搜索树中插入一个键值对 (key, value)
    // 返回值：如果插入成功返回 true，如果插入失败 (已存在相同 key) 返回 false
    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) {
            // 若当前节点 key 小于要插入的 key，则往右子树查找
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            // 若当前节点 key 大于要插入的 key，则往左子树查找
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                // 发现已有相同 key，插入失败
                return false;
            }
        }
        // 创建新节点
        cur = new Node(key, value);
        // 判断要插入到 parent 的左子树还是右子树
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }
    
    // 查找给定 key 对应的节点，返回指向该节点的指针，如果不存在则返回 nullptr
    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 {
                // 找到 key
                return cur;
            }
        }
        // 未找到 key
        return nullptr;
    }
    
    // 从二叉搜索树中删除 key 对应的节点，成功返回 true，失败返回 false
    bool Erase(const K& key) {
        Node* parent = nullptr; // 记录要删除节点的父节点
        Node* cur = _root; // 从根节点开始查找
        // 1. 先找到要删除的节点 cur 及其父节点 parent
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                // 找到了要删除的节点
                // 2. 根据 cur 是否存在子树分情况处理
                // a) cur 没有左子树
                if (cur->_left == nullptr) {
                    // 如果 cur 是根节点，则直接将根设置为右子树
                    if (cur == _root) {
                        _root = cur->_right;
                    } else {
                        // 如果 cur 不是根节点，则根据 parent 判断
                        // cur 是 parent 的左子树还是右子树
                        if (cur == parent->_right) {
                            parent->_right = cur->_right;
                        } else {
                            parent->_left = cur->_right;
                        }
                    }
                    delete cur;
                    return true;
                }
                // b) cur 没有右子树
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    } else {
                        if (cur == parent->_right) {
                            parent->_right = cur->_left;
                        } else {
                            parent->_left = cur->_left;
                        }
                    }
                    delete cur;
                    return true;
                }
                // c) cur 既有左子树又有右子树
                else {
                    // 使用替换法：找到 cur 的右子树中的最小值节点替换掉 cur
                    Node* rightMinParent = cur;
                    Node* rightMin = cur->_right;
                    // 在右子树中一直往左走，找到最小值节点
                    while (rightMin->_left) {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }
                    // 用最小值节点替换当前节点
                    cur->_key = rightMin->_key;
                    cur->_value = rightMin->_value;
                    // 将最小值节点删除
                    if (rightMin == rightMinParent->_left)
                        rightMinParent->_left = rightMin->_right;
                    else
                        rightMinParent->_right = rightMin->_right;
                    delete rightMin;
                    return true;
                }
            }
        }
        // 没有找到要删除的 key
        return false;
    }
    
    // 中序遍历：从小到大打印 key
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
private:
    // 辅助函数：中序遍历
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }
private:
    Node* _root; // 指向二叉搜索树的根节点
};
}

七、完整代码

template<class K>
// 树节点的结构体
struct BSTreeNode {
    typedef BSTreeNode<K> Node; // 千万别少了这句！！！！！！
    Node* _left;
    Node* _right;
    K _key;
    
    BSTreeNode(const K& key) // 这里是 K 是大写，一定要注意，改了好多
        : _left(nullptr), _right(nullptr), _key(key) {}
};

template<class K>
// 二叉搜索树这个类
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 默认构造
    BSTree() = default;
    
    // 拷贝构造
    BSTree(const BSTree<K>& t) { _root = Copy(t._root); }
    
    // 赋值重载
    // 完整的函数名每次忘记怎么写
    // BSTree<K>&：返回值类型是对当前对象的引用，以便支持链式赋值（a = b = c; ）。
    // operator=：定义赋值运算符。
    // const BSTree<K>& t：参数类型是一个 const 引用，表示要赋值的对象不应被修改。
    // 使用 swap 交换资源
    BSTree<K>& operator=(const BSTree<K>& t) {
        swap(_root, t._root);
        return *this;
    }
    
    // 传统深拷贝写法。也很好（代码详解在语雀）
    // BSTree<K>& operator =(const BSTree<K>& t) {
    //     tree1 = tree2
    //     if (this != &t) {
    //         Destroy(_root); // 清空 tree1 树里的节点，树还在，但是空树
    //         _root = Copy(t._root); // 把 tree2 里的节点深拷贝到 tree1
    //     }
    //     return *this; // 返回 tree1；
    // }
    
    // 析构
    ~BSTree() { Destroy(_root); }
    
    // 插入
    // 类的成员函数（如 Insert）中，成员变量 (_root) 是直接可见的，无需通过参数传递。这是因为成员函数默认会操作类的当前实例。
    bool Insert(const K& key) {
        // Node* cur = new Node(key); // 这里的 new 后面加什么还是不太清楚。New 的用法忘了
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        // 关键：保存父节点
        Node* parent = nullptr;
        // Node* cur = root; // Node* cur = root; 错误写法
        Node* cur = _root; // 不是 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; // 重复了，树里面已经有了 key。插入不了。
            }
        }
        // 此时 cur 为空，为待插入的位置
        // cur = new Node(key); // 这句又忘了
        // if (parent->_right == nullptr) {
        //     parent->_left = cur;
        // }
        // else {
        //     parent->_left = cur;
        // }
        // 上面的写法是错的。
        // 假如插入 16，此时 parent 为 14，cur 为空，应该判断 key 与 parent 的大小关系，而不是 14 左右子树是否为空。
        // 按照错误逻辑，16 插入到 14 的左子树了
        // 8
        // 3 10
        // 1 6 14
        // cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }
    
    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 {
                        /* 10
                           / \ 
                          5  15
                         / \ 
                        3   7 */
                        // 假如删除，15 是 10 的右，把 15 的右 (空),给 10 的右。
                        // 由此可知：左子节点为空 这部分代码可以解决叶子节点的情况
                        if (cur == parent->_right) {
                            parent->_right = cur->_right;
                        } else {
                            parent->_left = cur->_right;
                        }
                    }
                    delete cur;
                    return true;
                }
                // 右子节点为空:
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    } else {
                        if (cur == parent->_right) {
                            parent->_right = cur->_left;
                        } else {
                            parent->_left = cur->_left;
                        }
                    }
                    delete cur;
                    return true;
                }
                // 左右子节点均不为空:
                else {
                    // 替换法
                    Node* rightMinParent = cur;
                    Node* rightMin = cur->_right;
                    while (rightMin->_left) {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }
                    cur->_key = rightMin->_key;
                    if (rightMin == rightMinParent->_left)
                        rightMinParent->_left = rightMin->_right;
                    else
                        rightMinParent->_right = rightMin->_right;
                    delete rightMin;
                    return true;
                }
            }
        }
        return false;
    }
    
    // find 函数。用 k，关键字的意思
    bool Find(const K& key) {
        Node* cur = _root; // 从根节点开始查找
        // Node* cur = nullptr; // 为什么不行？
        // _root 是存储在 BSTree 类中的成员变量，它指向树的根节点。通过这个指针，你可以访问整个树。
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            } else if (cur->_key > key) {
                cur = cur->_left;
            } else {
                return true;
            }
        }
        return false;
    }
    
    // 前序遍历
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    //------------------------------------------------------------------------------------------------------------------
    // 递归实现
    // 这样的设计通常是为了提供递归操作的接口，允许用户以更简单的方式调用递归函数。以下是这些函数的作用：
    // bool FindR(const K& key) // 递归查找键值是否存在于树中。
    // 实际上调用 _FindR 函数。
    bool FindR(const K& key) {
        return _FindR(_root, key);
    }
    
    // bool InsertR(const K& key) // 递归插入一个键值到树中。
    // 实际上调用 _InsertR 函数。
    bool InsertR(const K& key) {
        return _InsertR(_root, key);
    }
    
    // bool EraseR(const K& key) // 递归删除一个键值。
    // 实际上调用 _EraseR 函数。
    bool EraseR(const K& key) {
        return _EraseR(_root, key);
    }
private:
    // 下面这部分隐藏，对外只提供 InOrder(). 用户只用关注接口不必关心细节。
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }
    
    Node* Copy(Node* root) {
        if (root == nullptr) return nullptr;
        Node* newRoot = new Node(root->_key);
        // 通过递归调用 Copy 函数来复制当前节点的左子节点。将返回的新左子树赋值给 newRoot 的左子节点
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }
    
    // 赋值运算重载的第二种写法要用到，析构函数也要用到
    void Destroy(Node* root) {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    
    // 这些函数的实现通常会更简洁，因为递归结构自然而然地处理了树的遍历：
    // bool _FindR(Node* root, const K& key) // 如果当前节点为空，则返回 false。
    // 根据键值与当前节点的比较，决定向左或向右子树递归查找。
    bool _FindR(Node* root, const K& key) {
        if (root == nullptr) return false;
        if (root->_key < key) return _FindR(root->_right, key);
        else if (root->_key > key) return _FindR(root->_left, key);
        else return true;
    }
    
    // bool _InsertR(Node*& root, const K& key) // 处理插入操作的递归逻辑。
    // 当找到合适的插入位置（当前节点为空）时，创建新节点。
    bool _Insert(Node*& root, const K& key) {
        if (root == nullptr) {
            // root->_key = key;
            root = new Node(key);
            return true;
        }
        if (root == nullptr) return false;
        if (root->_key < key) return _Insert(root->_right, key);
        else if (root->_key > key) return _Insert(root->_left, key);
        else {
            // 遇到值相等的，重复了 无法插入
            return false;
        }
    }
    
    // bool _EraseR(Node*& root, const K& key) // 处理删除操作的递归逻辑。
    // 逻辑与非递归的 _Erase 类似，但通过递归方式实现。
    bool _EraseR(Node*& root, const K& key) {
        // Node* parent = nullptr;
        // Node* cur = root;
        if (root == nullptr) return false;
        if (root->_key < key) return _EraseR(root->_right, key);
        else if (root->_key < key) return _EraseR(root->_left, key); // 注意此处应为 > key，原文可能有误，按逻辑修正
        else {
            // 注意，root 是上一节点的左指针 (右指针)
            // 保存当前待删除的节点。
            Node* del = root;
            // 如果左子树为空
            if (root->_right == nullptr) {
                root = root->_left;
            } else if (root->_left == nullptr) {
                root = root->_right;
            } else {
                // Node* rightMin = root->_right;
                // while (rightMin->_left) {
                //     rightMin = rightMin->_left;
                // }
                Node* rightMin = root->_right;
                while (rightMin->_left) {
                    rightMin = rightMin->_left;
                }
                swap(root, rightMin);
                return _EraseR(root->_right, key);
            }
            delete del;
            return true;
        }
    }
private:
    Node* _root = nullptr;
};

八、代码重难点

为什么有两处 template <class K>

在上面的代码中，出现两处 template <class K> 是因为它们的作用域和含义不同：

1. 第一处 template <class K>

   template<class K>
   struct BSTreeNode
   

   这一部分定义了一个模板结构体 BSTreeNode，它接受一个模板参数 K，用来指定二叉搜索树节点的关键字类型。模板参数 K 是用来描述节点内部的 _key 数据成员类型。

2. 第二处 template <class K>

   template<class K>
   class BSTree
   

   这里定义了一个模板类 BSTree，它也接受一个模板参数 K，用来指定树中的节点关键字类型。BSTree 内部的 Node 类型被定义为 BSTreeNode<K>，即二叉树节点的模板参数类型与 BSTree 的模板参数一致。

为什么需要两次 template <class K>？

这是因为 模板定义的作用域是独立的，模板参数的声明只能在其所属的模板中生效。也就是说：

• BSTreeNode<K> 的 K 和 BSTree<K> 的 K 是两个不同的模板参数，尽管它们名字相同，但彼此独立。
• 在 BSTree 中使用 BSTreeNode<K> 时，需要显式传递模板参数 K，以表明 BSTreeNode 的模板实例化。

如果模板类 BSTree 不单独定义自己的模板参数，而直接使用 BSTreeNode<K> 的模板参数，会导致代码难以扩展和维护。

bool 和 status 的区别

bool 和 status 的区别主要取决于上下文中的定义和使用方式。以下是它们之间的一些典型区别：

1. bool 是一种数据类型

• 描述: bool 是一种内置的布尔类型，用来表示逻辑上的真假值，取值范围是 true 或 false。
• 用途: 用于条件判断、布尔表达式、逻辑运算等。
• 常见场景:
  • 判断条件是否成立。
  • 返回是否成功的标志，例如函数的执行结果。

示例:

bool isReady = true; // 表示某个条件成立
if (isReady) {
    // 做某些事情
}

2. status 是一种抽象的状态表示

• 描述: status 一般用于表示系统、进程、任务、操作等的状态，通常不局限于 true 和 false 两种值。
• 用途: 表示多种状态（例如成功、失败、处理中、错误等），通常会被定义为枚举或特定类型。
• 常见场景:
  • 描述复杂的操作结果或状态。
  • 提供更多上下文信息。

示例（用枚举表示 status）:

enum class Status {
    SUCCESS,
    FAILURE,
    PENDING,
    ERROR
};
Status taskStatus = Status::PENDING; // 当前任务正在处理中
if (taskStatus == Status::SUCCESS) {
    // 操作成功
} else if (taskStatus == Status::ERROR) {
    // 操作失败
}

3. 典型区别

4. 选择依据

• 简单的真假判断:
  • 如果某个结果仅需表示 '是或否'（例如操作是否成功），选择 bool。
• 描述复杂状态:
  • 如果需要提供更详细的上下文信息，或者状态有多个可能值，选择 status 或类似的机制。

示例：二者结合使用

在实际工程中，可以同时使用 bool 和 status，例如在函数返回值中使用 status 表示总体结果，用 bool 表示局部成功或失败的标志：

enum class Status {
    SUCCESS,
    PARTIAL_SUCCESS,
    FAILURE,
    ERROR
};

bool isValidInput(const std::string& input) {
    return !input.empty(); // 简单的真假判断
}

Status processTask(const std::string& task) {
    if (!isValidInput(task)) {
        return Status::ERROR; // 返回复杂状态
    }
    // 处理任务逻辑...
    return Status::SUCCESS;
}