dw做门户网站,网站底部流程,wordpress如何更改页面显示字体,服装设计公司logo专栏引入#xff1a; 哈喽大家好#xff0c;我是野生的编程萌新#xff0c;首先感谢大家的观看。数据结构的学习者大多有这样的想法#xff1a;数据结构很重要#xff0c;一定要学好#xff0c;但数据结构比较抽象#xff0c;有些算法理解起来很困难#xff0c;学的很累…专栏引入 哈喽大家好我是野生的编程萌新首先感谢大家的观看。数据结构的学习者大多有这样的想法数据结构很重要一定要学好但数据结构比较抽象有些算法理解起来很困难学的很累。我想让大家知道的是数据结构非常有趣很多算法是智慧的结晶我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏在这里我将把数据结构内容以有趣易懂的方式展现给大家。 1.二叉树 生活中我们经常会遇到管理大量数据的情况比如图书馆书记的分类。而二叉树这种数据结构正是用来解决这种问题的当我们阅读书时书中的每个条目都有专门分类和子分类为了更好的组织这些内容需要使用一种高效的数据结构来存储和访问信息。下面举个简单的例子来引入二叉树我们在中学学习生物时知道了植物主要分为种子植物、苔藓植物等。那它们是如何进行分类的呢我们看下面这张图片 通过这种方式我们可以逐级展开二叉树更详细的组织植物分类的信息每个节点都代表一个特定的分类而子节点则代表该分类的下一级分类。这样我们可以更加轻松的查找和比较不同的植物分类信息。下面我们就来揭开二叉树的神秘面纱。
1.1二叉树的定义
二叉树是nn0个节点的有限集合该集合或者为空集合称为空二叉树或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。在下面的图中左边的就是一棵二叉树而右边的因为它的F节点有3个子节点所以它不是二叉树。 1.2二叉树的特点 二叉树具有以下几个特点
每个节点最多有两个子节点所以二叉树中不存在度大于2的节点。注意不是一定要有两个节点而是最多有两个节点没有节点或者只有一个节点也是可以滴。左子树和右子树是有顺序的次序不能颠倒因此二叉树是有序树。即使结构中某节点只有一个子节点也要区分它是左节点还是右节点。
二叉树具有以下五种基本形态空二叉树、只有一个根节点、根节点只有左子树、根节点只有右子树、根节点既有左子树又有右子树。 1.3特殊的二叉树
1.3.1斜树
斜树顾名思义斜树一定是斜的但是向哪里斜还是有讲究的。所有节点都只有左子树的二叉树的叫做左斜树所有节点都只有右子树的二叉树叫做右斜树这两者统称为斜树。在上一张图中根节点只有左子树和根节点只有右子树就是左斜树和右斜树的一个简单例子。斜树也有很明显的特点就是每一层只有一个节点节点个数和二叉树的深度相同。肯定也有人好奇这也叫树这不和线性表一样吗确实线性表可以理解成树的一种极其特殊的表现形式。
1.3.2满二叉树
我们通常举例子都是参差不齐的二叉树那是否存在完美的二叉树呢我们看下面这张图片 看来完美的二叉树是存在的。在一棵二叉树中如果所有分支节点都存在左子树和右子树并且所有叶子都在一层上这样的二叉树叫做满二叉树。下面就是一个满二叉树从样子上看就感觉它很完美 单是每一个节点都存在左右子树不能算满二叉树还必须要所有叶子都在一层上这样才能做到整棵树的平衡。因此满二叉树的特点有
叶子只能出现在最底层出现在其他层就不能达到平衡状态。除了叶子节点外每个节点都有两个子节点。即所有非叶子节点的度都为2.在同样深度的二叉树中满二叉树的节点个数最多叶子数最多。
满二叉树的每一层都是满的没有任何缺失节点。由于每个节点都具有两个子节点满二叉树的平衡性很好。这使得在满二叉树上执行搜索、插入和删除等操作的平均时间复杂度非常高效。在满二叉树中从根节点到任意一个叶子节点的路径长度都相同是最短的路径。满二叉树常用于堆数据结构。满二叉树在实际应用中比较少见因为它要求节点数必须是2的幂次方而真实的数据往往不具备这样的特点。
1.3.3完全二叉树
对一棵具有n个节点的二叉树进行层序编号如果编号为i1≤i≤n的节点与同样深度的满二叉树中的编号为i的节点在二叉树中的位置完全相同则这棵二叉树称为完全二叉树。如下图 在理解时我们要注意区分满二叉树和完全二叉树。首先从字面上区分“完全”和“满”的区别满二叉树一定是一棵完全二叉树完全二叉树不一定是满的。其次完全二叉树的所有节点和同样深度的满二叉树它们按层序编号相同的节点是一一对应的这个关键词是按层序编号。像下面的二叉树中因为5节点没有右子树只有左子树使得按层序编号的第11个编号空档了它不是完全二叉树 只有下面图中的树尽管它不是满二叉树但编号是连续的所以它是完全二叉树 这里我们就可以总结出完全二叉树的一些特点
叶子节点只能出现在最后两层。最下层的叶子节点一定是集中在左部连续位置。倒数第二层如果有叶子节点一定都在右部连续位置。如果节点的度为1则该节点只有左孩子及不存在右子树的情况。同样节点数的二叉树完全二叉树的深度最小。
通过上面的理解我们也知道了一个判断二叉树是否是完全二叉树的方法那就是看树的示意图给每个节点按照满二叉树的结构逐层顺序编号如果编号出现空挡就说明不是完全二叉树反之就是。完全二叉树在实际应用中较为常见它具有以下的优点
节点的存储更加高效由于完全二叉树的特点可以使用数组来存储节点。这样可以大大节省存储空间因为不需要为每个节点额外存储左右子节点的指针。访问效率更高由于节点的存储更加高效可以使用数组的索引来访问节点。这样可以实现随机访问访问的时间复杂度是O(1)。而在其他类型的二叉树中如果要找到某个节点需要从根节点出发进行遍历访问的时间复杂度较高。
1.4二叉树的性质
1.4.1二叉树的性质1
在二叉树的第i层至多有个节点i≥1。这个性质很容易理解我们观察一下满二叉树 第一层是根节点只有一个所以1。第二层有两个2。第三层有四个4。第四层有八个8。通过数据归纳法的论证我们可以很轻松的得出在二叉树的第i层上至多有个节点i≥1的结论。这个性质的重要性在于它给出了二叉树的每一层上节点数量的上限。通过这个性质我们可以更好地理解和分析二叉树的结构。同时这个性质也为二叉树的遍历、搜索等操作提供了重要的依据和限制。
1.4.2二叉树的性质2
深度为k的二叉树至多有个节点k≥1。这里一定要注意是后再减1而不是。如果不注意的话很容易和性质1搞混。深度为k也就是有k层的二叉树我们接着以上面那个满二叉树为例来看如果只有一层至多有个节点。如果只有两层至多有个节点。如果只有三层至多有个节点。如果只有四层至多有个节点通过数据归纳法我们可以得出二叉树的深度为k层此二叉树至多有个节点。
1.4.3二叉树的性质3
对于任何一棵二叉树如果其终端节点数为度为2的节点数为则。这是一个非常重要的性质首先我们从二叉树的构建过程一步一步来理解它 首先我们先看只有一个根节点的时候度为0的节点个数n01度为2的节点的个数为n20。我们设度为1的节点的个数为n1接着我们给根节点加一个节点这时候一定会减少一个度为0的节点一个度为0的节点变为度为1的节点然后再加一个度为0的节点新增的节点因为没有子节点所以增加一个度为0的节点度为0的节点个数变化之后和之前的个数一样所以n0仍为1n2仍为0。然后我们再加一个节点这时候会减少一个度为1的节点然后增加一个度为0的节点和一个度为2的节点 度为1的节点变来。通过这个规律我们可以发现度为0的节点比度为2的节点多1个即n0n21。
同时我们也可以发现树节点的总数为nn0n1n2。通过下图的例子节点总数为10它是由A、B、C、D度为2的节点F、G、H、I、J度为0的叶子节点和E这个度为1的节点组成的。总和为41510。 因为这个性质很重要刷题时会经常出现考察这个性质的题我从网上找了两个试题来帮助大家对这个性质加深印象 1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 答案C 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 答案A 解析根据题意我们可以知道n0n1n22nn0n21所以n0n1n0-12n即 2n0n1-12n我们在接着分析这棵树是一个完全二叉树所以度为1的节点个数为0或 1因为n0、n1、n2的值为整数所以我们可以得出n1为1然后解开这个方程就知 道n0的值为n即叶子节点个数为n。 1.4.4二叉树的性质4
具有n个节点的完全二叉树的深度h||1这里的 |x| 表示不大于x的最大整数。由满二叉树的定义我们可以知道深度为h的满二叉树的节点数n一定为因为这是最多的节点个数。那么对于n倒推可以得到满二叉树的深度为h完全二叉树我们前面也提到过它是一棵具有n个节点的二叉树如果按照层序编号后与同样深度的满二叉树中编号节点在二叉树中的位置完全相同那他就是完全二叉树也就是说它的叶子节点只会出现在最下面两层它的节点数一定小于等于同等深度的满二叉树的节点数但一定多于即满足由于节点数n是整数意味着意味着所以不等式两边取对数得到而h作为深度也是整数因此h||1。
