1. 查找
利用二叉查找树左小右大的性质,可以很容易实现查找任意值和最大/小值。
BSTNode * bst_search(BSTNode *node, int key)
{
while (node && key != node->key) {
if (key < node->key)
node = node->left;
else
node = node->right;
}
return node;
}
BSTNode * bst_minimum(BSTNode *node)
{
while (node->left != NULL)
node = node->left;
return node;
}
2. 插入
插入新结点的逻辑比较简单,关键是确定插入位置。
1. 首先为新结点分配内存并初始化。
2. 从根结点开始比较,小于已存在结点的键值则继续与其左子结点比较,
否则与其右子结点比较。一直这样比较到叶子结点从而确定插入位置。
3. 将新结点与此叶子结点关联。
void bst_insert(BSTNode **root, int key, char *val)
{
// 1.New node inserted to BST
BSTNode *newNode = malloc(sizeof(BSTNode));
newNode->left = newNode->right = NULL;
newNode->key = key;
newNode->value = val;
// 2.Locate insert location
BSTNode *pNode = NULL;
BSTNode *node = *root;
while (node != NULL) {
pNode = node;
if (key < node->key)
node = node->left;
else
node = node->right;
}
// 3.Link newNode to pNode
newNode->parent = pNode;
// Link pNode to newNode
if (pNode == NULL)
*root = newNode;
else if (key < pNode->key)
pNode->left = newNode;
else
pNode->right = newNode;
}
3. 删除
3.1 三种情况
删除二叉查找树中的结点稍微复杂一些,根据要删除结点的孩子结点的个数
,可以分为三种情况来处理:(假定要删除的结点为Z)
1. 结点Z没有孩子结点,那么直接删除Z就行了。
2. 结点Z有一个孩子结点,那么删除Z,将Z的父结点与此孩子结点(子树)关联就可以了。
(图中的a和b)
3. 结点Z有两个孩子结点,删除Z该怎样将Z的父结点与这两个孩子结点关联呢?
这种情况下不能直接删除Z,而是要用Z的后继(比Z的键值稍大的结点)来替代Z。
实现方法就是将后继从二叉树中删除,将后继的数据覆盖到Z中。
(图中的d)
图片来自《算法导论》第三版,与第二版的删除算法不太一样,而且多处理了一种特殊情况c,
即删除结点Z是二叉树的根结点。后面的删除代码是第二版的算法,在看删除代码前,先看
如何找到一个结点的后继。
3.2 后继
一个结点的后继是该结点的后一个,即比该结点键值稍大的结点。
所以,该结点右子树中的最小结点就是该结点的后继。如图结点7的后继就是9。
即可以直接从该结点的右子树中,沿左一直遍历到叶子结点从而找到最小值。
但如果该结点没有右孩子怎么办?例如结点13的后继。
结点没有右孩子,说明该结点在子树中是最大值。
那么就要找到13所在子树的父结点,并且:
1. 该子树的是这个父结点的左孩子。
2. 高度最低的这样的父结点。
BSTNode * bst_successor(BSTNode *node)
{
if (node->right != NULL)
return bst_minimum(node);
BSTNode *sucNode = node->parent;
while (sucNode != NULL && node == sucNode->right) {
node = sucNode;
sucNode = sucNode->parent;
}
return sucNode;
}
3.3 删除
学会了如何找到任意结点的后继,现在接着说二叉查找树的结点删除。
对于情况3,要删除结点Z的左右孩子都存在的情况,要用Z的后继要替代Z。
这需要先删掉后继,那如果Z的后继也有两个孩子怎么办?
这种情况是不可能的。习题12.2-5要证明的就是:如果二叉查找树中的
某个结点有两个子女,则其后继没有左子女,其前趋没有右子女。
简单地想,后继的左子女比后继小,结点与后继之间是不可能有其他结点的。
删除的步骤:
1. 确定实际要删除的结点是Z还是Z的后继。
2. 实际删除结点的孩子,Z的左/右孩子或者后继的右孩子。
3. 将实际要删除结点的父结点与其孩子关联。
4. 如果实际删除的是后继,则把后继中的数据拷贝到Z,替换它。
BSTNode * bst_delete(BSTNode **root, BSTNode *delNode)
{
// Real delete node: delNode or its successor
// (if delNode has both left and right child)
BSTNode *realDelNode;
if (delNode->left && delNode->right)
realDelNode = bst_successor(delNode);
else
realDelNode = delNode;
// Child of real delete node
BSTNode *childNode;
if (delNode->left)
childNode = realDelNode->left;
else
childNode = realDelNode->right;
// Link realDelNode child and parent
if (childNode)
childNode->parent = realDelNode->parent;
if (realDelNode->parent == NULL)
*root = childNode;
else if (realDelNode == realDelNode->parent->left)
realDelNode->parent->left = childNode;
else
realDelNode->parent->right = childNode;
// Copy successor data to delNode (override)
// if real delete node is not delNode but its successor
if (realDelNode != delNode) {
delNode->key = realDelNode->key;
delNode->value = realDelNode->value;
}
return realDelNode;
}
分享到:
相关推荐
源码实现了图片上传功能,可供相关功能开发的小伙伴参考学习使用。
工作总结,新年计划,岗位总结,工作汇报,个人总结,述职报告,范文下载,新年总结,新建计划。
提供的源码资源涵盖了安卓应用、小程序、Python应用和Java应用等多个领域,每个领域都包含了丰富的实例和项目。这些源码都是基于各自平台的最新技术和标准编写,确保了在对应环境下能够无缝运行。同时,源码中配备了详细的注释和文档,帮助用户快速理解代码结构和实现逻辑。 适用人群: 这些源码资源特别适合大学生群体。无论你是计算机相关专业的学生,还是对其他领域编程感兴趣的学生,这些资源都能为你提供宝贵的学习和实践机会。通过学习和运行这些源码,你可以掌握各平台开发的基础知识,提升编程能力和项目实战经验。 使用场景及目标: 在学习阶段,你可以利用这些源码资源进行课程实践、课外项目或毕业设计。通过分析和运行源码,你将深入了解各平台开发的技术细节和最佳实践,逐步培养起自己的项目开发和问题解决能力。此外,在求职或创业过程中,具备跨平台开发能力的大学生将更具竞争力。 其他说明: 为了确保源码资源的可运行性和易用性,特别注意了以下几点:首先,每份源码都提供了详细的运行环境和依赖说明,确保用户能够轻松搭建起开发环境;其次,源码中的注释和文档都非常完善,方便用户快速上手和理解代码;最后,我会定期更新这些源码资源,以适应各平台技术的最新发展和市场需求。
IMG_20240426_195457.jpg
Excel数据看板,Excel办公模板,Excel模板下载,Excel数据统计,数据展示
A Confidence-Guided Automated System for Non-emergency Calls.pdf
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
杭州电子科技大学,期末考试资料,计算机专业期末考试试卷,试卷及答案,数据结构。
对保险业中人工智能的监管: 平衡消费者保护与创新.pdf
重庆大学期末考试试卷,重大期末考试试题,试题及答案
震惊,师专男大竟然在夜深人静的夜晚写下了这些普通人都看不懂的东西,内容是...
一款支持侧边导航栏的网页导航APP源码,风格简约为主,可以通过远程文档进行远程控制列表,浏览器拥有检测下载的功能。,配置较为简单,适合入门小白学习参考。 导航软件iApp源码V3+配置教程 配置教程在mian.iyu的载入事件里面
该数据集和完整代码主要实现《基于CNN模型实现土壤湿度检测》,适用于正在学习深度学习、神经网络以及计算机、农业自动化等相关专业的伙伴们。在现代农业和环境监测中,研究土壤湿度数据来预测未来的湿度趋势十分重要。资源中的CNN模型可能仍不够完善,大家可以继续修改完善,不断研究其他的内容。感谢大家的支持和交流,你们的支持也是我前进的十足动力!
重庆大学期末考试试卷,重大期末考试试题,试题及答案
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
【基于Springboot+Vue的Java毕业设计】银行账目账户管理系统项目实战(源码+录像演示+说明).rar 【项目技术】 开发语言:Java 框架:Spingboot+vue 架构:B/S 数据库:mysql 【演示视频-编号:305】 https://pan.quark.cn/s/8dea014f4d36 【实现功能】 用户信息管理,存取业务管理,公告信息管理,挂失信息管理,账户信息管理等
工作总结,新年计划,岗位总结,工作汇报,个人总结,述职报告,范文下载,新年总结,新建计划。
智能机械装备制造信息化整体解决方案.pptx
杭州电子科技大学,期末考试资料,计算机专业期末考试试卷,试卷及答案,数据结构。
Unity在打包后仍能看到控制台输出,甚至通过命令调用绑定好的函数,调试游戏的强大助手!