当前位置：首页 > article >正文

【数据结构】二叉树——堆

article 2024/10/28 23:33:52

一、二叉树的概念与结构

二叉树的概念

二叉树是树的一种，二叉树的特殊之处在于，每个根节点都可以有两个子节点，可以两个子节点都为空，或者一个为空，一个不为空，或者两个都有数，在构建二叉树的节点时就可以看出：
在这里插入图片描述
现实中的二叉树：

就像这颗树，每次分叉都分出两个枝条，这就是一个二叉树

特殊的二叉树

完全二叉树

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。

在这里插入图片描述

二、特殊的二叉树——堆

2.1 堆的定义

首先堆是一个完全二叉树，堆中的数字要以一定的规则进行排列
如果我们创建一个堆
让堆中所有根部数据都小于该根的左右两孩子的数据，那么这个就是一个小堆
让堆中所有根部数据都大于该根的左右两孩子的数据，那么这个就是一个大堆
在这里插入图片描述
所以我们可以理解为，若堆第一层根部为整个堆的最大值，为大堆，若为整个堆的最小值，为小堆

2.2 堆的结构

我们知道了堆的定义那我们如何队堆进行创建以及存储呢?
有两个方案：顺序结构存储，链式结构存储

顺序结构存储

我们要定义父母节点和孩子节点
父母数组下标：
parent = (child - 1) / 2
孩子数组下标：
左孩子：child = parent * 2 + 1
右孩子：child = parent * 2 + 2
在这里插入图片描述

在这里插入图片描述

如图我们将二叉树通过顺序表，也就是数组存储
优点：有下标查找数据方便
缺点：有可能会出现空的情况浪费空间，在顺序表开辟空间时一次开辟二倍，会造成空间浪费

链式结构存储

在这里插入图片描述
我们像上面开辟二叉树的节点，分为根节点，左孩子节点，右孩子节点
优点：随用随开，不会有空间浪费
缺点：无法随意访问树中元素，只能遍历

总结

对于堆这种特殊二叉树来说，因为堆是完全二叉树，所以不存在中间有用不到的空间，所以对于创建堆这个特殊结构，我们选择采用顺序结构存储。

2.3 堆的代码实现

堆的结构体创建

在这里插入图片描述

堆的初始化

在这里插入图片描述
先判断传过来的是否为空指针，若为空指针则下面无法解引用，会使程序出错
在初始化阶段可以选择先开辟空间，比如先开辟四个空间，但是在插入时也会开辟空间，会有一些重复，我就没有选择开辟。

堆的销毁

因为我们要动态开辟空间，所以为了避免出现内存泄漏，我们要将开辟的空间进行释放
在这里插入图片描述
这里我们不能直接 free(php) 因为堆中还有我们开辟的数组，如果直接释放，就会使内存泄漏，并且使程序中出现野指针。

堆的插入

在将堆插入时我们要考虑以下一些问题：
1、是否需要为插入数据开辟空间
2、当数据插入堆时，我们需要对堆进行调整

问题1

解决问题1，我们要先将 size 与 capacity 进行比较，若相等说明需要开辟空间
在这里插入图片描述

问题2

解决问题2，我们要将插入的数进行向上调整，我们传进去的是孩子所在下标，我们要找到其父母下标，向上调整对多的情况是插入的数为最小值到了下标为0的位置。

我们写一个向上调整函数：
传入的是数组，和要向上调整的孩子节点。
在这里插入图片描述

堆的删除

这里的删除并不是将最后一个数删除，而是将下标为0位置的根删除，这就会引发一系列问题：
如何删除，是通过将后面的数据把根位置的数据覆盖吗？如果如此做的话，后面的数就不是堆了，还要重新建堆，这未免有些不合适。
在这里插入图片描述
如果删除之后要重新建堆，效率就会变得很低。

所以我们若要删除根位置节点，就不能直接删除
我们采用的方法是将数组末尾的数与根位置的节点进行交换，然后删除数组末尾的数据，因为根的两个子树没有变，所以两个子树还是堆，将根位置交换过去的数进行向下调整
向下调整：
向下调整和向上调整相反
向上调整是将数据从孩子向上与父母比
向下调整时将数据从父母向下与孩子比
若是小堆，向下调整时要与孩子中小的那一个进行比较，因为若是与两个孩子中较大的那一个进行比较有可能较大的孩子大于另外一个孩子而小于父亲，当这个孩子被换到上面时就会出错。