广西城乡与住房建设厅网站,房产网站栏目建设,wd ex4 安装wordpress,wordpress被镜像当看到这里的时候#xff0c;相信你的链表#xff0c;队列#xff0c;栈学的也差不多可以了#xff0c;那么接下来让我们一起进入树的学习吧#xff01;
一.树的概念以及一些知识记忆
树的定义#xff1a; 树是一种 非线性 的数据结构#xff0c;它是由 n #xff08…当看到这里的时候相信你的链表队列栈学的也差不多可以了那么接下来让我们一起进入树的学习吧
一.树的概念以及一些知识记忆
树的定义 树是一种 非线性 的数据结构它是由 n n0 个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的 。 树 有一个 特殊的结点称为 根结点 根节点没有前驱结点 除根节点外 其余结点被分成 M(M0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm 其中每一个集合 Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有 0 个或多个后继 因此树是 递归定义 的。 注意 树形结构中 子树之间不能有交集否则就不是树形结构 如图 它们都不是树原因就在于出现了子树有交集的情况。 树相关的知识点 让我们根据这幅图来认识下树相关的知识 节点的度 一个节点含有的子树的个数称为该节点的度 如上图 A 的为 6 叶节点或终端节点 度为 0 的节点称为叶节点 如上图 B 、 C 、 H 、 I... 等节点为叶节点 非终端节点或分支节点 度不为 0 的节点 如上图 D 、 E 、 F 、 G... 等节点为分支节点 双亲节点或父节点 若一个节点含有子节点则这个节点称为其子节点的父节点 如上图 A 是 B 的父节点别问为啥不叫母亲节点我也不知道 孩子节点或子节点 一个节点含有的子树的根节点称为该节点的子节点 如上图 B 是 A 的孩子节点 兄弟节点 具有相同父节点的节点互称为兄弟节点 是指亲兄弟如上图 B 、 C 是兄弟节点 树的度 一棵树中最大的节点的度称为树的度 如上图树的度为 6 高度是从1开始计的即树根为1. 节点的层次 从根开始定义起根为第 1 层根的子节点为第 2 层以此类推 树的高度或深度 树中节点的最大层次 如上图树的高度为 4 堂兄弟节点 双亲在同一层的节点互为堂兄弟如上图 H 、 I 互为兄弟节点 节点的祖先 从根到该节点所经分支上的所有节点如上图 A 是所有节点的祖先 子孙 以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是 A 的子孙 森林 由 m m0 棵互不相交的树的集合称为森林 二.树的表示方法 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了 既然保存值域也要保存结点和结点之间 的关系有以下表示方法 2.1.指针数组表示 #define N 10
struct TreeNode
{int date;struct TreeNode* arr[N];
}; 2.2顺序表表示 struct TreeNode
{int date;SeqList child;
}; 2.3.左孩子右兄弟表示法 struct TreeNode
{int date;struct TreeNode* leftchild;struct TreeNode* rightbrother;
}; 这是树的最优表示法。 三.树运用的举例 大家都知道Linux系统吧如下图 它就是一颗树但是也可以变成图以后要学的 windows就是图。 四.一些特殊的树重点 4.1.二叉树概念及结构 一棵二叉树是结点的一个有限集 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 二叉树可以最多有俩个子树但是亦可以一个或者没有。想象成二胎计划不一定要生两个孩子但是不能超过两个孩子 注意事项 1.二叉树不存在度大于 2 的结点 2. 二叉树的 子树有左右之分次序不能颠倒因此二叉树是有序树 4.2.特殊的二叉树 1. 满二叉树 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K 且结点总数是2^k-1)则它就是满二叉树。 2. 完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K的有n 个结点的二叉树当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树 4.3.二叉树的性质 1. 若规定根节点的层数为 1 则一棵非空二叉树的 第i层上最多有 (2^i-1)) 个结点. 2. 若规定根节点的层数为 1 则 深度为 h 的二叉树的最大结点数是(2^h-1) 1. 若 i0 i 位置节点的双亲序号 (i-1)/2 i0 i 为根节点编号无双亲节点 2. 若 2i1n 左孩子序号 2i1 2i1n 否则无左孩子 3. 若 2i2n 右孩子序号 2i2 2i2n 否则无右孩子 4.3.二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。(大家看过我的数据结构基础知识的应该都了解过物理结构的分类 1.顺序存储 顺序结构存储就是使用 数组来存储 一般使用数组 只适合表示完全二叉树 因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组在逻辑上是一颗二叉树。 2. 链式存储重点 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链。 四.堆 堆的定义 如果有一个关键码的集合 把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 大堆要求任何一个父亲孩子 小堆要求任何一个父亲孩子 堆的同一层次不一定有序。 大家可以看看下面这题 下列关键字序列为堆的是 A 100 , 60 , 70 , 50 , 32 , 65 B 60 , 70 , 65 , 50 , 32 , 100 C 65 , 100 , 70 , 32 , 50 , 60 D 70 , 65 , 100 , 32 , 50 , 60 E 32 , 50 , 100 , 70 , 65 , 60 F 50 , 100 , 70 , 65 , 60 , 32 答案是A 经过这些知识介绍大家对树和堆有了一定的了解下次我们就来实现他们。 最后祝福大家平安夜健健康康平平安安生活愉快。
