技术栈

主页 > 移动开发 >

C语言/C++编程学习,数据结构与算法,通俗易懂讲解,二叉搜索树插入删除

技术栈 - 中国领先的IT技术门户

C语言是面向过程的,而C++是面向对象的                                                                                                               C和C++的区别:

C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到输出(或实现过程(事务)控制)。

C++,首要考虑的是如何构造一个对象模型,让这个模型能够契合与之对应的问题域,这样就可以通过获取对象的状态信息得到输出或实现过程(事务)控制。 所以C与C++的最大区别在于它们的用于解决问题的思想方法不一样。之所以说C++比C更先进,是因为“ 设计这个概念已经被融入到C++之中 ”。

C与C++的最大区别:在于它们的用于解决问题的思想方法不一样。之所以说C++比C更先进,是因为“ 设计这个概念已经被融入到C++之中 ”,而就语言本身而言,在C中更多的是算法的概念。那么是不是C就不重要了,错!算法是程序设计的基础,好的设计如果没有好的算法,一样不行。而且,“C加上好的设计”也能写出非常好的东西。

很多小伙伴都老是会碰到疑问,其实还是基础没打扎实,这些题如果你不看答案你能知道多少呢?如果还有很多不知道就证明基础没打扎实,如果你还在入门纠结,如果你还在苦恼怎么入门!小编推荐一个学C语言/C++的学习裙【 六九九,四七零,五九六 】,无论你是大牛还是小白,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

在二叉搜索树查找一文中主要介绍了二叉搜索树的查找,本文将继续介绍其插入删除操作。二叉搜索树的插入和删除关键在于在插入和删除的过程中如何继续保持二叉搜索树的性质。

二叉搜索树结点定义如下:

插入结点

插入结点的位置对应着查找过程中查找不成功时候的结点位置,因此需要从根结点开始查找带插入结点位置,找到位置后插入即可。下图所示插入结点过程:

插入结点代码如下

小编推荐一个学C语言/C++的学习裙【 六九九,四七零,五九六 】,无论你是大牛还是小白,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

删除结点

二叉搜索树删除结点可以说是二叉搜索树中最为复杂的操作,要考虑的情况比较多,下面分情况讨论。

(1)要删除的结点z叶子结点,这是最简单的一种情况,直接修改其父节点相应指针为NULL。删除过程如下图所示:

(2)要删除的结点z为只有一个子树,让z的子树与z的父亲节点相连,删除z即可,删除过程如下图所示:

(3)要删除的结点z为有两个子树,则先找到z的后继结点y,y肯定是没有左子树的(如果y还有左子树,那么y就肯定不是z的后继结点),所以现在可以按照上面两种情况删除y结点,最后用y值代替z。整个删除过程如下图所示:


二叉搜索树删除结点的代码实现如下。

小编推荐一个学C语言/C++的学习裙【 六九九,四七零,五九六 】,无论你是大牛还是小白,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

代码中的bstree_successor(z)函数功能是找到结点z的后继结点,至于什么是后继结点以及其实现,前文二叉搜索树查找已有总结,此处不再详述。

上面就是二叉搜索树的插入和删除结点的思路和代码,大家在看代码的时候可以对着图将每种情况在自己脑中运行,比如说对于删除操作的第一种情况,它在代码中的运行流程是什么,这样可能更加容易理解。

为您提供通俗易懂的技术文章,让技术变的更简单!

这些是C/C++能做的

服务器开发工程师、人工智能、云计算工程师、信息安全(黑客反黑客)、大数据 、数据平台、嵌入式工程师、流媒体服务器、数据控解、图像处理、音频视频开发工程师、游戏服务器、分布式系统、游戏辅助等

责任编辑:admin  二维码分享:
本文标签: 结点C++删除二叉插入搜索