树
树的概念:
树(Tree)是一种抽象数据结构,它由节点(node)的集合组成,这些节点通过边相连,把
节点集合按照逻辑顺序抽象成图像,看起来就像一个倒挂着的树,也就是说数据结构中的树是根成朝上,叶子朝下。
树形结构中,⼦树之间不能有交集,否则就不是树形结构 ,就不能称之为树
⾮树形结构:
像上图,子节点与子节点会相交,这种就不能称之为树。树的专业术语
⽗结点/双亲结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点 ⼦结点/孩⼦结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点; 结点的度:⼀个结点有⼏个孩⼦,他的度就是多少; 叶⼦结点/终端结点:度为 0 的结点称为叶结点; 分⽀结点/⾮终端结点:度不为 0 的结点; 兄弟结点:具有相同⽗结点的结点互称为兄弟结点(亲兄弟); 树的高度或深度:树中结点的最⼤层次; 结点的祖先:从根到该结点所经分⽀上的所有结点; 路径:⼀条从树中任意节点出发,沿⽗节点-⼦节点连接,达到任意节点的序列; ⼦孙:以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。 森林:由 m(m>0) 棵互不相交的树的集合称为森林;二叉树
二叉树的概念:
在树形结构中,我们最常⽤的就是⼆叉树,⼀棵⼆叉树是结点的⼀个有限集合,该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
二叉树的特征:
从上图可以看出⼆叉树不存在度⼤于 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为底, n+1 为对数) 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*2+1。
第二步:创建whil循环,当孩子值大于size长度说明循环走完了一个堆则直接退出循环否则会下标越界。
第三步:先建立第一个if语句,先判断chid+1是否小于size,为了确保数组不会越界访问接再判断左右孩子的值哪一个更大,因为弹出了最大的值,所以要将第二大的值变成堆顶数据。如果右孩子的值比左边孩子大那么就++child。
第四步:建立第二个if语句如果此时孩子节点的值会大于我的父亲节点,那么就交换孩子节点与父亲节点,并重新将child(孩子)位置赋值给parent(父亲),孩子位置再次等于parent*2+1,向下进行循环调整。
取堆顶数据
销毁堆