石家庄做网站的有哪些公司,电脑编程与网站建设,购物网网站建设,seo优化易下拉霸屏#x1f6a9;纸上得来终觉浅#xff0c; 绝知此事要躬行。 #x1f31f;主页#xff1a;June-Frost #x1f680;专栏#xff1a;数据结构 #x1f525;该文章针对树形结构作出前言#xff0c;以保证可以对树初步认知。 目录#xff1a; #x1f30d;前言:#x1f3… 纸上得来终觉浅 绝知此事要躬行。 主页June-Frost 专栏数据结构 该文章针对树形结构作出前言以保证可以对树初步认知。 目录 前言:树✉️相关概念✉️ 树的存储✉️ 树的应用 二叉树✉️ 特殊二叉树✉️ 二叉树的存储 ❤️ 结语 前言: 线性结构是一种相对简单的数据结构元素之间按照一定的顺序排列每个元素最多有两个接口前驱和后继。这种结构相对直观易于理解和管理类似一种 一对一 的关系。相比之下树形结构则更为复杂变为了 一对多 的关系。元素之间的关系不再是简单的线性排列而是以一个或多个根节点为起点通过多个分支来连接不同的元素。每个节点可以拥有多个子节点而且每个子节点可以有任意多的兄弟节点。这种结构需要更多的内存空间来存储元素之间的关系同时也需要更高级的算法来操作和管理。从复杂性的角度来看树形结构比线性结构更加复杂。 此外树的应用广泛如二叉树、红黑树、B树、哈夫曼树等。在计算机科学中树的数据结构常常被用于对数据进行组织和存储以便于高效地实现各种算法和操作。 树 树是一种非线性的数据结构它是由n(n0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 ① 注意树是递归定义的在树的定义中一个树是由一个根节点和若干个子节点组成的这些子节点本身也是一棵棵树。因此树的结构和定义是相互嵌套的。通过递归定义我们可以将一个树的结构描述为一个递归的过程即每棵子树又包含着一个根节点和若干个子节点直到叶节点为止。 ⚠树形结构中子树之间不能有交集否则会成为 图。 例如
✉️相关概念
以上图①为例 节点的度一个节点含有的子树的个数称为该节点的度如上图A的为6。 叶节点或终端节点度为0的节点称为叶节点如上图B、C、H、I…等节点为叶节点。 非终端节点或分支节点度不为0的节点如上图D、E、F、G…等节点为分支节点。 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点如上图A是B的父节点。 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点如上图B是A的孩子节点。 兄弟节点具有相同父节点的节点互称为兄弟节点如上图B、C是兄弟节点。 树的度一棵树中最大的节点的度称为树的度如上图树的度为6。 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推。 树的高度或深度树中节点的最大层次如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点。 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先。 子孙以某节点为根的子树中任一节点都称为该节点的子孙如上图所有节点都是A的子孙。 森林由mm0棵互不相交的树的集合称为森林。
✉️ 树的存储 树的存储中既要保存值域也要保存结点和结点之间的关系有很多存储结构。例如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等 孩子兄弟表示法LCRS 双亲表示法 在每一个节点中存储其父节点的下标。这样就可以将树中各节点的结构关系表示出来也可以快速地对父节点进行访问。
✉️ 树的应用 树形结构的应用非常广泛。如
数据库中的索引数据库系统使用树形结构来实现索引以提高数据访问效率。电子邮件系统电子邮件系统中的邮件通常是通过树形结构进行组织和管理的每个邮件可以有多个回复或转发形成一个树形结构。编译器中的语法树编译器将源代码解析为语法树其中每个节点表示特定的语法结构如一个函数、一个循环或一个条件语句。文件系统的目录树结构。 在实践当中用的最多的树是二叉树。 二叉树 一棵二叉树是结点的一个有限集合该集合可以为空也可以由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 对于任意的二叉树都是由以下几种情况复合而成的 例如 注意
二叉树不存在度大于2的结点由于二叉树最多有2个孩子为了区分概念就定义了左孩子和右孩子所以二叉树的子树有左右之分次序不能颠倒 —— 二叉树是有序树。
✉️ 特殊二叉树
满二叉树 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。如果一个满二叉树的层数为K结点总数就是2h-1同样的如果一个满二叉树的节点总数为N则层数为log2(N1)。 满二叉树 假设有h层前h-1层都是满的最后一层不一定满节点从左到右连续。要注意的是满二叉树是一种特殊的完全二叉树。假设有h层则完全二叉树的节点范围为 [ 2(h-1) , 2h - 1] 。 一些性质
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2(i-1)个结点.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2h-1.对任何一棵二叉树, 如果度为0的其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有 n0 n21
✉️ 二叉树的存储 二叉树的存储结构通常可以采用顺序存储和链式存储两种。
链式存储对于一般的二叉树通常采用链式存储方式。每个节点包含三个字段数据域、左孩子指针和右孩子指针。数据域用于存储节点的值左孩子指针指向该节点的左子节点右孩子指针指向该节点的右子节点。如果某个节点没有子节点对应的指针就为空NULL。顺序存储对于完全二叉树可以直接使用数组进行存储将根节点存储在索引为1的位置然后按照层次顺序从左到右从上到下对每个节点赋予一个唯一的索引。这种存储方式对于完全二叉树来说可以节省存储空间并且可以通过索引快速访问节点。 顺序存储结构和链式存储结构各有优劣需要根据实际应用场景和需求来选择使用哪种存储方式。如果需要频繁查找且表的长度变化不大可以使用顺序存储结构如果需要频繁插入和删除操作且表的长度变化较大使用链式存储结构可能会更好。 ❤️ 结语 文章到这里就结束了如果对你有帮助你的点赞将会是我的最大动力如果大家有什么问题或者不同的见解欢迎大家的留言~
