网站返回首页按钮,余姚做网站设计的公司,电子图书网站建设,交易网站建设需要学什么软件树 树的概念#xff1a; 树#xff08;Tree#xff09;是一种抽象数据结构#xff0c;它由节点#xff08;node#xff09;的集合组成#xff0c;这些节点通过边相连#xff0c;把
节点集合按照逻辑顺序抽象成图像#xff0c;看起来就像一个倒挂着的树#xff0c;也…树 树的概念 树Tree是一种抽象数据结构它由节点node的集合组成这些节点通过边相连把
节点集合按照逻辑顺序抽象成图像看起来就像一个倒挂着的树也就是说数据结构中的树是根成朝上叶子朝下。 树形结构中⼦树之间不能有交集否则就不是树形结构 就不能称之为树 ⾮树形结构 像上图子节点与子节点会相交这种就不能称之为树。 树的专业术语 ⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点 ⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 结点的度⼀个结点有⼏个孩⼦他的度就是多少 叶⼦结点/终端结点度为 0 的结点称为叶结点 分⽀结点/⾮终端结点度不为 0 的结点 兄弟结点具有相同⽗结点的结点互称为兄弟结点(亲兄弟) 树的高度或深度树中结点的最⼤层次 结点的祖先从根到该结点所经分⽀上的所有结点 路径⼀条从树中任意节点出发沿⽗节点-⼦节点连接达到任意节点的序列 ⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。 森林由 mm0 棵互不相交的树的集合称为森林 二叉树 二叉树的概念 在树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。 二叉树的特征 从上图可以看出⼆叉树不存在度⼤于 2 的结点 并且⼆叉树的⼦树有左右之分次序不能颠倒因此二叉树又是一个有序树。 以上均为二叉树可能出现的情况。 满二叉树与完全二叉树 满二叉树 满二叉树是一种特殊的完全二叉树。⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀ 个⼆叉树的层数为 K 且结点总数是 2 k − 1 则它就是满⼆叉树。 从上图可以看出满二叉树属于一个等比数列通过等比数列求和公式可以计算出满二叉树的节点总数。 完全二叉树 完全二叉树Complete Binary Tree是一种特殊的二叉树其所有节点按照从上到下、从左到右的顺序填充除了最后一层可能不是满的其他所有层都必须是满的 根据上图示例只有左边是完全二叉树而右边不是因为完全二叉树要保证k-1层是满的而第l层要保证顺序必须一次按照从左到右不能中间断开。同时也可以推断出完全二叉树的节点范围为[2^(h-1),2^h-1]. 2^(h-1) 是高度为 ( h ) 的二叉树最少的节点数。它表示二叉树的最底层可能是单侧排列的最小节点数即最小深度。 2^h - 1 是高度为 ( h ) 的二叉树的最大节点数。它表示如果二叉树是满二叉树所有层都是满的情况下的节点数。 二叉树的性质: 若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2^(k−1) 个结点 若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2^h-1(最大节点数情况为满二叉树上图证明过了) 若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 ( log 以2为底 n1 为对数) h log (n 1) 二叉树的存储结构 ⼆叉树⼀般可以使⽤两种结构存储⼀种顺序结构⼀种链式结构而在这篇文章小编主要说的是顺序存储。 顺序存储 顺序结构存储就是使⽤数组来存储⼀般使⽤数组只适合表⽰完全⼆叉树。 从上图可以看出二叉树使用顺序存储时在物理结构上就是一个数组而拆解成逻辑结构就是一个二叉树而用顺序表存储二叉树时只适用于完成二叉树与满二叉树因为不是完全⼆叉树会有空间的浪费完全⼆叉树更适合使⽤顺序结构存储。现实中我们通常把堆⼀种⼆叉树使⽤顺序结构的数组来存储需要注意的是这⾥的堆和操作系统 虚拟进程地址空间中的堆是两回事⼀个是数据结构⼀个是操作系统中管理内存的⼀块区域分段。 用堆实现二叉树 小根堆 从上图可以发现在堆顶(数组下标为0)的位置中存放的数据是这个堆中最小的值并且堆中某个结点的值总是不⼩于其⽗结点的值我们将这种堆称之为小根堆。 大根堆 从上图可以发现在堆顶(数组下标为0)的位置中存放的数据是这个堆中最大的值并且堆中某个结点的值总是不大于其⽗结点的值我们将这种堆称之为大根堆。 堆的实现 堆的结构 根据上图结构可以得知堆的底层为一个顺序表那么顺序表里存的数值不一定是整型所以这里用typedef命名变量类型这样后期改的话也方便接着就是定义一个size用来存储堆的有效数据capaticy用来存储堆的容量。 初始化堆 入堆 第一步先进行断言判断传入是指针是否为NULL。 第二步再次判断size是否等于capaticy如果等于就进行扩容。 第三步接着将数组a的size(尾部)下标位置插入x值并将size指向有效数值的下一个位置。最后通过向上调整算法维护堆里的数据。 向上调整算法: 假设这里假设此时为大堆大堆堆顶为最大值其父节点都不会小于它们的孩子节点。 这里先定义一个Swap(交换函数),为后续的交换做准备。向上调整函数定义了两个参数第一个为指向堆的指针,第二个为child(孩子)位置。这里需要知道一个公式父亲节点位置(孩子节点位置-1)/2。 第一步:定义一个parent变量用于保存父亲节点位置 第二步创建while循环因为是向上调整所以起始位置会在数组末尾当孩子节点为0的时候表示已经达到了堆顶的位置则就不需要进行调整循环结束。 第三步在循环里创建一个if语句如果父亲节点的值小于孩子节点那么就进行向上交换孩子变父亲父亲变孩子然后将父亲位置赋值给孩子继续向上找父亲节点位置进行循环判断是否交换如果不需要交换(父亲节点孩子节点)就直接退出循环。 出堆 出堆一般是在堆顶进行弹出数据因为要么是取最大值要么是取最小值在堆底出堆并没有任何的意义所在。 第一步先判断传进来的指针是否为NULL并且保证堆里有数据才能进行出堆操作。 第二步交换堆顶和堆底的值并将堆的有效数据位置size--。 第三步进行向下调整。 向下调整算法 假设这里假设此时为大堆大堆堆顶为最大值其父节点都不会小于它们的孩子节点。 向下调整函数定义了三个参数第一个为指向堆的指针,第二个为parent(父亲)位置,第三个为堆的长度。 第一步:先定义child(孩子)变量,这里只需要计算出左孩子的位置根据数组的特性数组为一块连续的内存地址,所以计算出左孩子的位置再加一就是右孩子的位置。根据公式父亲节点位置(孩子节点位置-1)/2得出左孩子位置parent*21。 第二步创建whil循环当孩子值大于size长度说明循环走完了一个堆则直接退出循环否则会下标越界。 第三步:先建立第一个if语句,先判断chid1是否小于size为了确保数组不会越界访问接再判断左右孩子的值哪一个更大因为弹出了最大的值所以要将第二大的值变成堆顶数据。如果右孩子的值比左边孩子大那么就child。 第四步:建立第二个if语句如果此时孩子节点的值会大于我的父亲节点那么就交换孩子节点与父亲节点并重新将child(孩子)位置赋值给parent(父亲)孩子位置再次等于parent*21向下进行循环调整。 取堆顶数据 销毁堆
