二叉树及其顺序结构（堆）

来源：纷纭教育

一、树

1.1 树的概念与结构

树是一种非线性结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂着的数。

有一个特殊的节点，称为根节点，根节点没有前驱节点。

树的节点遵循从上到下，从左到右的顺序排列。

除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树（如下图）。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

1.2 树的相关术语

二、二叉树

2.1 概念与结构

由一个根节点加一棵左子树和一棵右子树构成（因为是二叉树，所以每个父节点下的孩子节点个数不大于2）

二插数具备以下特征：

（1）二叉树不存在根大于2的节点

（2）二叉树有左右子树之分，次序不能颠倒，因此称为有序数

2.2 特殊的二叉树

2.2.1 满二叉树

一个二叉树如果每一层的节点个数都达到最大值则为满二叉树（既对应父节点都有且只有两个子节点）。

2.2.2 完全二叉树

完全二叉树是由满二叉树引出来的。最后一层节点个数不一定达到最大，满二叉树一定包含完全二叉树，而完全二叉树不一定是满二叉树。

2.3 二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。由于本章实现的是顺序结构，所以链式结构不讲放到下一章讲。

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

从上图可以看出：非完全二叉树把空节点也存进数组中，这样造成了很大的空间浪费。

三、实现顺序结构二叉树

看到顺序结构二叉树，就想到堆。

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树。既堆是二叉树的一种表现形式，因为还具备其他的特性使其成为特殊的二叉树。

3.1 堆的概念与结构

堆分为大堆（大根堆）和小堆（小根堆）。解释如下：

根节点存在数组首元素位置，依次从上到下从左到右按顺序存储

大根堆：

二叉树中，每个孩子节点所对应的双亲节点比自身大则为大根堆。10的父节点56大于10,25和15的父节点30也比25和15大，30和56的父节点70同样比30和56大。将根节点最⼤的堆叫做最⼤堆或⼤根堆。

小根堆：

二叉树中，每个孩子节点所对应的双亲节点比两个孩子节点小为小根堆。根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆具有以下性质：

（1）堆中某个节点的值总是不大于或不小于其父节点的值。

（2）堆总是一颗完全二叉树

那么二叉树又有什么特殊的性质呢？

💡 ⼆叉树性质

对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

（1）若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点

（2）若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦

（3）若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

综上所述：知道根节点，我们可以通过公式找到其对应的子节点位置；知道子节点同理可以找到其父节点位置。

3.2 算法分析

在建堆和调整堆的过程中，我们会用到以下两种算法：向上调整算法和向下调整算法。

（一）向上调整建堆算法

假设有一个数组如下，将其从上到下从左到右用树的形式表示得：它是一颗二叉树但不符合堆的性质。上面提到堆只有两种形式：大根堆和小根堆，此图两者均不满，所以要对其进行调整构建堆，要调整就涉及到向上调整算法。

💡 向上调整算法

（1）先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后。

（2）插⼊之后如果堆的性质遭到破坏（不再是大根或小根堆），将新插⼊结点顺着其双亲往上调整到合适位置即可。

上面同样介绍了二叉树的性质：知道孩子节点能找到双亲节点，同理知道双亲节点也可找到孩子节点。

父节点位置=（子节点下标-1）/2 ：（i -1）/2 i : 节点下标

所以最后一个孩子10的父节点（10-1）/2=4，对应数组中下标为4的元素28；28确实如图所示是10的父节点。同样我们可以找一下倒数第二个孩子37的父节点（9-1）/2=4，同样如图所示28为其父节点。

找到父节点后，若要调整成小堆的形式则判断父节点是否比子节点大，若大交换位置，使父节点是堆中最小值。接着i--进行下一个元素（i -1）/2 找父节点再比较的过程。不难发现这是一个循环调整的过程，循环结束的标志是数组中所有元素都遍历完，既数组下标大于0进入循环。

通过以上排序后，可使原本数组符合小堆的要求，可用于一开始给定个数组，要求你建成一个小堆的场景。（此方法不是固定只能建（调整）小堆，也可调整成大堆；父节点是否比子节点小，若小交换位置就变成大堆，这边就不演示大堆了）

代码如下：

向上调整你得给我要调整的数组吧，以及要调整元素下标，所以向上调整函数有两个参数，调整后不需要返回值。

💡 向上调整算法建堆时间复杂度为： O(n ∗ log2 n)

（二）向下调整建堆算法

向上调整建堆是从最后一个子节点开始调整的话，那么向下调整建堆则从根节点开始向下调整使其满足堆的性质。有⼀个前提：左右⼦树必须是⼀个堆，才能用向下调整算法。

假设我们要建一个小堆，以下左右子树不符合小堆的性质那就要一部分一部分调整使其符合小堆的性质。

先从最右边开始，因为我们知道最后一个孩子19的节点下标就能够通过（i -1）/2 找到父节点65；已知父节点下标通过2i+1找到左孩子，再2i+1+1找到右孩子（因为树是按数组顺序依次排列，兄弟节点只要+-1就能对应找到其在数组中的位置）让它的两个孩子34和19先比较出最小的那个再与父节点65交换。

再让父节点--来到下一个父节点25位置，循环上面步骤，比较出最小的孩子节点再与父节点交换，交换完父节点再--来到根节点，循环条件父节点个数>=0。通过不断调整将会建立出一个符合要求的堆。

此算法同样适用建大堆，只要微调即可。

（注：由于纯手绘字迹比较潦草还请多担待；再者向下调整的数据选的不太好，调整完碰巧数组为升序（只是碰巧）调整的步骤和思想无误！）

代码：

向下调整得给我要调整的数组吧，然后要调整的父节点也得给我吧，以及整个数组大小；总不能调着调着越界了吧，所以有3个参数。

💡 向下调整算法建堆时间复杂度为： O(n)

3.3 堆的实现

堆底层结构为数组，因此定义堆的结构等于定义数组结构：

（1）堆的初始化

（2）堆的销毁

堆的销毁等于数组空间的销毁

（3）往堆插入数据

往数组中插入数据得先判断是否空间足够，不够要动态realloc增容，使其有足够的空间存放数据。

动态增容另一篇博客：有细讲此处不再赘述。

增容后往数组最后一个位置插入数据，此时数组未经调整可能不符合堆的结构，所以使用向上调整法建大堆（也可向下调整，只是这里采用向上），调整完别忘了让数组元素个数加1。

（4）判断堆是否为空/求堆的节点个数

这两个函数实现起来比较简单，堆为空则数组个数为0

堆的节点个数直接返回数组元素个数即可

（5）删除堆顶数据

可能很多人会认为：哎呀！So easy，直接把arr[0] 删了就好。这是错的！不要学！！

有没有考虑到：如果直接删除堆顶，整颗数的父子结构直接乱套，也就不存在堆原本的性质，这将会十分麻烦，所以下面我将介绍一种删除堆顶的方法。

堆的删除：

删除堆是删除堆顶的数据，将堆顶的数据跟最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏向下调整算法。

交换：

向下调整：左右⼦树必须符合堆性质，才能调整。

向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

💡 向下调整算法

（1）将堆顶元素与堆中最后⼀个元素进⾏交换

（2）删除堆中最后⼀个元素

（3）将堆顶元素向下调整到满⾜堆特性为⽌

【注】：这里要和前面向下调整算法建堆区别开！！

你这样理解堆删除之前本来就是需要提前建堆的升序建大堆，那么你需要用调整函数把原来的数组构建为一个大堆，然后再利用向下调整算法对这个大堆每次交换堆头和堆尾元素进行删除最后⼀个数据。