【C++升华篇】学习C++就看这篇---＞二叉搜索树深度剖析
目录
前言：
从本篇文章开始正式进入C++高阶 的学习,C++高阶主要包括二叉搜索树 ,AVL树,红黑树,哈希等高阶数据结构, 以及C++11和智能指针,抛异常等等. 高阶的内容往往是与普通人拉开差距的 内容,请同学们耐心学习!本篇文章着重讲解，之后我们来模拟实现二叉搜索树!最后拓展讲解二叉搜索树的应用场景.
本章重点：
本篇文章着重讲解
1. 二叉搜索树的概念以及定义
2. 二叉搜索树的模拟实现
3. 二叉搜索树的应用场景
📕1、二叉搜索树的概念及定义
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
-
若它的左子树不为空,则左子树的所有节点的值都小于根节点的值 -
若它的右子树不为空,则右子树的所有节点的值都大于根节点的值 -
它的左右子树也分别为二叉搜索树
如下：
📕2、二叉搜索树的性质
首先,二叉搜索树是有序的!
它的中序遍历出来就是一个有序的序列
上图所显示的二叉搜索树,中序遍历出来的结果如下
[1,3,4,6,7,8,10,14,13] 有序序列其次,二叉搜索树只支持增删查,并不支持改,因为随意修改会导致这棵树可能不满足二叉搜索树的条件,比如将上图中的14改为9,它就不是二叉搜索树了,这一点很好理解!
需要注意的是：二叉搜索树中不能出现值相同的节点,若插入时出现值相同的节点就直接返回false,插入失败!
为什么使用二叉搜索树？
主要优势在于平均时间复杂度：
查找（Search）: O(log n)
插入（Insert）: O(log n)
删除（Delete）: O(log n)
这比在数组或链表中进行这些操作（通常是O(n)）要快得多。当然，这是在树保持“平衡”的理想情况下。如果树退化成一条链（例如，你一直插入递增的数字），最坏情况会变为O(n)。（高级的平衡BST如AVL树、红黑树就是为了解决这个问题而生的，今天我们只讨论基础BST）。
📕3、二叉搜索树的操作及实现
在C++中实现BST的节点
万事开头难，我们先从构建“砖块”开始——树节点。
template <typename K>
class BSTreeNode {
public:
K _data; // 节点存储的数据
BSTreeNode<K>* _left; // 指向左子节点的指针
BSTreeNode<K>* _right; // 指向右子节点的指针
// 构造函数
BSTreeNode(const K& value) : _data(value), _left(nullptr), _right(nullptr) {}
};代码解释：
我们使用了模板（template），这样我们的BST就可以存储任意数据类型（int, string, double等）。
每个节点包含三部分：
data: 存储的核心数据。
left: 一个指针，指向比当前节点值小的子树（左子树）。
right: 一个指针，指向比当前节点值大的子树（右子树）。构造函数初始化节点，并将左右指针设为
nullptr（空），表示这是一个叶子节点。
✨BST的核心操作（重点！）
现在我们来为BST这个“分拣系统”编写管理程序。我们将创建一个BST类来封装所有操作。
template <typename T>
class BSTree {
typedef BSTreeNode<T> Node;
public:
bool insert(const T& value) {}
bool search(T value) {}
void inorder(Node* root) {}
void inorder()
{}
void deleteValue(T value) {}
private:
Node* _root = nullptr; // 树的根节点
};✨A. 插入操作
思想： 从根开始，比较要插入的值与当前节点的值，根据“左小右大”规则递归地找到正确的位置。
bool insert(const T& value) {
if (_root == nullptr)
{
_root = new Node(value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)//双指针法的根本目的解决的就是cur，因为我们无法让cur在要插入节点的上个节点停下来，因为左节点右节点都有可能为空
{
if (cur->_data > value)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_data < value)
{
parent = cur;
cur = cur->_right;
}
else
return false;;
}
cur = new Node(value);
if (value > parent->_data)
parent->_right = cur;
else
parent->_left = cur;
return true;
}示例： 依次插入 50, 30, 70, 20, 40, 60, 80
树的结构:
50 / \ 30 70 / \ / \ 20 40 60 80代码解释：
- 这里必须要使用双指针法，因为插入之后需要之前的节点即所插入节点的父节点链接到该节点
- 需要注意的是二叉搜索树的插入是不会动之前已经插入的节点，小就放入左树，大就放入右树，相等就返回false，二叉搜索树里不存在相等的数值。
✨B. 查找操作
思想： 和插入类似，利用BST的性质快速缩小搜索范围。
bool search(T value) {
Node* cur = _root;
while (cur)
{
if (value == cur->_data)
{
return true;
}
else if (value > cur->_data)
{
cur = cur->_right;
}
else
cur = cur->_left;
}
return false;
}✨C. 遍历 - 中序遍历
BST有一个非常重要的特性：中序遍历（左-根-右）会产生一个有序的序列。
void inorder(Node* root) {
if (root == nullptr)
return;
inorder(root->_left);
cout << root->_data << " ";
inorder(root->_right);
}
void inorder()
{
inorder(_root);
cout << endl;
}✨D. 删除操作（最复杂）
删除操作是最复杂的，需要分三种情况来进行讨论，我们慢慢来分析：
-
被删除的节点无孩子
这种情况是最简单的，直接删除它，并将其父节点的对应指针设为
nullptr。
-
要删除的节点只有一个子节点：
删除该节点，并将其父节点的指针指向它的那个子节点。相当于“绕过”被删除的节点。
void deleteValue(T value) {
Node* cur = _root;//注意
Node* parent = cur;
while (cur->_data != value)
{
if (value > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else if(value < cur->_data)
{
parent = cur;
cur = cur->_left;
}
if (!cur)//注意
return;
}
if (cur->_left == nullptr || cur->_right == nullptr)
{
if (cur == parent->_left && !cur->_left)
{
parent->_left = cur->_right;
delete cur;
}
else if (cur == parent->_left && !cur->_right)
{
parent->_left = cur->_left;
delete cur;
}
else if (cur == parent->_right && !cur->_right)
{
parent->_right = cur->_left;
delete cur;
}
else if (cur == parent->_right && !cur->_left)
{
parent->_right = cur->_right;
delete cur;
}
else//注意
{
delete cur;
_root = nullptr;
}
}
}1. 这里需要格外注意被删除节点的孩子需要连接到被删除节点的父节点的左还是右，虽然我们心知肚明，但是当真正写代码的时候特别容易忽略，需要注意。
2. 还有一点需要注意，如果Node* parent = cur;初始的parent设为nullptr就会产生错误，如下面：
如果我们删除的是8，那就完了，parent就不会进入循环里，也就得不到更新，下面对nullptr解引用就会产生错误。
3. 当最后只有一个节点的时候，删除了之后我们要及时对类里面的root进行更新防止产生野指针的问题
虽然分成了两种情况但是，
被删除的节点无孩子也可归类到要删除节点只有一个子节点上，我们可以把nullptr当作一个子节点嘛，这段代码逻辑比较清晰，我们继续看下面的重头戏。
-
要删除的节点有两个子节点
这种是最复杂的情况，不再是简单的指向问题了，这里我使用的是一个常用的方法:
替换法：
-
策略：找到该节点右子树中的最小节点（或左子树中的最大节点）的值，用这个值替换要删除的节点的值。
-
然后，类似上述情况删除那个右子树中的最小节点（因为它现在已经被复制到上面了，原来的位置需要删除，并且它肯定没有左子节点，所以删除它很简单）。
解释：
依然要注意的是，删除之后，父节点该链到被删除节点的哪里，因为我们最终删除的是被删除节点右子树的最小节点那个位置（可以确定的是它的左节点一定为nullptr），但是它的右节点可不一定为nullptr需要注意。
而且更加需要注意的是父节点是右还是左进行连接，和上面情况是一样的，就像上图假如没有4，是不是用6和3去替换，那么最终就是6的右节点去链到7上。
Node* rightMinParent = cur;//注意
Node* rightMin = cur->_right;
T temp;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
temp = cur->_data;
cur->_data = rightMin->_data;
rightMin->_data = temp;
parent = rightMinParent;
cur = rightMin;
if (parent->_right == cur)//注意
{
parent->_right = cur->_right;
delete cur;
}
else
{
parent->_left = cur->_right;
delete cur;
}📕4、总结
总结与注意事项
-
核心思想：记住“左小右大”的递归定义，这是所有操作的基础。
-
效率：在平衡的情况下，BST非常高效。要避免插入有序数据导致树退化成链表。
-
内存管理：示例中省略了析构函数的完整实现，在实际项目中务必要写一个函数来递归释放所有节点，防止内存泄漏。
-
进阶学习：上面我们提到，二叉搜索树有它的优点，但是如果碰到有序的数组那就玩完，解决这个问题就是下面我们即将学习到的AVL树或红黑树，它们是能自我平衡的BST，保证了最坏情况下也是O(log n)的性能。C++标准库中的
std::set和std::map就是基于红黑树实现的。
敬请期待吧！
拓展链接:二叉搜索树的全部代码
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
60
0- 0
已为社区贡献12条内容
所有评论(0)