【数据结构初阶】顺序结构二叉树（堆）接口实现超详解

@TOC

1.树

1. 1 树的概念与结构

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。有一个特殊的结点，称为根结点，根结点没有前驱结点。

除根结点外，其余结点被分成 M(M>0)个互不相交的集合 T₁、T₂、…、T_m ，其中每一个集合T_i (1 <= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。

树形结构中，子树之间不能有交集，否则就不是树形结构。其实就是一个节点不能有多个前驱。

树可以看做是这样的：

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树

是现实中的树倒过来的样子。这里有一些不是树的结构存储作为对比：

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_完全二叉树_02

子树是不相交的（如果存在相交就是图了，图是另一种数据结构）
除了根结点外，每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边

1. 2 树的相关术语

以此图为例：

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_结点_03

父结点 / 双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
子结点 / 孩子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
结点的度：一个结点有几个孩子，他的度就是多少；比如A的度为 6，F的度为 2，K的度为 0
树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为 6
叶子结点 / 终端结点：度为 0 的结点称为叶结点；如上图：B、C、H、I...等结点为叶结点
分支结点 / 非终端结点：度不为 0 的结点；如上图： D、E、F、G...等结点为分支结点
兄弟结点 ：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图：B、C是兄弟结点
结点的层次 ：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推。
树的高度或深度：树中结点的最大层次；如上图：树的高度为 4
结点的祖先 ：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
路径：一条从树中任意节点出发，沿父节点 - 子节点连接，达到任意节点的序列；比如A到Q的路径为：A - E - J - Q； H到O的路径H - D - A - E - J - Q
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m(m > 0)棵互不相交的树的集合称为森林

1. 3 树的表示

孩子兄弟表示法 树结构相对线性表就比较复杂了，要存储表示起来也比较麻烦，既然保存数据，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里就先介绍其中最常用的孩子兄弟表示法：

struct TreeNode
 {
	 struct Node* child; 	// 最左边的孩子结点
	 struct Node* brother; 	// 指向其右边的下一个兄弟结点
	 int data; 				// 结点中的数据域
};

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_04

以这个二叉树为例，假如想从A找到I，就是：

A->child->child->brother->brother->child->brother

通过这样的存储方式，我们可以找到树上的每一个节点。

1. 4 树形结构实际运用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_05

2.二叉树

2. 1 概念与结构

在树形结构中，我们最常用的就是二叉树，一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二又树组成或者为空。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_结点_06

从上图可以看出二叉树具备以下特点:

二叉树不存在度大于 2 的结点
二叉树的子树有左右之分，次序不能颠倒，因此二又树是有序树

注意：对于任意的二又树都是由以下几种情况复合而成的：

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_结点_07

2. 2 特殊的二叉树

2. 2. 1 满二叉树

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

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_08

2. 2. 2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时（简单地讲，就是第X层没有完全放满时，X+1层不能有节点，且没有满的层的节点必须是从左往右排布的）称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_09

二叉树性质根据满二叉树的特点可知：

若规定根结点的层数为 1，则一棵非空二叉树的第i层上最多有 2^i-1 个结点
若规定根结点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h-1
若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度h = log₂(n+1)(log以2为底，n+1为对数)

2. 3 二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2. 3. 1 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二又树更适合使用顺序结构存储。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_10

通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 3. 2 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，现在我们接触的一般是二叉链。高阶数据结构如红黑树等会用到三叉链。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_完全二叉树_11

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_完全二叉树_12

3. 实现顺序结构二叉树（小堆）

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

3. 1 堆的概念与结构

如果有一个关键码的集合K = {k₀,k₁,k₂,…，k_n-1}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：

K_i <= K_2*i+1 (或K_i >= K_2*i+1 且 K_i <= K_2*i+2)

则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_二叉树_13

堆具有以下性质：

堆中某个结点的值总是不大于或不小于其父结点的值。
堆总是一棵完全二叉树。

二叉树性质：对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有:

若 i>0 ，i 位置结点的双亲序号为(i-1)/2；若i=0 ，i为根结点编号，无双亲结点
若 2i+1<n，左孩子序号：2i+1，2i+1>=n 否则无左孩子
若 2i+2<n，右孩子序号：2i+2，2i+2>=n 否则无右孩子

3. 2 堆的实现

我们先以小堆为例进行实现：

3. 2. 1 堆的定义

//小堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Heap;

其实可以看到，堆的底层结构和动态顺序表是一模一样的，所以部分接口和顺序表也是一样的，就简略介绍了。

3. 2. 2 初始化与销毁

创建将所有成员变量置为NULL或0。在main函数中创建堆变量再传入进行初始化，可以避免在销毁时对堆变量本身进行free。

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

销毁把动态申请的数组free掉，再把所有成员置为NULL或0就可以了。

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->arr);
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

3. 2. 3 交换

交换两个数的位置，下面的函数需要用到。

void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

3. 2. 4 入堆与向上调整函数

这里就是堆和顺序表不同的部分了。

如果我们想向堆中加入一个数据，该怎么做？直接将它放进数组就完成了吗？当然不行，为了确保在插入一个数据之后这个数组还能表示一个堆，我们需要先实现一个向上调整算法，在向顺序表插入新数据后，将这个数据向上调整到合适的位置来确保堆的正确。

//向上调整
void AdjustUp(HPDataType* arr, int child);

参数arr是堆的底层数组，参数child是要向上调整的数据。

要怎么向上调整？我们可以找到child的父节点parent，如果parent对应的数据比child小，就说明现在已经不用再进行调整了，堆已经正确了。如果如果parent对应的数据比child大，就交换这两个数。如果调整一次之后堆仍然不正确，就继续上面的步骤直到堆正确。如图：

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_结点_14

void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);
	int parent = (child - 1)/2;	//父节点
	while (child)	//注意child可能会被调整到根节点，这时候就不能再调整了
	{
		if (arr[child] < arr[parent])	//如果条件语句不成立，就说明堆已经成型
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;	//循环以上步骤
		}
		else
			break;
	}
}

接下来看入堆：有以下两个步骤：

参考顺序表向数组尾插数据
向上调整

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//插入数据
	if (hp->size == hp->capacity)
	{
		//扩容
		int newcapacity = hp->capacity == 0 ? 2 : 2 * hp->capacity;
		HPDataType* new = (HPDataType*)realloc(hp->arr, newcapacity * sizeof(HPDataType));
		if (!new)
		{
			perror("realloc");
			exit(1);
		}
		hp->arr = new;
		hp->capacity = newcapacity;
	}
	hp->arr[hp->size++] = x;
	//向上调整
	AdjustUp(hp->arr, hp->size - 1);
}

3. 2. 5 判空与取堆顶数据与堆的大小

判空

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

取堆顶数据 注意堆顶的下标是0。

HPDataType HeapTop(Heap* hp)
{
	assert(hp && hp->size);
	return hp->arr[0];
}

堆的大小

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

3. 2. 6 出堆与向下调整

堆这个数据结构如果要删除数据只能从堆顶删除（可以类比现实中的堆，肯定不能从中间抽数据，不然堆就塌了）。那该怎么删除数据呢？直接将堆顶元素删除吗？如果是这样，就要把后面所有元素向前挪动一位，而且两个孩子节点谁当父节点也是个问题。（在纸上画一画，很容易会发现这样删除真的很复杂）所以更合适的办法应该是将堆顶元素与堆的最后一个元素交换位置，将最后一个元素删除，再进行向下调整算法。

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_完全二叉树_15

向下调整和向上调整的思想是一样的，都是通过比较父节点与孩子节点并交换，直到堆是正确的。注意这里父节点应该和较小的孩子节点进行比较与交换，来确保交换（如果发生交换）之后父节点大于孩子节点。向下调整算法还有一个前提：左右子树必须是一个堆，才能调整。也就是说在调整之前，除了堆顶元素外，堆必须是正确的。

【数据结构初阶】顺序结构二叉树（堆）接口实现超详解_结点_16

void AdjustDown(HPDataType* arr, int parent, int n)
{
	assert(arr);
	int child = 2 * parent + 1;//左孩子
	while (child < n)	//如果已经调整到了叶子节点，child就已经大于n了，不能再调整了
	{
		//找较小的孩子，child++就是右孩子了
		if (child + 1 < n && arr[child] > arr[child + 1])
			child++;
		//这里和向上调整就一样了，比较，交换，循环
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

接下来就是出堆的完整函数了：

void HeapPop(Heap* hp)
{
	assert(hp && hp->size);
	//交换堆顶和最后一个元素
	Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
	//删除最后一个元素（原来的堆顶）
	hp->size--;
	//向下调整
	AdjustDown(hp->arr, 0, hp->size);
}

3. 2. 7 大堆

实现小堆之后，只需要在两个调整算法中更改一下调整的判断条件（比如原来是父节点比子节点大就交换，更改成父节点比子节点小就交换）就能实现大堆了，这里就不再赘述了。

谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！我会持续更新更多优质文章

秒客网