物流网站平台建设,网站网络安全怎么做,小程序商城货源怎么找,建设工程什么意思概述树的章节一般分两大部分#xff1a; 一部分将树#xff0c;一部分将二叉树#xff1b;虽然二叉树也是树#xff0c;但是二叉树足够特殊#xff0c;足够有用#xff0c;所以重点来讲#xff1b;或者说#xff0c;如果不是二叉树#xff0c;树的家族也不会如此的德高…概述树的章节一般分两大部分 一部分将树一部分将二叉树虽然二叉树也是树但是二叉树足够特殊足够有用所以重点来讲或者说如果不是二叉树树的家族也不会如此的德高望重。在二叉树中又有一些特殊性质的二叉树可能没法用树的结构来描述他们之间的关系比如 满二叉树一定是完全二叉树完全二叉树和二叉排序树直接却没有从属关系完全二叉树和二叉排序树是从不同的维度定义出来的特殊的二叉树。二叉排序树(也叫二叉查找树)在树的家族中是一颗耀眼的明星但是在树的章节中没有被介绍大概因为这是二叉树的实际应用而和树本身的形态没有直接关系还有一些特殊的树如红黑树、B、B-树稍后再研究有些数据结构的书是没有提及的大概因为这些东西可以自学不需要教吧。树树的逻辑结构树的定义树是n(n0)个结点的有限集合。当 n 0 时称为空树任意一颗非空树满足一下两个条件有且只有一个特定的称为根的结点当 n 1 时除根结点之外的其余结点被分成m(m0)个互不相交的有限集合T1, T2, …, Tm其中每个集合又是一棵树并称为这个根结点的子树树的基本术语结点的度树的度叶子结点分支结点孩子结点双亲结点兄弟结点路径、路径长度祖先、子孙结点的层数、树的深度(高度)层序编号有序树、无序树森林同构树的表示形式一般有四种表示形式树形图嵌套图凹凸表广义表树的遍历前(根)序遍历后(根)序遍历层序遍历注 这里说的是树不是二叉树所以没有中序遍历(如果有的话三个子树的树根应该放哪里)树的存储结构双亲表示法思想 每个结点都记住自己双亲结点的位置(即可保证该树是唯一的)缺点 要找到一个结点的所有孩子是比较麻烦的使用数组存储还是比较方便的孩子表示法思想 每个结点都记住自己孩子的位置(即可保证该树是唯一的)缺点 要找到结点的双亲结点比较麻烦两种形式多重链表标识思想 父亲那N个绳拉住自己的N个孩子关于拿几根绳两种办法有几个孩子拿几根绳需要有一个地方记录自己的绳子数目(就是该结点的度)孩子最多的父亲拿几根绳子大家就都拿几根绳子没人的绳子数目是一样的不需要各自记录孩子链表思想所有节点维护在一个数组中然后父亲拿一根绳子牵着老大然后老大牵着老二依次类推孩子双亲表示法思想孩子表示法中添加一个双亲节点的指针孩子兄弟表示法思想 每个节点都左手拉着自己孩子右手拉着自己的弟弟妹妹二叉树概述二叉树是一种最简单的树结构其存储结构更具有规范性和确定性在一系列条件的约束下使得二叉树具有很多的性质方便我们研究和使用二叉树。二叉树的定义二叉树的5种基本形态空二叉树只有一个根结点根结点只有左子树根结点只有右子树根结点既有左子树又有右子树特殊二叉树斜树左斜树右斜树满二叉树完全二叉树从满二叉树的最后面的结点去掉n (n 0)个结点都是完全二叉树满二叉树是一种特殊的完全二叉树二叉树的性质二叉树有5个重要的性质他们主要讨论了树的深度、结点数等之间的关系在二叉树的第i层上至多有2i-1个结点 (i 1)深度为k的二叉树至多有2k-1个结点 (k 1)对任何一颗二叉树T如果其叶子结点数为n0度为2的结点数为n2则n0n21具有n个结点的完全二叉树的深度为log2n1如果有一颗有n个节点的完全二叉树的节点按层次序编号对任一层的节点i(1in)有1.如果i1则节点是二叉树的根无双亲如果i1则其双亲节点为[i/2]向下取整2.如果2in那么节点i没有左孩子否则其左孩子为2i3.如果2i1n那么节点没有右孩子否则右孩子为2i1二叉树的遍历前序遍历中序遍历后序遍历二叉树的存储顺序表思想 将一棵树通过添加“虚节点”的方式完善成完全二叉树然后存储缺点 空间浪费严重只适合存储完全二叉树的情况链式存储二叉链表思想 每个结点包含数据域和左右孩子两个指针域缺点 寻找双亲结点不方便三叉链表思想 在二叉链表的基础上添加双亲结点指针域线索链表实际问题 select * from tb where id N limit 2; 在这种情况下我们不仅要查到id2的结点还要找到他附近的一些结点即 需要访问二叉树中的结点在某种遍历序列中的前驱和后继于是 在存储结构中应该保存结点在某种遍历序列中前驱和后继的信息。思想 根据二叉树的性质可知二叉树中有n1个指针域为空可以想办法利用起来通过添加标记来区分是孩子指针还是前驱(或后继)指针注意 挨着自己的孩子在线索化中未必就挨着自己但是要找到挨着自己的那个结点并不难对于中序线索链表如果自己子树的深度为k则找到自己的前驱或后继的时间复杂度为log2k由于二叉树的遍历次序有三种因此有三种意义上的前驱和后继相应的也有三种线索链表前序线索链表、中序线索链表、后序线索链表。中序线索链表看起来更加直观一些中序线索链表上求结点前驱中序线索链表上求结点后继中序线索链表上遍历
