【数据结构】穿梭在二叉树的时间隧道：顺序存储的实现

专栏引入

哈喽大家好，我是野生的编程萌新，首先感谢大家的观看。数据结构的学习者大多有这样的想法：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学的很累。我想让大家知道的是：数据结构非常有趣，很多算法是智慧的结晶，我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏，在这里我将把数据结构内容以有趣易懂的方式展现给大家。

1.二叉树的顺序存储结构

之前我们谈过了树的存储结构，并且谈到了顺序存储结构对树这种一对多的关系结构实现起来还是比较困难的。但二叉树是一种特殊的树，由于二叉树的特殊性，使得它可以使用顺序存储结构来实现，二叉树的顺序存储结构就是使用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现出来节点之间的逻辑关系，比如：双亲和孩子的关系、左孩子右兄弟的关系等。先来看看完全二叉树的顺序存储，就用下面这棵二叉树为例：

将这棵二叉树存入数组中，相应的下标对应其同样的位置，很多数据结构相关书籍上下标都是将0空置，从1开始存储，其实下标0的位置是否存放数据对堆的实现的难度没有影响，为了节省空间我对下标为0的位置进行了存储，如下图：

这下我们可以看出来完全二叉树的优越性了吧，由于它严格的定义，所以用顺序结构也可以表现出二叉树的结构来，当然对于一般的二叉树，尽管层序编号不能反映出来逻辑关系，但是可以将其按完全二叉树来编号，只不过，把不存在的节点设置为"NULL"而已，就像下面的图中，虚线部分表示不存在：

我们再考虑一种极端的情况：一颗深度为h的右斜树。它只有h个节点，却要分配 $2^{h}-1$ 个存储单元空间，这显然是对存储空间的浪费，如下图所示：

所以，二叉树的顺序存储结构一般只适用于完全二叉树。上一篇中我们提到了堆是一个特殊的完全二叉树，所以这篇我们就以堆为例子来实现二叉树的顺序存储。

2.堆

2.1堆的概念

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子节点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。如下图所示：

从堆的定义可以知道：根节点一定是堆中所有结点的最大（小）值。在上一篇堆二叉树的性质介绍时，有一个性质还没和大家介绍，因为这个性质就仿佛是为堆量身定制的，所以我计划在介绍堆时再介绍它：

如果一棵有n个节点的完全二叉树（其深度为 $\left \lfloor \log_{2}n \right \rfloor+1$ ）的节点按层序编号（从第一层到第 $\left \lfloor \log_{2}n \right \rfloor+1$ 层，每层从左到右），对任一节点i（1≤i≤n）有：

如果i=1，则节点i是二叉树的根，无双亲；如果i>1,则双亲是节点 $\left \lfloor i/2 \right \rfloor$ 。
如果2i>n，则节点i没有左孩子（节点i为叶子节点），否则其左孩子是节点2i。
如果2i+1>n，则节点i没有右孩子；否则其右孩子是节点2i+1。

在这个性质第二、三条，也就是说明下标i与2i和2i+1的双亲子女的关系：双亲结点=（子节点-1）/2。

2.2堆的实现

我们先来定义一下堆的结构：

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

2.2.1堆的创建和销毁

堆的创建我们使用顺序存储来实现，所以它的创建和销毁的实现代码和顺序表的实现的相同。首先是堆的创建函数：

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

接着是堆的销毁函数：

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

2.2.2堆的向上调整

一说到调整我们肯定会对两个数据进行交换，我们先来写一个交换函数：

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

堆的向上调整是将一个元素插入到小堆时，调整堆的结构，使其满足小堆的性质过程。实现堆的向上调整的要先将元素插入到数组的最后一个位置（这一步我们在堆的插入操作中实现）。这时候我们就要比较插入元素和其双亲结点的大小关系，然后做出调整。这里我们可以用循环实现，用循环来实现比用递归实现的好处有：

空间开销：循环实现通常比递归实现需要更少的内存空间。递归函数会在每次调用时创建一个新的函数栈帧，而循环则只使用一个循环体内的局部变量。
性能：循环实现通常比递归实现具有更高的执行效率。递归函数在每次调用时都需要进行函数调用、参数传递和返回值处理等操作，而循环通过使用迭代变量和循环条件判断来控制流程，避免了递归带来的额外开销。

首先我们先将这个函数里面的判断条件先写好：

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

既然我们要用循环来实现，那么使用while()语句的循环条件是什么呢？最坏的情况就是将新插入的节点经过调整变成根节点，那条件是parent≥0吗？parent是不会小于0的，当parent=0时，插入的数据还要接着向上调整交换，此时child变为0，parent=(0-1)/2，我们计算出来的parent时-0.5，但是要取整，所以parent还是0，此时循环还是没结束，会再次进入循环，此时child==parent，经过判断语句会侥幸跳出循环，这样是不严谨的。我们将循环条件设为child大于0就可以完美解决这个问题。此时，这个向上调整的操作完整代码为：

void AdjustUp(HPDataType* a, int child)
{
	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;
		}
	}
}

2.3堆的插入

堆的插入操作和顺序表的插入操作相似，其具体步骤为：

首先，函数开始时先进行一些边界判断，确保堆的指针有效。
如果堆的当前元素数量等于堆的容量，即堆已满，需要进行动态扩容。这里使用realloc函数对堆的数组进行扩容，新的容量为原来容量的两倍。
将待插入的元素x放到堆数组的最后一个位置，并将堆的元素数量递增。
调用AdjustUp函数对刚插入的元素进行向上调整，保持堆的性质。

我们来实现一下这个操作：

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

2.4堆的向下调整

堆的向上调整是为了让堆在插入数据时能够保持堆的性质，而堆的向下调整操作是在删除根节点后，为了维护堆的性质而进行的操作。该操作的目的是将新的根节点下沉到合适的位置，使得根节点的值不大于它的左右子节点的值。堆的向下调整具体步骤为：

初始化子节点的索引child，设为父节点的左孩子节点的索引，即parent*2+1。
进入一个循环，判断当前节点是否有左孩子节点，如果有则执行循环体。
在循环体内，先假设左孩子节点的值最小，将child设为左孩子节点的索引。
检查右孩子节点是否存在，即child+1<size，如果存在且右孩子节点的值小于左孩子节点的值，则将child更新为右孩子节点的索引。
检查当前节点的值是否大于最小的子节点的值，如果是，则交换当前节点和最小子节点的值，将当前节点的索引设为子节点的索引child，并更新子节点的索引为新的左孩子节点的索引child=parent*2+1。
如果当前节点的值不大于最小子节点的值，即a[child]>=a[parent]，则跳出循环。
重复之前的步骤，直到当前节点没有左孩子节点为止。

我们来具体实现一下这个操作：

void AdjustDown(int* 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[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.5堆的删除

堆的删除具体操作步骤为：

调用Swap函数来交换小堆根节点（php->a[0]）和最后一个节点（php->a[php->size - 1]）的值。这样就将要删除的根节点移到了最后一个位置。
将小堆的大小减1，即php->size--，表示删除了一个节点。
最后，调用AdjustDown函数来对小堆进行向下调整，以维护小堆的性质。这样就完成了小堆的删除操作。

我们来实现一下这个操作：

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);
}