C++ | 二叉搜索树

前言

本篇博客讲解c++中的继承

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：C++_普通young man的博客-CSDN博客

⏩ 本人giee:   普通小青年 (pu-tong-young-man) - Gitee.com

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章
————————————————

---

目录

  二叉搜索树的概念

二叉搜索树的性能分析

最优情况

最差情况

平均情况

二分查找对比

平衡二叉搜索树

二叉搜索树的插入

二叉搜索树的查找

二叉搜索树的删除

二叉搜索树的实现代码

BSTNode 类

BSTree 类

内部细节

辅助函数

二叉搜索树key使用场景

场景1：小区无人值守车库

场景2：英文文章单词拼写检查

二叉搜索树key和key/value使用场景

场景1：简单的中英互译字典

场景2：商场无人值守车库

场景3：统计文章中单词出现的次数

key/value代码实现

BSTNode 类

BSTree 类

内部细节

---

二叉搜索树的概念

        二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它满足特定的排序属性，这使得在树中的查找、插入和删除操作变得高效。以下是二叉搜索树的一些关键概念和性质：

1. 定义：

   • 二叉搜索树是一种二叉树，每个节点最多有两个子节点，并且每个节点的值大于其左子树上的任何其他节点的值，小于其右子树上的任何其他节点的值。
   • 这意味着对于任意节点 n，所有左子树中的节点值 x 都满足 x ≤ n，所有右子树中的节点值 y 都满足 y ≥ n。

2. 性质：

   • 左子树上所有结点的值均小于或等于根结点的值。
   • 右子树上所有结点的值均大于或等于根结点的值。
   • 根结点的左子树和右子树本身也必须是二叉搜索树。
   • 二叉搜索树中可以支持插入重复的键值，这取决于具体的应用场景。在一些实现中，如标准模板库(STL)中的 std::set 和 std::map 不允许重复键值；而 std::multiset 和 std::multimap 则允许重复键值。

3. 操作：

   • 查找：给定一个键值，在二叉搜索树中查找该键值对应的节点。
   • 插入：将一个新的节点添加到树中，同时保持二叉搜索树的性质。
   • 删除：从树中移除一个节点，并调整树以维持其为二叉搜索树。
   • 中序遍历：按照左-根-右的顺序访问树中的节点，可以得到一个递增的有序序列。

代码结构：

// 节点结构定义
template<class T>
class BSTNode {
public:
    T _key; // 节点存储的键值
    BSTNode<T>* _left; // 左子节点指针
    BSTNode<T>* _right; // 右子节点指针

    // 构造函数
    BSTNode(const T& key) :
        _key(key), // 初始化键值
        _left(nullptr), // 初始化左子节点指针为nullptr
        _right(nullptr) // 初始化右子节点指针为nullptr
    {}
};

---

二叉搜索树的性能分析

二叉搜索树（BST）的性能主要依赖于树的高度。下面是对不同情况下的性能分析：

最优情况

• 当二叉搜索树是一棵完全二叉树（或者接近完全二叉树）时，树的高度是最小的，此时高度大约为 log⁡2N，其中 N 是树中的节点数量。
• 在这种情况下，二叉搜索树的所有基本操作（查找、插入、删除）的时间复杂度都是 O(log⁡2N)，这是非常高效的。

最差情况

• 当二叉搜索树退化成一条链（单支树），即所有的节点只有一个子节点时，树的高度最大，此时高度为 N。
• 在这种情况下，二叉搜索树的操作时间复杂度退化为 O(N)，这意味着查找、插入、删除可能需要遍历整个树。

平均情况

• 如果二叉搜索树的构建是随机的，并且没有明显的偏向性，那么平均情况下树的高度大致为 log⁡2N，因此平均时间复杂度为 O(log⁡2N)。

二分查找对比

• 二分查找可以在 O(log⁡2N) 时间内完成查找，但前提是数据必须存储在一个支持随机访问的数据结构（如数组）中，并且数据必须是有序的。
• 二分查找的缺点在于，对于插入和删除操作，由于数据存储在数组中，可能需要移动大量的元素来保持有序性，导致效率较低，通常是 O(N)。

平衡二叉搜索树

• 为了解决二叉搜索树在最坏情况下的性能问题，引入了自平衡二叉搜索树的概念，如AVL树和红黑树。(这个后面我也会学习)
• 这些树通过旋转等方法自动保持树的平衡，确保任何操作都不会使树的高度超过 O(log⁡2N)，从而提供了更稳定的性能。

---

二叉搜索树的插入

1. 树为空的情况：

   • 如果二叉搜索树为空，那么直接创建一个新的节点，并将这个新节点作为树的根节点（root指针指向这个新节点）。

2. 树不为空的情况：

   • 如果二叉搜索树不为空，则根据二叉搜索树的性质进行插入操作：
     • 比较待插入值与当前节点的值：
       • 如果待插入值小于当前节点的值，则向当前节点的左子树方向移动。
       • 如果待插入值大于当前节点的值，则向当前节点的右子树方向移动。
     • 继续沿着左子树或右子树向下寻找，直到找到一个空的位置（即当前节点的左子节点或右子节点为空）。
     • 在找到的空位置处插入新的节点。

3. 处理相等值的情况：

   • 如果二叉搜索树支持插入相等的值，那么当待插入值等于当前节点的值时，可以选择向左子树方向移动或向右子树方向移动，找到空位置后插入新节点。
   • 注意保持逻辑的一致性，即如果选择向左插入相等的值，那么应该始终如此，或者始终选择向右插入，避免在不同的情况下选择不同的方向，这样可以避免混乱并保持树的一致性和可预测性。

代码展示：

bool insert(const T& key) {
    // 判断根节点是否为空
    if (_root == nullptr) {
        // 如果树为空，则创建一个新的节点作为根节点
        _root = new Node(key);
        return true; // 插入成功
    }

    // 使用两个指针，person 用来记录最近访问过的父节点，cur 用来记录当前正在访问的节点
    Node* person = nullptr;
    Node* cur = _root;

    // 循环遍历树直到找到空位置
    while (cur != nullptr) {
        if (key >= cur->_key) { // 如果待插入的键值大于等于当前节点的键值
            person = cur; // 更新父节点指针
            cur = cur->_right; // 向右子树移动
        }
        else if (key < cur->_key) { // 如果待插入的键值小于当前节点的键值
            person = cur; // 更新父节点指针
            cur = cur->_left; // 向左子树移动
        }
        else { // 如果键值已经存在，则返回失败
            return false;
        }
    }

    // 创建新的节点
    cur = new Node(key);

    // 将新节点链接到适当的位置
    if (key >= person->_key) { // 如果键值大于等于父节点的键值，则作为右子节点插入
        person->_right = cur;
    } else { // 否则作为左子节点插入
        person->_left = cur;
    }

    return true; // 插入成功
}

可以用这组数据测试：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

key::BSTree<int> s1;
//插入
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto it : a)
{
s1.insert(it);
}
s1.InOrder();//

    s1.InOrder();->中序打印，是有序的，大家可以自己画画递归展开图，方便自己理解

 void _InOrder(BSTNode<T>* _root) {
        if (_root == nullptr) {
            return;
        }
        _InOrder(_root->_left); // 遍历左子树
        cout << _root->_key << " "; // 访问当前节点
        _InOrder(_root->_right); // 遍历右子树
    }

---

二叉搜索树的查找

查找操作的具体过程

1. 从根开始比较：

   • 从根节点开始，比较查找值 x 与当前节点的值。
   • 如果 x 大于当前节点的值，则向当前节点的右子树方向移动。
   • 如果 x 小于当前节点的值，则向当前节点的左子树方向移动。

2. 最多查找高度次：

   • 查找操作最多需要进行树的高度次比较。
   • 如果一直走到某个节点的左子节点或右子节点为空，还没有找到目标值 x，则说明该值不在树中。

3. 不支持插入相等的值：

   • 如果二叉搜索树不支持插入相等的值，那么一旦找到目标值 x 即可立即返回成功。

4. 支持插入相等的值：

   • 如果二叉搜索树支持插入相等的值，这意味着可能存在多个值为 x 的节点。
   • 在这种情况下，一般要求查找中序遍历的第一个值为 x 的节点。
   • 例如，在查找值 3 时，如果有多于一个 3，则应返回第一个在中序遍历中出现的 3。

代码展示：

// 查找操作
bool find(const T& key) {
    Node* cur = _root; // 从根节点开始查找

    // 循环直到找到节点或到达空节点
    while (cur != nullptr) {
        if (key > cur->_key) { // 如果查找的键值大于当前节点的键值
            cur = cur->_right; // 向右子树移动
        } else if (key < cur->_key) { // 如果查找的键值小于当前节点的键值
            cur = cur->_left; // 向左子树移动
        } else { // 如果找到目标键值
            return true; // 找到目标键值，返回 true
        }
    }

    // 没有找到目标键值
    return false;
}

 测试代码：

//查找
if (s1.find(7))
{
cout << "OK"<<endl;
}
else
{
cout << "NO" << endl;
}

---

二叉搜索树的删除

        删除二叉搜索树中的节点是一个稍微复杂的过程，因为它需要保持树的性质——对于任何节点，其所有左子树的节点的键值小于该节点的键值，所有右子树的节点的键值大于该节点的键值。下面是针对不同情况的解决方案：

情况总结表：

情况	描述	解决方案
1	N的左右孩子均为空	直接将N的父亲节点对应的子节点指针设为空，然后删除N节点。（也可以当作情况2或3处理）
2	N的左孩子为空，右孩子不为空	将N的父亲节点对应的子节点指针指向N的右孩子，然后删除N节点。
3	N的右孩子为空，左孩子不为空	将N的父亲节点对应的子节点指针指向N的左孩子，然后删除N节点。
4	N的左右孩子均不为空	使用N的左子树中的最大值节点R（最右节点）或N的右子树中的最小值节点R（最左节点）来替代N节点。替换后，转而删除R节点，此时R节点符合情况2或3。

文字描述：

1. N的左右孩子均为空：

   • 这是最简单的情况，只需要将N的父亲节点的相应孩子指针设为空，然后删除N即可。这种情况下，N没有子节点，因此不会影响树的结构。

1. N的左孩子为空，右孩子不为空：

   • 这种情况下，可以用N的右孩子来代替N的位置。具体操作是将N的父亲节点的相应孩子指针指向N的右孩子，然后删除N节点。

2. N的右孩子为空，左孩子不为空：

   • 类似于情况2，只是这次使用N的左孩子来代替N的位置。具体操作是将N的父亲节点的相应孩子指针指向N的左孩子，然后删除N节点。

1. N的左右孩子均不为空：

   • 这种情况比较复杂，不能直接删除N。可以找到N的左子树中的最大值节点R（即最右侧的节点）或N的右子树中的最小值节点R（即最左侧的节点），并将R的值与N交换。之后，问题转化为删除R节点，这时R节点只可能有一个孩子或者没有孩子，属于情况2或3。

这边一定是去找右子树的最左边的值，才是最合适的值

这里就可以发现为什么replacePerson为什么不给nullptr，而是要给cur，当我们要删除root就会野指针

---

代码实现：

bool erase(const T& key) {
    Node* person = nullptr; // person用于记录cur的父节点，以便在删除节点时调整父节点的指向
    Node* cur = _root; // 从根节点开始搜索目标键值对应的节点
    
    // 循环查找要删除的节点
    while (cur) {
        if (key > cur->_key) { // 如果目标键值大于当前节点键值，则向右子树搜索
            person = cur; // 更新person为当前节点，因为下一步将进入右子树
            cur = cur->_right; // 向右子树继续查找
        }
        else if (key < cur->_key) { // 如果目标键值小于当前节点键值，则向左子树搜索
            person = cur; // 更新person为当前节点，因为下一步将进入左子树
            cur = cur->_left; // 向左子树继续查找
        }
        else { // 找到了要删除的节点
            // 情况1: 要删除的是叶子节点或只有一个孩子的节点
            if (cur->_left == nullptr) { // 没有左孩子
                // 判断是否是根节点
                if (cur == _root) {
                    _root = cur->_right; // 将根节点设置为其右孩子
                }
                else { // 不是根节点
                    if (person->_left == cur) { // 要删除的节点是其父节点的左孩子
                        person->_left = cur->_right; // 将其父节点的左孩子设置为要删除节点的右孩子
                    }
                    else { // 要删除的节点是其父节点的右孩子
                        person->_right = cur->_right; // 将其父节点的右孩子设置为要删除节点的右孩子
                    }
                }
                delete cur; // 删除该节点
            }
            else if (cur->_right == nullptr) { // 没有右孩子
                // 判断是否是根节点
                if (cur == _root) {
                    _root = cur->_left; // 将根节点设置为其左孩子
                }
                else { // 不是根节点
                    if (person->_left == cur) { // 要删除的节点是其父节点的左孩子
                        person->_left = cur->_left; // 将其父节点的左孩子设置为要删除节点的左孩子
                    }
                    else { // 要删除的节点是其父节点的右孩子
                        person->_right = cur->_left; // 将其父节点的右孩子设置为要删除节点的左孩子
                    }
                }
                delete cur; // 删除该节点
            }
            // 情况2: 要删除的节点有两个孩子（左右孩子都有）
            else {
                Node* replacePerson = cur; // replacePerson记录待替换节点的父节点
                Node* replace = cur->_right; // replace记录待替换的节点，初始化为当前节点的右孩子
                
                // 寻找右子树中的最小节点
                while (replace->_left) {
                    replacePerson = replace; // 更新replacePerson为当前节点
                    replace = replace->_left; // 向左子树继续查找最小值
                }
                
                // 将找到的最小节点的键值复制到当前节点
                cur->_key = replace->_key;
                
                // 删除替换用的节点
                if (replacePerson->_left == replace) { // 如果待删除节点是其父节点的左孩子
                    replacePerson->_left = replace->_right; // 将其父节点的左孩子设置为待删除节点的右孩子
                }
                else { // 如果待删除节点是其父节点的右孩子
                    replacePerson->_right = replace->_right; // 将其父节点的右孩子设置为待删除节点的右孩子
                }
                delete replace; // 删除替换用的节点
            }
            return true; // 成功删除节点
        }
    }
    return false; // 未找到要删除的节点
}

---

二叉搜索树的实现代码

#include<iostream>
using namespace std;
//key搜索
namespace key {

//节点结构
template<class T>
class BSTNode
{
public:
T _key;
BSTNode<T>* _left;
BSTNode<T>* _right;
//构造
BSTNode(const T& key) :
//初始化列表
_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};

//树的结构
template<class T>
class BSTree
{
//typedef BSTNode<T> Node
using Node = BSTNode<T>;

public:

/*插入*/
bool insert(const T& key) {
//判断根是否为空
if (_root == nullptr) {
_root = new Node(key);
return true;
}
//双指针
Node* person = nullptr;
Node* cur = _root;
//循环
while (cur)
{
if (key >= cur->_key) {
person = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
person = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//链接节点
cur = new Node(key);
if (key >= person->_key)
{
person->_right = cur;
}
else
{
person->_left = cur;
}
return true;
}

/*查找*/
bool find(const T& key) {
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}

/*删除*/
bool erase(const T& key) {
//双指针
Node* person = nullptr;
Node* cur = _root;
//循环
while (cur)
{
if (key > cur->_key) {
person = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
person = cur;
cur = cur->_left;
}
else
{
//叶子节点+只有一个节点的
if (cur->_left == nullptr) {
//判断是否是根节点
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (person->_left == cur) {

person->_left = cur->_right;
}
else
{
person->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
//判断是否是根节点
if (cur == _root) {
_root = cur->_left;
}
else
{
if (person->_left == cur) {

person->_left = cur->_left;
}
else
{
person->_right = cur->_left;
}
}
delete cur;
}
//两个节点
else
{
Node* replacePerson = cur;//指向cur是防止删除根节点的时候越界
Node* replace = cur->_right;//右子树的最小值(最合适，可以带左子树试一下，不构成BST)
while (replace->_left)
{
replacePerson = replace;
replace = replace->_left;
}
//将这个值赋值给cur位置
cur->_key = replace->_key;
//删除节点
if (replacePerson->_left == replace)
{
replacePerson->_left = replace->_right;
}
else
{
replacePerson->_right = replace->_right;
}
delete replace;
}
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);
}
private:
Node* _root = nullptr;
};
}

BSTNode 类

这是用于表示树中的节点的类。每个节点包含：

• _key：键，用于排序。
• _left 和 _right：指向左子节点和右子节点的指针。

构造函数用于初始化节点的键值和左右子节点指针，默认左右子节点均为 nullptr。

BSTree 类

这个类定义了二叉搜索树的行为：

• 插入操作 (insert)：向树中添加一个新的键。如果键已经存在，则插入失败。
• 查找操作 (find)：在树中查找具有指定键的节点。
• 删除操作 (erase)：从树中移除具有指定键的节点。
• 中序遍历 (InOrder)：按升序打印树中的所有键。

内部细节

• 树的根节点 _root 是一个私有成员变量，初始值为 nullptr 表示空树。
• 插入、查找和删除操作都使用了“双指针”技术来找到正确的插入或删除位置。
• 插入操作处理了树为空的情况，直接将新节点作为根节点。
• 删除操作处理了三种情况：叶子节点、有一个子节点、有两个子节点的情况。

辅助函数

• _InOrder：递归地执行中序遍历。

---

二叉搜索树key使用场景

场景1：小区无人值守车库

在这个场景下，小区的物业管理公司将所有购买了车位的业主车牌号录入后台系统中。当车辆试图进入小区时，入口处的系统会自动扫描车牌号，并与后台系统中的车牌号进行比对。如果车牌号存在于二叉搜索树中，则意味着该车辆拥有进入小区的权利，此时系统会自动抬起栏杆让车辆通过；反之，如果车牌号不在二叉搜索树中，则系统会提示该车辆不属于本小区，并阻止其进入。

在这个应用中，车牌号作为唯一的标识符（key），同时也是用来判断车辆是否有权进入的关键信息。由于车牌号通常是唯一的，并且不会经常改变，因此这种情况下非常适合使用二叉搜索树来高效地存储和查询这些车牌号。

场景2：英文文章单词拼写检查

这个场景涉及到检查一篇英文文章中的单词拼写是否正确。为了实现这一功能，首先需要构建一个包含所有正确拼写的单词的词库，并将这些单词按照字母顺序插入到二叉搜索树中。当文章被读取时，系统会对文章中的每个单词进行检查，通过二叉搜索树来确定该单词是否存在。如果一个单词没有出现在二叉搜索树中，这意味着它可能是拼写错误的单词，此时可以将其用波浪线标出或以其他方式高亮显示，以便用户进一步检查和修正。

在这种情况下，单词本身作为key，同时也是要验证的信息。二叉搜索树允许快速定位特定单词，从而使得拼写检查过程更加高效。

---

二叉搜索树key和key/value使用场景

场景1：简单的中英互译字典

在这个场景中，我们创建一个简单的中英互译字典，其中英文单词作为key，中文翻译作为value。当用户输入一个英文单词时，系统会在二叉搜索树中查找该key，如果找到，就会返回对应的中文翻译。这样就实现了基于key的快速查找功能。需要注意的是，虽然不允许直接修改key，但是value是可以更新的，例如可以在原有条目的基础上增加新的翻译或更正现有的翻译。

场景2：商场无人值守车库

在这个场景下，商场的无人值守车库系统会在车辆入场时记录其车牌号码（作为key）以及入场时间（作为value）。当车辆离开停车场时，出口处的系统会再次扫描车牌号码，并通过二叉搜索树查找对应的入场时间。然后，系统计算停车时长（当前时间减去入场时间），并据此计算停车费用。用户支付费用之后，栏杆升起，车辆可以离开。这种情况下，车牌号码作为唯一标识符，并且保持不变，而入场时间是可以根据实际情况更新的value。

场景3：统计文章中单词出现的次数

在这个场景中，我们需要统计一篇文章中各个单词的出现频率。首先，将文章中的每一个单词作为key，初始化时对应的value设置为出现次数（默认为0）。每当读取到一个新的单词时，系统会在二叉搜索树中查找该单词。如果单词尚未出现过（即value为0或者不存在），则将其加入树中，并将其value设置为1（表示首次出现）。如果单词已经存在，则将对应的value（出现次数）增加1。这样，随着文章的逐字读取，二叉搜索树中就会记录下每个单词的出现次数。

key/value代码实现

namespace key_value {

// 节点结构定义
template<class T, class V>
class BSTNode
{
public:
T _key;       // 存储键
V _value;     // 存储值
BSTNode<T, V>* _left;   // 左子节点指针
BSTNode<T, V>* _right;  // 右子节点指针

// 构造函数
BSTNode(const T& key, const V& value) :
_key(key),
_value(value),
_left(nullptr),
_right(nullptr)
{}
};

// 树的结构定义
template<class T, class V>
class BSTree
{
// 使用别名简化BSTNode类型的书写
using Node = BSTNode<T, V>;

public:
// 默认构造函数
BSTree() = default;

// 拷贝构造函数
BSTree(const BSTree& tmp) {
// 深拷贝整棵树
_root = _Copy(tmp._root);
}

// 析构函数
~BSTree() {
// 释放所有节点占用的内存
Destroy(_root);
_root = nullptr;
}

// 拷贝赋值运算符
BSTree& operator=(BSTree tmp) {
// 使用交换技巧完成浅拷贝到深拷贝的转换
swap(_root, tmp._root);
return *this;
}

/* 插入 */
// 向树中插入键值对
bool insert(const T& key, const V& value) {
// 如果树为空，创建新节点作为根节点
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}
// 使用双指针找到合适的位置插入新节点
Node* person = nullptr;
Node* cur = _root;
while (cur) {
if (key >= cur->_key) {
person = cur;
cur = cur->_right;
}
else if (key < cur->_key) {
person = cur;
cur = cur->_left;
}
else {
// 如果键已存在，插入失败
return false;
}
}
// 创建新节点，并根据比较结果将其插入到合适的位置
cur = new Node(key, value);
if (key >= person->_key) {
person->_right = cur;
}
else {
person->_left = cur;
}
return true;
}

/* 查找 */
// 在树中查找指定键对应的节点
Node* find(const T& key) {
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
cur = cur->_right;
}
else if (key < cur->_key) {
cur = cur->_left;
}
else {
return cur;
}
}
return nullptr;
}

/* 删除 */
// 从树中删除指定键及其对应的节点
bool erase(const T& key) {
// 使用双指针找到要删除的节点
Node* person = nullptr;
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
person = cur;
cur = cur->_right;
}
else if (key < cur->_key) {
person = cur;
cur = cur->_left;
}
else {
// 处理三种情况：叶节点、只有一个子节点、有两个子节点
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
}
else {
if (person->_left == cur) {
person->_left = cur->_right;
}
else {
person->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
}
else {
if (person->_left == cur) {
person->_left = cur->_left;
}
else {
person->_right = cur->_left;
}
}
delete cur;
}
else {
Node* replacePerson = cur;
Node* replace = cur->_right;
while (replace->_left) {
replacePerson = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replacePerson->_left == replace) {
replacePerson->_left = replace->_right;
}
else {
replacePerson->_right = replace->_right;
}
delete replace;
}
return true;
}
}
return false;
}

// 类内部调用中序遍历
void InOrder() {
_InOrder(_root);
std::cout << std::endl;
}

private:
// 中序遍历（递归）
void _InOrder(Node* _root) {
if (_root == nullptr) {
return;
}
_InOrder(_root->_left);
std::cout << _root->_key << "-" << _root->_value << " ";
_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* new_node = new Node(_root->_key, _root->_value);
new_node->_left = _Copy(_root->_left);
new_node->_right = _Copy(_root->_right);
return new_node;
}

private:
Node* _root = nullptr; // 根节点指针
};
}

下面是对给定代码的一个简明解析：

这段代码定义了一个二叉搜索树(Binary Search Tree, BST)，它是一个数据结构，用于存储键值对。该实现使用了 C++ 的模板类来支持不同类型的键和值。

BSTNode 类

这是用于表示树中的节点的类。每个节点包含：

• _key：键，用于排序。
• _value：与键关联的值。
• _left 和 _right：指向左子节点和右子节点的指针。

BSTree 类

这个类定义了二叉搜索树的行为：

• 构造函数：默认构造函数和拷贝构造函数。
• 析构函数：清理树中的所有节点。
• 拷贝赋值运算符：使用交换技巧来实现深拷贝。
• 插入操作 (insert)：向树中添加一个新的键值对。如果键已经存在，则插入失败。
• 查找操作 (find)：在树中查找具有指定键的节点。
• 删除操作 (erase)：从树中移除具有指定键的节点。
• 中序遍历 (InOrder)：按升序打印树中的所有键值对。
• 辅助函数：
  • _InOrder：递归地执行中序遍历。
  • Destroy：释放树中的所有节点。
  • _Copy：递归地复制一棵树。

内部细节

• 树的根节点 _root 是一个私有成员变量，初始值为 nullptr 表示空树。
• 插入和删除操作处理了二叉搜索树中常见的几种情况：没有子节点、有一个子节点以及有两个子节点的情况。
• 拷贝构造函数和拷贝赋值运算符确保了对象的正确复制。

---

原文地址：https://blog.csdn.net/2302_78381559/article/details/142371870

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！