【C++】二叉搜索树（二叉查找树、二叉排序树）详解
文章目录
- 一、概念
- 二、定义
- 强制生成默认构造BSTree() = default
- 赋值重载swap写法详解
- 传统深拷贝写法中为什么需要return *this?
- InOrder()为何这样设计？
- 三、查找、插入
- 四、删除
- 五、性能分析
- 六、应用——KV模型
- 七、完整代码
- 八、代码中重难点
- 为什么有两处template
typedef BSTreeNode}
};
template
typedef BSTreeNode
_root = Copy(t._root);
}
private:
//下面这部分隐藏，对外只提供InOrder().用户只用关注接口不必关心细节。
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;
}
Node* _root = nullptr;
}
默认构造函数
强制生成默认构造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 的好处包括：
- 让编译器自动生成，减少代码量和维护负担。
- 避免意外错误，例如忘记初始化成员变量。
适用场景
使用 = default 常见于以下场景：
- 需要默认构造函数，但有其他特殊构造函数：
如果定义了其他构造函数（如拷贝构造、移动构造等），而仍需要默认构造函数，必须显式声明它。
- 需要提高代码语义的清晰度：
即使编译器会自动生成默认构造函数，显式 = default 更直观。
赋值运算符重载函数
BSTree& operator=(const BSTree& t) { swap(_root, t._root); return *this; } //传统深拷贝写法。也很好 //BSTree& operator =(const BSTree& t) //{ // //tree1=tree2 // if (this != &t) // // { // Destory(_root);//清空tree1树里的节点，树还在，但是空树 // _root = Copy(t._root);//把tree2里的节点深拷贝到tree1 // } // return *this;//返回tree1； //}赋值重载swap写法详解
这种写法很高效，节省资源，一定要掌握！！！
我们通过一个详细的例子来说明写法二（swap 方式）中的每一步，以及各个变量（如 this 和 t）的变化。
代码回顾
template class BSTree { typedef BSTreeNode Node; public: BSTree& operator=(BSTree 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& operator=(BSTree t)
- 当 tree1 = tree2; 发生时，tree2 作为参数传递给 BSTree 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 函数。该函数的核心是交换两个对象的值，具体步骤如下：
- 创建临时变量 temp：temp 保存 this->_root（即 tree1 的 _root），此时 temp = 5。
- 将 t._root 赋给 this->_root：此时 this->_root 指向 t._root 的值（即 10），也就是 tree2 的根节点。
- 将 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 这个节点及其子树（如果有）。
变量状态：
- this->_root：保持指向 10，即 tree2 的根节点。
- t：将在函数结束时销毁，t._root 指向 5 的那部分内存会被释放。
最终结果
- tree1：现在拥有 tree2 的树结构，根节点为 10。
- tree2：原来的结构不变，仍然指向 10，但由于我们是通过副本 t 操作，tree2 本身不会受到影响。
- 旧的 tree1 的树（即以 5 为根的树）：在 t 的生命周期结束时，随着 t 的析构函数被调用，旧的 tree1 树被销毁。
关键点总结：
- 临时副本：通过传值的方式，将 tree2 的副本传递给 t，t 独立于 tree2。
- 高效的 swap：swap 交换了 tree1 和 t 的根节点指针，而不是深拷贝整个树，效率更高。
- 资源管理：由于 t 是传入的临时变量，赋值过程结束后 t 会被自动销毁，释放旧的 tree1 的内存，避免了手动 Destroy 的麻烦。
- 链式赋值：return *this 支持链式调用，如 tree1 = tree2 = tree3;。
这种 swap 的写法，简洁、高效，并且通过临时对象 t 自动管理资源，是现代 C++ 中推荐的写法。
传统深拷贝写法中为什么需要return *this?
为什么返回 *this？即使 tree1 的内存已被释放？
- 释放的只是原树的节点，树本身仍然存在
调用 Destory(_root) 时，仅释放了 tree1 原有的节点内存，但 tree1 本身（即当前对象）仍然存在。_root 只是一个指针成员变量，而非整个 tree1 对象的内存。
例如：
- 如果 tree1 原本有数据，它们会被 Destory 清空，变成一个空树（_root == nullptr）。
- 然后通过 Copy(t._root)，重新构造 tree1 的数据结构，使其变得与 tree2 相同。
最终，tree1 并没有被销毁，而是被重建。
- 返回值的意义：支持链式赋值
返回 *this 是赋值运算符的标准设计，用于支持链式赋值。链式赋值允许连续的赋值操作，如：
BSTree a, b, c; a = b = c;
- 流程：
- b = c 执行后，返回 b 的引用。
- 然后将 b 的引用作为参数传递给 a = b。
如果不返回 *this，链式赋值将无法工作。
- 为什么不是返回销毁的内容？
Destory(_root) 只是清空了树的原有数据，tree1 的对象本身还存在。返回 *this 是返回当前对象的引用，表示赋值操作完成，当前对象的状态被更新为目标对象的状态。
例如：
BSTree tree1, tree2; // 假设 tree1 有旧的节点，tree2 是目标树 tree1 = tree2;
在 tree1 = tree2 过程中：
- 清空 tree1 的原节点，但 tree1 本身还在。
- 将 tree2 的数据复制到 tree1。
- 返回 tree1 的引用，表示 tree1 现在是 tree2 的深拷贝。
- 示意图说明
初始状态：
- tree1：包含若干节点，_root 指向一棵树。
- tree2：包含若干节点，_root 指向另一棵树。
操作后：
- Destory(_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() { Destory(_root); }中序遍历InOrder()
void InOrder() { _InOrder(_root); cout if (root == nullptr) return; _InOrder(root-_left); cout _key _right); }InOrder()为何这样设计？
InOrder() 函数设计的目的是为了封装实现细节，让用户只需调用接口函数即可完成对二叉树的中序遍历，而不必了解树的内部数据结构。这种设计的优势在于以下几点：
- 隐藏内部实现细节
在代码中，InOrder() 调用了一个私有的辅助递归函数 _InOrder(Node* root)：
void InOrder() { _InOrder(_root); cout if (!root) return; InOrderManual(root-_left); cout _key _right); }封装之后，用户无需处理树的节点指针，也不用理解递归过程，降低了使用门槛。
- 降低错误概率
让用户直接访问和操作树的内部结构（如 _root 指针）可能导致以下问题：
- 不小心破坏了树的完整性（如误修改了 _root 或其他节点的子指针）。
- 错误遍历逻辑：用户可能误用树的节点指针，造成逻辑混乱。
通过只暴露 InOrder() 方法，用户无法直接接触内部的 _root 或树节点，减少了误操作的风险。
- 增强代码的可维护性和扩展性
如果以后需要修改中序遍历的实现（例如加入线程或并行化），我们只需改动私有的 _InOrder() 方法，而无需修改 InOrder() 或影响用户代码。
用户调用 InOrder() 的方式保持不变，代码改动对外透明。这种设计符合模块化设计的思想。
三、查找、插入
1.查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在
另外需要注意的是
①最大元素一定是在树的最右分枝的端结点上。
②最小元素一定是在树的最左分枝的端结点上。
//find函数。 用k，关键字的意思 bool Find(const K& key) { Node* cur = _root;// 从根节点开始查找 //_root 是存储在 BSTree 类中的成员变量，它指向树的根节点。通过这个指针，你可以访问整个树。 while (cur) { if (cur->_key _right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; }2.插入
- 特殊情况处理：
如果树是空的（即 root == nullptr），那么直接把要插入的元素作为根节点插入即可。
- 基本规则：
○ 因为是二叉搜索树，所以不能插入重复元素。
○ 插入的元素一定会成为某个叶子节点（即没有子节点的位置）。
- 具体操作思路：
○ 从根节点开始定义一个指针变量 cur 来遍历树，初始时 cur = root。
○ 如果插入的值比当前节点的值小，就向左子树移动；如果插入的值比当前节点的值大，就向右子树移动。
○ 在移动时，还需要定义另一个变量 parent 记录当前节点的“父节点”，也就是 cur 移动前的位置。这样，当找到一个空位时，知道应该插入在 parent 的左子树还是右子树。
- 最后一步：
○ 当 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 _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 _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 _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个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N
六、应用——KV模型
- K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
- KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方
式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是就构成一种键值对。
- 统计次数
//统计词语出现的次数 string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" }; // 统计水果出现的次 BSTree countTree; for (auto str : strs) { auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder();
模型代码
namespace key_value { // ====================== // 二叉搜索树节点结构体 // ====================== template struct BSTreeNode { // 为了简化书写，用 Node 表示 BSTreeNode 类型本身 typedef BSTreeNode 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 BSTree { typedef BSTreeNode 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 _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 _right = cur; } else { parent->_left = cur; } return true; } // 查找给定 key 对应的节点，返回指向该节点的指针，如果不存在则返回 nullptr Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key _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 _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 if (root == nullptr) return; _InOrder(root-_left); cout _key _right); } private: Node* _root; // 指向二叉搜索树的根节点 }; }七、完整代码
template //树节点的结构体 struct BSTreeNode { typedef BSTreeNode Node;//千万别少了这句！！！！！！ Node* _left; Node* _right; K _key; BSTreeNode(const K& key)//这里是K是大写，一定要注意，改了好多 :_left(nullptr) , _right(nullptr) , _key(key) { } }; template //二叉搜索树这个类 class BSTree { typedef BSTreeNode Node; public: //默认构造 BSTree() = default; //拷贝构造 BSTree(const BSTree& t) { _root = Copy(t._root); } //赋值重载 //完整的函数名每次忘记怎么写 //BSTree& ：返回值类型是对当前对象的引用，以便支持链式赋值（a = b = c; ）。 //operator=：定义赋值运算符。 //const BSTree& t：参数类型是一个const引用，表示要赋值的对象不应被修改。 //使用 swap 交换资源 BSTree& operator=(const BSTree& t) { swap(_root, t._root); return *this; } //传统深拷贝写法。也很好（代码详解在语雀） //BSTree& operator =(const BSTree& t) //{ // //tree1=tree2 // if (this != &t) // { // Destory(_root);//清空tree1树里的节点，树还在，但是空树 // _root = Copy(t._root);//把tree2里的节点深拷贝到tree1 // } // return *this;//返回tree1； //} //析构 ~BSTree() { Destory(_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; //不是root while (cur) { if (cur->_key _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 _right = cur; } else { parent->_left = cur; } return true; } bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key _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 _right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; } //前序遍历 void InOrder() { _InOrder(_root); cout 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(const K & key); } private: //下面这部分隐藏，对外只提供InOrder().用户只用关注接口不必关心细节。 void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root-_left); cout _key _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 Destory(Node* root) { if (root == nullptr) { return; } Destory(root->_left); Destory(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 _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 _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 _right, key); } else if (root->_key _left, 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); } } } private: Node* _root = nullptr; };八、代码中重难点
为什么有两处template // 做某些事情 } SUCCESS, FAILURE, PENDING, ERROR }; Status taskStatus = Status::PENDING; // 当前任务正在处理中 if (taskStatus == Status::SUCCESS) { // 操作成功 } else if (taskStatus == Status::ERROR) { // 操作失败 } 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; }
- K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
- 那7和10怎么在二叉排序树中找到呢？
- 为什么是7或者10来替换8的位置？
- d情况（要删除的结点有左、右孩子结点） ——替换法删除
- 特殊情况处理：
- 原因 1: 明确默认构造需求
- 生成默认构造函数：
- 为什么有两处template
typedef BSTreeNode}
};
template
typedef BSTreeNode
_root = Copy(t._root);
}
private:
//下面这部分隐藏，对外只提供InOrder().用户只用关注接口不必关心细节。
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;
}
Node* _root = nullptr;
}
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。
