二叉树的先序遍历代码_二叉树的先序遍历代码

二叉树的先序遍历代码_二叉树的先序遍历代码二叉搜索树 —— 不能说完全没用,至少思想是经典的前言我们知道,「 顺序表 」 可以 「 快速索引 」 数据,而 「 链表 」 则可以快速的进行数据的「 插入 和 删除 」。那么,有没有一种数据结构,可以快速的实现 「 增 」「 删 」「 改 」「 查 」

二叉搜索树 —— 不能说完全没用,至少思想是经典的   前言   我们知道,「 顺序表 」 可以 「 快速索引 」 数据,而 「 链表 」 则可以快速的进行数据的「 插入 和 删除 」。那么,有没有一种数据结构,可以快速的实现 「 增 」「 删 」「 改 」「 查 」 呢? 本文,我们就来聊一下一种 「 树形 」 的数据结构,它既有链表的快速插入与删除的特点,又有顺序表快速查找的优势。它就是:「 二叉搜索树 」
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码二叉搜索树的查找
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码二叉搜索树的删除
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码二叉搜索树的插入   一、二叉树的概念   在学习二叉搜索树之前,我们首先需要了解下什么是二叉树。英雄哪里出来:二叉树 —— 用递归来描述数据结构   二、二叉搜索树的概念   1、定义   二叉搜索树,又称为二叉排序树,二叉查找树,它满足如下四点性质:   1)空树是二叉搜索树; 2)若它的左子树不为空,则左子树上所有结点的值均小于它根结点的值; 3)若它的右子树不为空,则右子树上所有结点的值均大于它根结点的值; 4)它的左右子树均为二叉搜索树;
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   如图所示,对于任何一棵子树而言,它的根结点的值一定大于左子树所有结点的值,且一定小于右子树所有结点的值。   2、用途   从二叉搜索树的定义可知,它的前提是二叉树,并且采用了递归的方式进行定义,它的结点间满足一个偏序关系,左子树根结点的值一定比父结点小,右子树根结点的值一定比父结点大。   正如它的名字所说,构造这样一棵树的目的是为了提高搜索的速度,如果对二叉搜索树进行中序遍历,我们可以发现,得到的序列是一个递增序列。
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   3、数据结构   我们用孩子表示法来定义一棵二叉搜索树的结点。如下:   (1) 二叉搜索树结点的值,注意,这里的类型其实可以是任意类型,只要这种类型支持 关系运算符 的比较即可,本文为了把问题简单话,一律采用整数进行讲解。(2) 二叉搜索树结点的左儿子结点的指针,没有左儿子结点时,值为;(3) 二叉搜索树结点的右儿子结点的指针,没有右儿子结点时,置为;   4、结点创建   结点创建就是给结点分配一块内存,并且填充它的数据域和指针域,然后返回这个结点。C语言实现如下:   三、二叉搜索树的操作   1、查找   二叉搜索树的查找指的是:在树上查找某个数是否存在,存在返回,不存在返回。   1)算法原理   对于要查找的数,从根结点出发,总共四种情况依次判断:   1)若为空树,直接返回;   2)的值 等于 树根结点的值,则直接返回;   3)的值 小于 树根结点的值,说明对应的结点不在根结点,也不在右子树上,则递归返回左子树的 查找 结果;   4)的值 大于 树根结点的值,说明对应的结点不在根结点,也不在左子树上,则递归返回右子树的 查找 结果;   2)动图演示   如图所示,代表的是从一个二叉搜索树中查找一个值为 3 的结点。一开始, 3 比根结点 5 小,于是递归访问左子树;还是比子树的根结点 4 小,于是继续递归访问左子树;这时候比根结点 2 大,于是递归访问右子树,正好找到值为 3 的结点,回溯结束查找。
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   3)源码详解   (1) 这个函数用于查找以为根结点的树中是否存在值为这个结点;(2) 空树是不可能存在值为的结点的,直接返回;(3) 一旦发现有值为的结点,直接返回;(4) 的值 小于 树根结点的值,说明对应的结点不在根结点,也不在右子树上,则递归返回左子树的 查找 结果;(5) 的值 大于 树根结点的值,说明对应的结点不在根结点,也不在左子树上,则递归返回右子树的 查找 结果;   2、插入   二叉搜索树的插入指的是:将给定的值生成结点后,插入到树上的某个位置,并且保持这棵树还是二叉搜索树。   1)算法原理   对于要插入的数,从根结点出发,总共四种情况依次判断:   1)若为空树,则创建一个值为的结点并且返回;   2)的值 等于 树根结点的值,无须执行插入,直接返回根结点;   3)的值 小于 树根结点的值,那么插入位置一定在 左子树,递归执行插入左子树的过程,并且返回插入结果作为新的左子树;   4)的值 大于 树根结点的值,那么插入位置一定在 右子树,递归执行插入右子树的过程,并且返回插入结果作为新的右子树;   2)动图演示   如图所示,代表的是将一个值为 3 的结点插入到一个二叉搜索树中。一开始, 3 比根结点 5 小,于是递归插入左子树;还是比子树的根结点 4 小,于是继续递归插入左子树;这时候比根结点 2 大,于是递归插入右子树,右子树为空,则直接生成一个值为 3 的结点,回溯结束插入。
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   3)源码详解   (1) 函数用于将值为的结点插入到以为根结点的子树中;(2) 如果是空树,则创建一个值为的结点并且返回;(3) 的值 等于 树根结点的值,无须执行插入,直接返回根结点;(4) 的值 小于 树根结点的值,那么插入位置一定在 左子树,递归执行插入左子树的过程,并且返回插入结果作为新的左子树;(5) 的值 大于 树根结点的值,那么插入位置一定在 右子树,递归执行插入右子树的过程,并且返回插入结果作为新的右子树;   3、删除   二叉搜索树的删除指的是:在树上删除给定值的结点。   1)算法原理   删除值为的结点的过程,从根结点出发,总共四种情况依次判断:   1)空树,不存在结点直接返回空树;   2)的值 小于 树根结点的值,则需要删除的结点一定不在右子树上,递归调用删除左子树的对应结点;   3)的值 大于 树根结点的值,则需要删除的结点一定不在左子树上,递归调用删除右子树的对应结点;   4)的值 等于 树根结点的值,相当于是要删除根结点,这时候又要分三种情况:   4.1)当前树只有左子树,则直接将左子树返回,并且释放当前树根结点的空间;   4.2)当前树只有右子树,则直接将右子树返回,并且释放当前树根结点的空间;   4.3)当左右子树都存在时,需要在右子树上找到一个值最小的结点,替换新的树根,而其它结点组成的树作为它的子树,并且在子树中删掉这个最小的结点,而这一步删除的过程正是继续递归调用结点删除的过程;   2)动图演示   如图所示,下图展示的是,从这棵树删除根结点 5 的过程。首先,由于它有左右儿子结点,所以这个过程,根结点并不是真正的删除。而是从右子树中找到最小的结点 6,替换根结点,并且从根结点为 7 的子树中删除 6 的过程。由于 6 没有子结点所以这个过程就直接结束了。
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   3)源码详解   3.1)接口简介   在介绍二叉搜索树的结点删除算法前,我们首先需要知道以下四个接口:   (1) :查找为根的树中,值最小的那个结点的值,根据二叉搜索树的性质,如果左子树存在,则必然存在更小的值,递归搜索左子树;如果左子树不存在,则根结点的值必然最小,直接返回,具体实现见下文;(2) :在为根的树中,删除值为的结点,是我们需要实现的删除接口,具体实现见下文;(3) :在为根的树中,将根结点删除,并且使得剩下的树还是二叉搜索树,具体实现见下文;   3.2)查找最小结点   (1) 如果左子树存在,则递归调用左子树的查找最小结点接口;(2) 如果左子树不存在,则当前根结点的值一定是最小的,直接返回接口;   3.3)删除给定结点   (1) 如果为空树,则直接返回空结点;(2) 如果需要删除的结点,是这棵树的根结点,则直接调用接口,下文会介绍它的实现;(3) 如果需要删除的结点的值 小于 树根结点的值,则需要删除的结点必定在左子树上,递归调用左子树的删除,并且将返回值作为新的左子树的根结点;(4) 如果需要删除的结点的值 大于 树根结点的值,则需要删除的结点必定在右子树上,递归调用右子树的删除,并且将返回值作为新的右子树的根结点;(5) 最后,返回当前树的根结点;   3.4)删除给定二叉搜索树的根结点,并且返回新的树根   (1) 如果左子树为空,则用右子树做为新的树根;(2) 如果右子树为空,则用左子树作为新的树根;(3) 否则,当左右子树都为非空时,利用,从右子树上找出最小的结点,作为新的根,并且在右子树中删除对应的结点,删除过程就是递归调用的过程;   4、构造   二叉搜索树的构造就是:给定一个数组序列,构造出一个棵二叉搜索树。   1)算法原理   原理比较简单,一开始是一棵空树,然后遍历数组,对每个素生成一个结点,不断执行插入操作,并且返回新的树根,就完成了构造的过程。   2)源码详解   (1) 初始化空树;(2) 根据数组给定顺序执行插入树的操作;   插入过程需要明确一点,就是如果给定的数组是严格递增,或者严格递减,就会导致每次插入都要遍历树的所有结点,这样就使得整个插入过程的时间复杂度变成了 O(n^2),改善的方法有几种: 方法1:随机将数组打乱顺序,再执行插入; 方法2:每次插入后,变换成平衡树,对于平衡树相关内容,下篇文章会详细讲解;   四、二叉搜索树的遍历   1、先序遍历   给定一个某个二叉搜索树的先序遍历序列,构造出一棵二叉搜索树,方法如下:   1)首先,考虑先序遍历的特点:先访问根结点,再依次访问左右子树;所以,第一个结点一定是根结点;   2)然后,数组往后遍历的过程中,遇到的所有小于当前根结点的结点,都必然是左子树上的结点,后面的结点必然是右子树的(当然,如果检测到后面的结点有比这个根结点小的,则这个序列无法构造出一棵二叉搜索树);   3)遍历找到左右子树的分界点后,就可以进行左右子树递归计算了,注意递归时返回构造完的子树的根结点。   2、中序遍历   二叉搜索树的中序遍历是最常用的,一棵二叉搜索树的中序遍历是一个递增序列。   递增序列是存在单调性的,所以可以利用这个特性,在有效的时间内找出这棵树的第 k 大结点。   3、后序遍历   给定一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果,方法如下:   1)从后序遍历的定义出发,先左子树,再右子树,最后根结点。所以,这个序列的最后一个素,一定是根结点,且所有小于它的素作为左子树,所有大于它的素作为右子树。   2)如果能够分成这样两部分,则递归计算左右子树;   3)否则,在出现第一个大于 最后一个素的情况下,又出现小于 最后一个素的情况,则表示这是一种非法情况,直接返回。   五、二叉搜索树的总结   纵观二叉搜索树的查找、插入 和 删除。完全取决于二叉搜索树的形状,如果是完全二叉树或者接近完全二叉树,则这三个过程都是
O(log_2n) 的,如果是斜树,则三个过程近似操作线性表,为
O(n)
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码
二叉树的先序遍历代码_二叉树的先序遍历代码   关于 「 二叉搜索树 」 的内容到这里就结束了。如果还有不懂的问题,可以通过 「 万人千题 」上的联系方式联系作者,线上沟通交流。   本文所有示例代码均可在以下 github 上找到:github.com/WhereIsHeroFrom/Code_Templates

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/86350.html

(0)
上一篇 2024年 7月 26日 下午4:53
下一篇 2024年 7月 26日 下午5:02

相关推荐

关注微信