数据结构——“二叉搜索树”

🕗 发布于 2024-09-20 12:04 数据结构

二叉搜索树是一个很重要的数据结构，它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是O(n)，最好是O(logn)。接下来看一看它的接口函数的实现。

为了使用方便，这里采用模版的方式：

一、节点

template <class K>
struct BSnode
{
BSnode(K key)
:_key(key)
{}
K _key;
BSnode* _left = nullptr;
BSnode* _right = nullptr;
};

_key用来储存数据，_left和_right用来储存左子树和右子树的节点。

二、搜索树的类的定义

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

这里typedef了BSnode<K>为Node的类型，方便使用。并创建了根节点，缺省值为空指针。

三、搜索树的插入

搜索树的结构是左子树所有节点的值小于等于根结点的值，右子树所有节点的值大于等于根节点的值。在这里我不考虑等于的情况，即一棵树中不允许出现相同的值。代码如下：

//搜索树的插入
bool Insert(K& key)
{
Node* cur = _root;
Node* parent = nullptr;
if (cur == nullptr)
{
_root = new Node(key);
}
else
{
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

if (key > parent->_key)//插入的值大于父亲节点，那么就需要在父亲节点的右边插入
{
parent->_right = new Node(key);
}
else//插入的值小于父亲节点，那么就需要在父亲节点的左边插入
{
parent->_left = new Node(key);
}
}
return true;
}

代码大体情况如下：

1.第一次插入数据的时候，根节点指向空，需要单独讨论。

2.根节点不为空，那么就根据搜索树的特点找到最后插入的位置，申请新节点，连接新节点。

3.找不到插入的位置，即插入的数据已经存在，返回false。

四、搜索树的查找

//搜索树的查找
Node* Find(const K& key)
{
assert(_root);
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key <  key)
{
cur = cur->_right;
}
else
{
return cur;
}
}

return nullptr;
}

这段代码是根据搜索树的特点进行查找（搜索的值大于根，那么去右子树查找，小于则去左子树查找），倘若找到，返回该节点指针，找不到，返回空指针。

五、搜索树的删除

搜索树的删除偏向复杂，在我写出的代码中大致分为以下几点：

1.删除的数据在叶子节点上。

2.删除的节点不在叶子节点上，但是它的左右节点至少有一个是空。

3.删除的节点不在叶子节点上，且左右子树都不为空。

4.删除的节点在根节点，根节点至少有一个为空。

通过总结可以精简以上条件：

1.删除的节点的左右节点至少有一个为空。

2.删除的节点的左右节点都不为空。

代码如下：

//搜索二叉树的删除
bool Erase(const K& key)
{
assert(_root);
//先找到要删除的节点
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}

//找不到要删除的数据，返回false
if (cur == nullptr)return false;
//找到了

//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”
if (cur->_left == nullptr || cur->_right == nullptr)
{
//该节点是根，且且根节点至少一个子树为空
if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 
{
_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;
delete cur;
}
//该节点是左孩子
else if (cur == parent->_left)
{
//左节点为空
if (cur->_left == nullptr && cur->_right != nullptr)
{
parent->_left = cur->_right;
}
//右节点为空
else if(cur->_left != nullptr && cur->_right == nullptr)
{
parent->_left = cur->_left;
}
//左右节点均为空
else
{
parent->_left = nullptr;
}

//释放资源
delete cur;
}
//该节点是右孩子
else if (cur == parent->_right)
{
//左节点为空
if (cur->_left == nullptr && cur->_right != nullptr)
{
parent->_right = cur->_right;
}
//右节点为空
else if (cur->_left != nullptr && cur->_right == nullptr)
{
parent->_right = cur->_left;
}
//左右节点均为空
else
{
parent->_right = nullptr;
}

//释放资源
delete cur;
}

}
//处理“该节点的左右孩子均不为空”
else
{
//找到左节点的最大值
Node* Fparent = cur;
Node* Fcur = cur->_left;



while (Fcur ->_right)
{
Fparent = Fcur;
Fcur = Fcur->_right;
}
//交换节点的值
cur->_key = Fcur->_key;
//Fcur的左边有数据
if (Fcur->_left)
{
Fparent->_right = Fcur->_left;
delete Fcur;
}
//Fcur的左边没有数据
else
{

if(Fcur == Fparent->_left)
{
Fparent->_left = nullptr;
}
else
{
Fparent->_right = nullptr;
}
delete Fcur;
}

}

return true;
}

首先是先要找到删除的数据，若找不到，返回false，若找到，那么进行下一步：

找到后还有如下情况：

1.删除的节点的左右节点至少有一个为空。

对应代码：

//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”
if (cur->_left == nullptr || cur->_right == nullptr)
{
//该节点是根，且且根节点至少一个子树为空
if (parent == nullptr)//parent为空，证明输入的是根节点，且根节点至少一个子树为空 
{
_root->_left == nullptr ? _root = _root->_right : _root = _root->_left;
delete cur;
}
//该节点是左孩子
else if (cur == parent->_left)
{
//左节点为空
if (cur->_left == nullptr && cur->_right != nullptr)
{
parent->_left = cur->_right;
}
//右节点为空
else if(cur->_left != nullptr && cur->_right == nullptr)
{
parent->_left = cur->_left;
}
//左右节点均为空
else
{
parent->_left = nullptr;
}

//释放资源
delete cur;
}
//该节点是右孩子
else if (cur == parent->_right)
{
//左节点为空
if (cur->_left == nullptr && cur->_right != nullptr)
{
parent->_right = cur->_right;
}
//右节点为空
else if (cur->_left != nullptr && cur->_right == nullptr)
{
parent->_right = cur->_left;
}
//左右节点均为空
else
{
parent->_right = nullptr;
}

//释放资源
delete cur;
}

}

原理：由于删除的节点左右子树至少有一个为空，那么就可以让父节点继承被删除节点的非空节点。继承后，删除该节点。如果被删除的节点的左右子树都为空，即被删除的节点是叶子节点，那么就可以直接删除叶子节点，然后将父节点指向空。

以上代码分别对删除的节点是左子树还是右子树的情况下，删除的节点是否有左子树，是否有右子树，还是左右子树都没有进行讨论，涵盖所有情况。值得注意的是，当搜索树呈现链状的时候，如果删除的是根节点，此时的父节点是空，不能进行访问，那么需要在这里单独讨论。将根节点移动到有数据的那个子节点。

2.删除的节点的左右节点都不为空。

对应代码：

//处理“该节点的左右孩子均不为空”
else
{
//找到左节点的最大值
Node* Fparent = cur;
Node* Fcur = cur->_left;
while (Fcur ->_right)
{
Fparent = Fcur;
Fcur = Fcur->_right;
}
//交换节点的值
cur->_key = Fcur->_key;
//Fcur的左边有数据
if (Fcur->_left)
{
Fparent->_right = Fcur->_left;
delete Fcur;
}
//Fcur的左边没有数据
else
{

if(Fcur == Fparent->_left)
{
Fparent->_left = nullptr;
}
else
{
Fparent->_right = nullptr;
}
delete Fcur;
}

}

第二种情况就不能直接进行交换。因为父节点没有多余的指针指向被删除节点的左右节点。那么在这里的思想是找到一个比被删除的节点的左孩子大，右孩子小。符合条件的是：左子树的最大值，或者右子树的最小值。找到之后交换节点值。但是还是需要注意的是，找到最大值以后，分为两种情况：

a.最大值的左边为空。

b.最大值的左边不为空。

那么进行讨论：比如删除的数据是8。

a.最大值的左边为空：

这个条件下可以直接交换删除

b.最大值的左边不为空：

这种情况下就需要将父节点的右节点（最大值的位置）指向最大值的左节点。

在这段代码中：

//找到左节点的最大值
Node* Fparent = cur;
Node* Fcur = cur->_left;
while (Fcur ->_right)
{
Fparent = Fcur;
Fcur = Fcur->_right;
}

Node* Fparent = cur;的目的是避免这种情况下，空指针解引用的问题：删除的数据是3：

倘若Fparent 为空

此时Fcur已经为叶子节点（已经为3的左子树的最大值），while循环不会进而以下代码会对Fparent解引用，造成访问空指针的错误。如果将Fparent复制为cur，那么从一开始，Fparent就是Fcur的父节点，既不违反逻辑，也解决了问题。

因为此时1在父节点的左边，所以综上所述，再删除节点的同时也是需要判断被删除的节点是左节点还是右节点。

示例：

int main()
{
BSTree<int> tree;

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

for (auto f : a)
{
tree.Insert(f);
}


for (auto f : a)
{
tree.Erase(f);
tree.InTraversal();
cout << endl;
}

return 0;
}

结果（中序遍历）：

原文地址：https://blog.csdn.net/2301_79972085/article/details/142308300

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

上一篇：STM32的GPIO的八种工作模式
下一篇：基于Python的自然语言处理系列（12）：使用TorchText和LSTM进行序列到序列（seq2seq）翻译

预处理（1）（手绘）
大家好，今天给大家分享一下编译器预处理阶段，那么我们来看看。上面是一些预处理阶段的知识，那么明天给大家讲讲宏吧。
阅读更多2024-11-18
C语言项⽬实践-贪吃蛇
GetAsyncKeyState 的返回值是short类型，在上⼀次调⽤ GetAsyncKeyState 函数后，如果返回的16位的short数据中，最⾼位是1，说明按键的状态是按下，如果最⾼是0
阅读更多2024-11-18
Cache Line设计
以上代码实现了模拟的 Cache Line 结构，并包含了初始化、修改和释放内存的功能，完全符合题目中的需求描述。
阅读更多2024-11-18
Linux性能优化之火焰图简介
Linux 火焰图（Flame Graph）是一种可视化工具，用于分析程序性能问题，尤其是 CPU 使用情况。它展示了程序中函数调用的层次结构和各个调用栈占用的时间比例。本文详细介绍，包括火焰图的工作
阅读更多2024-11-18
南京邮电大学《智能控制技术》期末抢救（下）
专家系统是一个智能程序系统：具有相关领域内大量的专家知识；能应用人工智能技术模拟人类专家求解问题的思维过程进行推理，解决相关领域内的困难问题，并且达到领域专家的水平。专家系统所要解决的问题一般没有算法
阅读更多2024-11-18
pytorch基础-前向传播与反向传播
神经网络的基础，前向传播与反向传播（包含理论推导与pytorch代码）
阅读更多2024-11-18
【hacker送书第15期】AI绘画精讲与AIGC时代游戏美术设计：从入门到精通
随着人工智能技术的飞速发展，AI绘画已经成为了一个备受瞩目的领域。在这个背景下，北京大学出版社推出了一系列关于AI绘画的优秀图书，其中就包括了《AI绘画精讲：Stable Diffusion从入门到精
阅读更多2024-11-18
Electron：Menu 自定义菜单的使用、自定义右键菜单、动态创建菜单
Electron：Menu 自定义菜单的使用、自定义右键菜单、动态创建菜单
阅读更多2024-11-18
算法----二分法找出有序列表指定值
res = dichotomy(0, len(data) - 1, data, 56) # 这里max索引应该是len(data) - 1，因为索引从0开始。return dichotomy(mid
阅读更多2024-11-18
网络
第四次挥手时，客户端发出 ACK 后，会等待 2MSL（报文在网络上存在的最长时间）确保最后的 ACK 报文能够到达服务端，2MSL 之后客户端会关闭连接，服务端收到确认后也会关闭连接。IP 协议是整
阅读更多2024-11-18

数据结构——“二叉搜索树”

一、节点

二、搜索树的类的定义

三、搜索树的插入

四、搜索树的查找

五、搜索树的删除

1.删除的节点的左右节点至少有一个为空。

2.删除的节点的左右节点都不为空。

相关文章