东莞北京网站建设,小程序营销策划方案,学校网站建设公司,wordpress index 漏洞作者#xff1a;小树苗渴望变成参天大树 作者宣言#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 #xff0c;就 给 作 者 点 点 关 注 吧#xff01; 树前言一、树概念及结构1.1树的概念1.2 树的相关概念1.3 树的表示1.4树在实际中的运用… 作者小树苗渴望变成参天大树 作者宣言认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 就 给 作 者 点 点 关 注 吧 树前言一、树概念及结构1.1树的概念1.2 树的相关概念1.3 树的表示1.4树在实际中的运用表示文件系统的目录树结构二、二叉树概念及结构2.1概念2.2 二叉树的性质2.3 二叉树的存储结构2.3.1链式存储2.3.2顺序存储三、总结前言
今天我们来讲一讲非线性的一种数据结构大家肯定对这种结构充满好奇和不解今天我就带大家来解决这个问题我所将的是树以及二叉树这种结构本篇着重讲解关于树的相关概念带小白先入个门我们开始进入正文。 一、树概念及结构
1.1树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 我们来看看树的图 这是现实中的树 数据结构中的图 我们来看看那些不是树 注意树形结构中子树之间不能有交集否则就不是树形结构 1.2 树的相关概念 1.节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 2.叶节点或终端节点度为0的节点称为叶节点 如上图 B、 C、H、I…等节点为叶节点 3.非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 4.双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 5.孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 6.兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 7.树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 8.节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 9.树的高度或深度树中节点的最大层次 如上图树的高度为4 10.堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 11.节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 12.子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 13.森林由mm0棵互不相交的树的集合称为森林 相信看到这里大家对树有了一定的认识。
1.3 树的表示
我们上面知道了树是什么那我们怎么表示他呢今天我就使用图的形式来给大家展示。 我们之前学过单链表把定义单链表的结构想象成树第一个节点就是根节点其余每个节点只有一个孩子的树然后再来想一下树的定义结构。多了几个指针来存储他的孩子节点而已。 我们看到上面树的结构是非常复杂的有的人就想定义一个结构体定义指针来存储此节点的孩子节点但是我们不知道这个节点有多少个孩子你定义的这个结构体可能只适用于一个节点其余节点就不满足
有点牛人就想出来一个厉害的方法不管你有几个孩子节点我都可以给你表示出来。左孩子右兄弟 我们来看看他的具体逻辑图方便理解 具体看定义实现
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};今天我们就将树的定义关于树的操作我不做重点介绍因为树的操作不是重点我们重点操作的是二叉树接下来会介绍。 1.4树在实际中的运用表示文件系统的目录树结构 再我们文件系统里面用的最多
二、二叉树概念及结构
2.1概念 一棵二叉树是结点的一个有限集合该集合: 或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成 具体一点就是一个树的节点最多只有两个孩子或者是一个空树。 二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 我们来看看哪些是二叉树 我们再来看看现实中的二叉树 我们再来看看两种特殊的二叉树 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.2 二叉树的性质 1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1 我们使用错位相减法来解决这个证明后面有好多证明都需要使用错位相减法不会的赶紧熟悉一下 3.对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n0 n2 1; 若规定根节点的层数为1具有n个结点的满二叉树的深度h . (ps 是log以2为底n1为对数) 因为是满二叉树总结点的是2^h-1再计算的时候可以不带1所以直接取对数得深度 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 (1)若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 (2) 若2i1n左孩子序号2i12i1n否则无左孩子 (3) 若2i2n右孩子序号2i22i2n否则无右孩子 2.3 二叉树的存储结构
2.3.1链式存储
我们上面讲到树的存储结构左孩子右兄弟法那我们二叉树只有两个孩子我们可以采取定义左右孩子的指针来保存两个孩子结点这就是二叉树的链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址也成二叉链式 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}我们的链式存储还有一个存储方式是三叉链式多了一个指针域指向其父亲
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}今天我们依旧不讲他的操作我们只讲他的存储操作再之后的博客会讲到
2.3.2顺序存储
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
我们刚才讲到的性质5就派上用场了我们来看图 我们看到顺序存储只适用满二叉树这样不会造成空间浪费但是大部分时候我们看到的都是非满二叉树那么顺序存储就没有意义了吗当然不是再我接下来讲的堆的时候就会排上用场了
三、总结
今天关于树的概念以及存储方式还有二叉树的概念性质存储方式我也给大家解释清楚了希望不懂的读者可以仔细的去学学接下来一篇我讲重点介绍堆希望大家可以来支持博主。
