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

一起学数据结构（8）——二叉树中堆的代码实现

news 2025/7/8 0:29:35

在上篇文章中提到，提到了二叉树中一种特殊的结构——完全二叉树。对于完全二叉树，在存储时，适合使用顺序存储。对于非完全二叉树，适合用链式存储。本文将给出完全二叉树的顺序结构以及相关的代码实现：

1. 二叉树的结构建立、销毁及初始化：

给出下图中二叉树的逻辑结构及存储结构：

二叉树的逻辑结构只是根据想象创建出来的结构，但是在计算机存储时，并不存在逻辑结构这种形式。而是下方的存储结构。所以，以下所有操作的对象都是存储结构中连续的数组。例如需要在上述二叉树中插入一个新的结点，并且此结点存储了元素 $90$ 。逻辑结构表示如下：

对于存储结构而言，以上操作只是在已有数组的末尾插入了一个值。存储结构表示如下：

所以，对于二叉树的结构建立，可以仿照之前的顺序表的结构，代码如下：

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

其中，指针 $a$ 用来后续进行连续空间的开辟， $size$ 表示数组的长度， $capacity$ 用来记录数据的容量，一旦 $size = capacity$ 就需要进行扩容。

对于二叉树的销毁与初始化，与前面的文章中方式相同，只给出代码，不做多余解释：

二叉树的初始化如下：

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

二叉树的销毁如下：

void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

2. $HeapPush$ 向二叉树中插入结点：

2.1 HeapPush 向二叉树中插入结点：

前面提到，二叉树的逻辑结构在计算机中并不存在，并且下面的代码操作都是针对二叉树的逻辑结构的。所以，向二叉树中插入元素这一操作，实际就是在数组的末尾插入一个元素。但是在插入元素之前，需要判定数组的空间是否有剩余，即满足： $size < capacity$ 。一旦 $size = capacity$ ，则需要进行一次扩容。对于扩容这一步骤在之前的文章中多次使用，这里依旧直接给出代码：

void HeapPush(HP* php, HPDataType* x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* newnode = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (newnode == NULL){perror("realloc");exit(-1);}php->a = newnode;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;}

2.2 针对二叉树为小堆情况下，新插入元素的位置调整：

2.2.1 结点调节的逻辑分析：

例如对于上面给出的完全二叉树，可以看出，这个二叉树满足父结点数值 $<$ 子结点数值，为小堆

对于新结点中插入的数值，需要区分下列情况进行判定：

1. 插入的值大于父结点中的数值 $56$ ，即：

此时插入的结点的数值为 $90$ ，依旧满足子结点数值 $>$ 父结点数值，因此不需要对结点的关系进行更改。

2. 插入的值小于父结点中的数值 $56$ ：

此时插入的结点中存储的值为 $32$ 。不满足小堆中父结点存储的值 $<$ 子结点的关系。所以，需要对二叉树的关系进行更改，即对此时的子结点、父结点交换位置，效果如下：

但是，如果插入的结点中存储的值，小于二叉树中任何结点的值，例如新插入结点中存储的值为 $1$ 。此时调整后的二叉树的效果如下：

对于调整父结点、子结点的关系，在上一篇文章中，根据完全二叉树的性质给出了下列的等式：

对于一个父结点，假设其在数组中的下标为 $parent$ ，则其左子结点的下标：

$child1 = parent*2+1$

其右子结点的下标为：

$child2 = parent*2+2$

对于任意子结点 $child$ （左、右子结点都适用），其父结点的下标可以用下面的等式表示，及：

$parnet = (child-1)/2$

定义函数 $Adjustup$ 用于完成对子结点、父结点关系的调整：
前面提到，对于插入子结点，最极端的情况就是子结点中存储的值小于二叉树中任意结点的值，导致子结点需要一直与父结点进行替换，直至到根结点，即数组中下标为 $0$ 的结点的位置。因此需要利用循环来控制结点的调整次数，通过上面的分析可以得出，循环的条件就是子结点对应的下标 $> 0$ ，即： $child> 0$ 。

2.2.2 Adjustup 结点调节的代码分析：

对于上面的给出的向二叉树中插入元素的操作中，需要注意，在插入元素后，会对表示数组长度的 $size+1$ ，所以，每次进行上述插入操作后： $size$ -数组的实际长度 $=1$ 。

上面说到，会创建函数 $Adjustup$ 函数来调整结点的位置，整个操作中，需要知道子结点、父结点的下标，因为父结点的下标可以通过上面给出的等式进行计算。所以，在对函数传递参数时，只需要传递数组的指针和插入的子结点的下标。因为插入的结点为数组的最后一位，所以，直接传递数组的实际长度，即 $size-1$ 即可。

对于交换子结点和父节点这一功能在后面需要多次适用，所以，为了方便，直接再创建一个交换函数 $Swap$ 即可。交换函数对应的代码如下：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}

调整函数代码如下：

void Adjustup(HPDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

对于上面已经给出的插入函数，在最后加上已经定义好的调整函数即可。

为了验证前面的功能是否正常，再定义函数 $HeapPrint$ 用于打印二叉树的结点。打印函数嗲澳门如下：

void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}
}

通过下面的代码，对插入并且调整结点的函数进行验证：

#include"TreeNode.h"void Test1()
{int a[] = { 9，8，7，5，4，3，2 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestory(&hp);}
int main()
{Test1();return 0;
}

运行结果如下：

运行结果显示的是二叉树的存储结构，将上述存储结构转为逻辑结构，即：

满足小堆的定义。

3.删除二叉树中的结点：

3.1 删除二叉树中结点逻辑分析：

给定下列的二叉树：

对于二叉树的删除结点而言，删除尾部结点的意义并不大，所以，一般的删除结点都是指删除二叉树的根结点。

前面提到，对于二叉树的操作，是作用在二叉树的存储结构上，上图二叉树的存储结构如下：

对于一个连续的数组，删除头结点的方式可以是让后面的元素依次向前覆盖。但是对于二叉树而言，向前覆盖来删除头结点的方式可能会造成二叉树的结构错误，例如，利用覆盖的方法删除了头结点的二叉树的逻辑结构如下：

调整过后的二叉树，将不再满足上方的小堆关系，即子结点存储的数据 $>$ 父结点存储的数据。并且，再顺序表的文章中就提到，对于依次覆盖这种方法，时间复杂度为 $O(N)$ ,效率并不高。

为了解决上面的问题，给定下方的方法来完成对于根结点的删除：

首先，将二叉树的尾结点和根结点替换，效果如下：

对于二叉树的存储结构，可以随机访问数组的任意下标所对应的位置，并且尾插和尾删的效率为 $O(1)$ ，所以，直接将尾结点删除，即：

通过上述方法删除了二叉树的原根结点之后，此时二叉树的子树并没有受到影响，依旧是小堆，删除了二叉树的原根结点后，需要对二叉树中的结点的位置进行调整。

在调整位置时，需要先比较结点的子结点所存储的数据的大小，例如根节点的子结点分别存储了数据 $5,3$ ,由于根节点存储的数据 $4$ 大于右子结点所存储的数据 $3$ ，因此两个结点交换位置。

需要注意，此处的调整并不同于上方给出的调整函数 $Adjustup$ 。上方的函数调整的对象是针对于新插入的尾结点。调整的方向是总体向上的，本处的调整是针对于置换完后的新的根结点，总体的方向是自上而下的，因此，此处再构建另一个调整函数 $Adjustdown$ 。

3.2 代码分析——Adjustdown 删除二叉树中结点：

对于调整函数 $Adjustdown$ ，首先判断非叶子结点的子结点的大小关系，并找到较小的一个。可以先假设一个结点为小结点（此处默认左子结点为小结点），对于左子结点的下标，可以通过上面的等式

$child = parent*2+1$

得出，对于右子结点，可以表示为 $child+1$ ，再对两个结点中数据的大小进行判定，如果 $a[child+1]<a[child]$ ，则表示右子结点为较小的结点，让 $child+1$ ,反之不变。此处需要注意一种特殊情况，及：

此时，存储数据 $3$ 的结点只有左结点，没有右结点， $child+1$ 会引起数组的越界访问，所以，在进行结点大小判定之前，需要判定 $child+1<size$ 。

找到左、右子结点中较小的一个后，对父结点、子结点的大小进行判定，如果子结点中存储的数据小于 $<$ 父结点中的数据，则交换两个结点的位置。

对于交换这一过程，最好的情况下是交换一次，最坏的情况下是交换到叶子结点。所以，判断循环是否进行的条件便是判断 $child$ 的大小是否 $<$ $size$ 。对应代码如下：

void Adjustdown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while ( child < size){if (child+1 < size && a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

3.3 代码分析——HeapPop 删除二叉树中的结点：

删除结点一共需要下列步骤：

1. 交换首位结点

2. 删除尾结点

3.通过调整函数对结点的位置进行调整

对应代码如下：

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;Adjustdown(php->a, php->size, 0);}

4. 返回根结点所存储的数据：

原理较为简单，只给出代码，不做解释：

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

5. 探空：