【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）

=========================================================================

相关代码gitee自取：

=========================================================================

接上期：

=========================================================================

1 . 非线性表里的树(Tree)

树的概念及结构：



树的概念

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

树的结构

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

除根节点外，其余节点被分成 M(M>0) 个互不相交的集合 T1 、T2 、……、Tm ，
其中每一个集合 Ti(1<= i <= m) 又是一棵结构与树类似的子树。
每棵子树的根节点有且只有一个前驱节点，可以有零个或多个后继节点

树是递归定义的

树形结构中，子树之间不能有交集，否则就不是树形结构

图示：



树的其它相关概念：

(有些概念对应意思不好理解，可以结合看下列示例图的例子)

概念名称对应意思下图中例子
节点的度 一个节点含有的子树个数称为该节点的度节点A的度为6
🔺叶节点
(终端节点) 度为0的节点称为叶节点节点B、C、H……为叶节点

🔺分支节点
(非终端节点)
度不为0的节点称为分支节点节点D、E、F……为分支节点
🔺父节点
(双亲节点) 若一个节点含有子节点，
则这个节点称为其子节点的父节点节点A是节点B的父节点
🔺子节点
(孩子节点) 一个节点含有的子树的根节点称为该节点的子节点节点B是节点A的子节点
兄弟节点 具有相同父节点的节点互称为兄弟节点节点B、C是兄弟节点
树的度 一棵树中，最大的节点的度称为树的度下图中树的度为6
🔺节点的层次 从根开始定义起，
根为第一(零)层，根的子节点为第二(一)层，
以此类推（建议从第一层起算，空树可用零层表示）节点A所在层为第一层，
节点B所在层为第二层……
🔺树的高度
(树的深度) 树中节点的最大层次下图中树的高度(深度)为4
堂兄弟节点 父节点(双亲节点)在同一层的节点互称为堂兄弟节点H、I互为兄弟节点
🔺节点的祖先 从根到该节点上的所有的分支节点都是祖先节点A是所有节点的祖先
🔺子孙 以某节点为根的子树中任一节点
都称为该节点的子孙所有节点都是节点A的子孙
森林由m(m>0)棵互不相交的树组成的集合称为森林

示例图：





树的存储（表示）：



树的表示方式：

树结构相对线性表就比较复杂了，要存储（表示）起来就比较麻烦了，
既要保存值域，也要保存节点和节点之间的关系

实际中树有很多种表示方式如：
双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等，
我们这里就简单了解其中最常用的（左）孩子（右）兄弟表示法
（树结构的最优设计）


（左）孩子（右）兄弟表示法结构：
                     //树中各节点数据域存储数据的类型：
                     typedef int DataType;
 
                     //（左）孩子（右）兄弟表示法：
                     struct TreeNode
                     {
                         //节点中的数据域：
                         DataType data;
 
                         //第一个孩子节点 -- 最左边的孩子节点：
                         struct TreeNode* firstchild;
 
                         //指向该节点下一个兄弟节点 -- 右边的兄弟节点：
                         struct TreeNode* nextbrother;
                     };
这个表示法本质是用链表实现树：

firstchild 指针 -- 相当于链表头指针，找到当前节点下一层的头节点

nextbrother 指针 -- 相当于链表遍历指针，可以往后遍历该层节点

使用示例图：

概念名称	对应意思	下图中例子
节点的度	一个节点含有的子树个数称为该节点的度	节点A的度为6
🔺叶节点 (终端节点)	度为0的节点称为叶节点	节点B、C、H……为叶节点
🔺分支节点 (非终端节点)	度不为0的节点称为分支节点	节点D、E、F……为分支节点
🔺父节点 (双亲节点)	若一个节点含有子节点，则这个节点称为其子节点的父节点	节点A是节点B的父节点
🔺子节点 (孩子节点)	一个节点含有的子树的根节点称为该节点的子节点	节点B是节点A的子节点
兄弟节点	具有相同父节点的节点互称为兄弟节点	节点B、C是兄弟节点
树的度	一棵树中，最大的节点的度称为树的度	下图中树的度为6
🔺节点的层次	从根开始定义起，根为第一(零)层，根的子节点为第二(一)层，以此类推（建议从第一层起算，空树可用零层表示）	节点A所在层为第一层，节点B所在层为第二层……
🔺树的高度 (树的深度)	树中节点的最大层次	下图中树的高度(深度)为4
堂兄弟节点	父节点(双亲节点)在同一层的节点互称为堂兄弟	节点H、I互为兄弟节点
🔺节点的祖先	从根到该节点上的所有的分支节点都是祖先	节点A是所有节点的祖先
🔺子孙	以某节点为根的子树中任一节点都称为该节点的子孙	所有节点都是节点A的子孙
森林	由m(m>0)棵互不相交的树组成的集合称为森林

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2 . 树中的二叉树(Binary Tree)

二叉树的概念及结构：



二叉树的概念

一棵二叉树是节点的一个有限集合，该集合满足：

或者为空
或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树的结构

二叉树不存在度大于2的节点
（所以节点的度可能是 0 即空树，也可能是 1 或 2 ）

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

图示：

注意：

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





特殊的二叉树

满二叉树

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

图示：

完全二叉树

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


简单理解:

假设树的高度是 K ，前 K-1 层是"满"的，
最后一层不一定满（至少有一个节点），且树从左到右是连续的
则该树即完全二叉树



注：

满二叉树是一种特殊的完全二叉树

完全二叉树的最后一层为满即是满二叉树

所以假设完全二叉树的高度为 K ，
节点总数最高是 2^K - 1 ；节点总数最少(最后一层只有一个节点)是 2^(K - 1)

图示：





二叉树的存储结构

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



顺序结构

顺序结构存储就是使用数组来存储，
任意位置通过下标可以找到父亲或者孩子，数组中下标为0的元素即为根节点

使用数组进行存储一般只适合表示完全二叉树（满二叉树），
因为不是完全二叉树的话会有空间的浪费

现实使用中只有堆才会使用数组来存储

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树


顺序结构(数学)规律：

通过父节点（下标）找到子节点（下标）：
左节点 ==》  leftchild = parent * 2 + 1
右节点 ==》  rightchild = parent * 2 + 2

通过子节点（下标）找到父节点（下标）：
父节点 ==》 parent = (child - 1) / 2
通过观察可以发现左节点下标都是奇数，右节点下标都是偶数，
(偶数-1) / 2 会向下取整，得到偶数父节点下标，
所以一个公式即可求得父节点

该规律只适用于完全二叉树，因为完全二叉树从左到右是连续的
（非完全二叉树也可以使用，但因为节点不一定是连续的，
所以数组中有些位置不存储元素，导致空间浪费）

图示：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3 . 完全二叉树中的堆(Heap)

堆的概念及结构



堆的概念

如果有一个关键码的集合   $K = \left \{ k_{0}, k_{1}, k_{2}, ...,k_{n-1}\right \}$ ，
把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：

$_{}^{}$ $K_{i} \leqslant K_{2*i+1}$ 且 $K_{i} \leqslant K_{2*i+2}$
（ $K_{i}\geqslant K_{2*i+1}$ 且 $K_{i}\geqslant K_{2*i+2}$ ）

其中 i = 0，1，2……

则称为小堆（或大堆）

将根节点最大的堆叫做最大堆或大根堆 -- 大堆

根节点最小的堆叫做最小堆或小根堆 -- 小堆



简单理解：

小堆 -- 各父节点值总是小于等于其子节点值（各子节点值总是大于等于其父节点值）
大堆 -- 各父节点值总是大于等于其子节点值（各子节点值总是小于等于其父节点值）



堆的结构

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

堆总是一棵完全二叉树

图示：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

4 . 堆的实现

使用二叉树的顺序结构实现堆

普通的二叉树并不适合用数组（顺序结构）来存储，因为会存在大量的空间浪费

而完全二叉树更适合使用顺序结构存储，
所以现实中通常把堆（一种完全二叉树）使用顺序结构的数组来存储

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两码事，
一个是数据结构，一个是操作系统中管理内存的一块区域分段

（详细解释在图片的注释中，代码分文件放下一标题处）

实现具体功能前的准备工作

在堆头文件中包含之后所需头文件

定义节点值(堆底层数组元素)的类型

定义堆类型

图示





---------------------------------------------------------------------------------------------



HeapInit函数 -- 对堆类型中的成员进行初始化

assert断言接收的堆类型指针不为空

将堆根节点指针置为NULL，
将堆当前节点个数置为0，
将堆当前开辟的空间单位置为0

图示





---------------------------------------------------------------------------------------------



HeapDestroy函数 -- 对堆类型进行销毁

assert断言接收的堆类型指针不为空

释放堆类型中以a为头开辟的动态空间


将堆当前节点个数和堆当前开辟的空间单位置为0

图示





---------------------------------------------------------------------------------------------



HeapPrint函数 -- 打印堆中各节点值

assert断言接收的堆类型指针不为空

使用for循环循环打印

图示





---------------------------------------------------------------------------------------------



Swap函数 -- 在向上向下调整操作中互换节点位置

向上调整（AdjustUp内部函数）和向下调整（AdjustDown内部函数）是在
推插入节点（HeapPush函数）和堆删除节点（HeapPop）操作中的重要步骤，
而在向上调整操作和向下调整操作中需要用到Swap函数，交换两节点值

该函数实现很简单，创建一个临时变量配合调换两节点值即可

图示





---------------------------------------------------------------------------------------------



AdjustUp内部函数
--
用于在插入节点后（HeapPush函数）向上调整该节点在堆中的位置

通过上面“顺序结构”中讲到的公式
通过子节点下标child找到其父节点下标parent

使用while循环进行向上调整

图示





---------------------------------------------------------------------------------------------



（难）HeapPush函数 -- 在堆类型中插入一个节点

assert断言接收的堆类型指针不为空

断言后要判断是否需要扩容，需要则进行扩容操作并检查是否扩容成功


空间足够后，将插入节点放入堆
插入后堆当前节点个数size++


插入节点后调用向上调整AdjustUp内部函数，
对插入节点在堆中的位置进行调整，
使得插入后整体还是一个堆（大堆或小堆）

图示





---------------------------------------------------------------------------------------------



HeapInitArray函数 -- 接收一个数组将其初始化为一个堆底层数组

实现了向上调试AdjusuUp内部函数后，
可以运用其来建堆（建大堆还是小堆取决于AdjustUp函数内的条件设置），
相比前面的HeapInit初始化函数，
该函数会直接为堆开辟动态空间，并放入各节点值

assert断言接收的堆类型指针不为空
assert断言数组a不为空


开辟动态空间并检查开辟情况


将堆当前节点个数置为n
将堆当前开辟的空间单位置为n


将数组a元素拷贝作为堆底层数组元素

再循环向上调整堆中的节点（底层数组元素）进行建堆

图示





---------------------------------------------------------------------------------------------



AdjustDown内部函数
--
用于在删除根节点后（HeapPush函数）向下调整堆，使其还是一个堆

通过上面“顺序结构”中讲到的公式
通过父节点下标parent找到其左子节点下标child

使用while循环循环向下调整堆（以小堆为例）


在while循环中，先找出当前两个子节点中的较小子节点下标


在while循环中，找到较小节点下标后，
判断是否需要向下调整，执行相应操作

图示





---------------------------------------------------------------------------------------------



（难）HeapPop函数 -- 删除堆类型根节点（删除当前堆中最值）

assert断言接收的堆类型指针不为空
assert断言堆节点个数（底层数组元素个数）不为0

使用交换节点Swap函数将根节点值和尾节点值交换
再将移至尾部的原根节点删除


使用向下调整AdjustDown内部函数对堆进行向下调整

图示





---------------------------------------------------------------------------------------------



HeapTop函数 -- 获取并返回推根节点值

assert断言接收的堆类型指针不为空
assert断言堆节点个数（底层数组元素个数）不为0

直接返回根节点值

图示





---------------------------------------------------------------------------------------------



HeapEmpty函数 -- 判断堆类型是否为空

assert断言接收的堆类型指针不为空

如果堆节点个数（底层数组元素个数）为0则说明堆为空

图示





---------------------------------------------------------------------------------------------



总体测试：





---------------------------------------------------------------------------------------------



HeapSort排序函数（难）
--
使用堆中向下调整的操作对普通数组进行排序（升序或降序）

建堆：
将要排序的数组看做一棵完全二叉树，
使用循环向下调整操作从倒数第一个父节点（非叶子节点）开始向下调整，
调整完成后，数组就会符合堆的性质（这里以小堆为例）
升序 -- 建大堆；降序 -- 建小堆

排序：
使用while循环进行排序，
把最小值（小堆根节点）和尾元素进行交换，
把除最小值的其它值看做堆，进行向下调整，选出次大小值，
调整好了最尾的一个值，再循环调整下一个

图示

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

5 . 对应代码

Heap.h -- 头文件


#pragma once
 
//在堆头文件中包含之后所需头文件：
#include 
#include 
#include 
#include 
 
 
//定义节点值(堆底层数组元素)的类型：
typedef int HPDataType;
 
//定义堆类型：
typedef struct Heap
{
	//因为底层是用顺序结构实现，
	//所以该类型和顺序表类似：
 
	//指向堆节点的指针：
	//（指向堆底层数组的首元素）
	HPDataType* a;
 
	//堆当前节点个数：
	//（堆底层数组的元素个数）
	int size;
 
	//堆当前开辟的空间单位：
	//（堆底层数组动态开辟的空间单位）
	int capacity;
 
}HP; //堆类型Heap重命名为HP
 
 
 
//堆初始化函数1 -- 对堆类型中的成员进行初始化
//接收 堆类型指针（php）
void HeapInit(HP* php);
 
//堆销毁函数 -- 对堆类型进行销毁
//接收 堆类型指针（php）
void HeapDestroy(HP* php);
 
//打印堆函数 -- 打印堆中各节点值
//接收 堆类型指针（php）
void HeapPrint(HP* php);
 
//节点位置互换函数 -- 在向上向下调整操作中互换节点位置：
//接收要互换位置的两个节点的指针（p1 和 p2）
void Swap(HPDataType* p1, HPDataType* p2);
 
//堆插入函数 -- 在堆类型中插入一个节点
//接收 堆类型指针（php）和插入节点的值（x）
void HeapPush(HP* php, HPDataType x);
 
//堆初始化函数2 -- 接收一个数组将其初始化为一个堆底层数组
//接收 堆类型指针（php）、数组首元素地址（a）、数组元素个数（n）
void HeapInitArray(HP* php, int* a, int n);
 
//堆删除函数 -- 删除堆类型根节点（删除当前堆中最值）
//接收 堆类型指针（php）
void HeapPop(HP* php);
 
//堆顶函数 -- 获取并返回推根节点值
//接收 堆类型指针（php）
HPDataType HeapTop(HP* php);
 
//判空函数 -- 判断堆类型是否为空
//接收 堆类型指针（php）
bool HeapEmpty(HP* php);

---------------------------------------------------------------------------------------------

Heap.c -- 实现文件


#define _CRT_SECURE_NO_WARNINGS 1
 
//包含堆头文件：
#include "Heap.h"
 
//堆初始化函数1 -- 对堆类型中的成员进行初始化
// （一开始不给值，之后使用函数插入值形成堆）
//接收 堆类型指针（php）
void HeapInit(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//(确保有成功创建堆类型可以被初始化）
	assert(php);
 
	//将堆根节点指针置为NULL：
	php->a = NULL;
	//将堆当前节点个数置为0：
	php->size = 0;
	//将堆当前开辟的空间单位置为0：
	php->capacity = 0;
}
 
 
 
//堆销毁函数 -- 对堆类型进行销毁
//接收 堆类型指针（php）
void HeapDestroy(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//确保有堆类型可以被销毁
	assert(php);
 
	//释放堆类型中以a为头开辟的动态空间：
	free(php->a);
 
	//将堆当前节点个数和堆当前开辟的空间单位置为0：
	php->a = NULL;
	php->size = php->capacity = 0;
}
 
 
 
//打印堆函数 -- 打印堆中各节点值
//接收 堆类型指针（php）
void HeapPrint(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//(确保有成功创建堆类型可以被打印）
	assert(php);
 
	//使用for循环循环打印：
	for (int i = 0; i < php->size; i++)
		//size有多少个节点就打印多少个节点值：
	{
		//通过下标打印节点值：
		printf("%d ", php->a[i]);
	}
 
	//换行：
	printf("\n");
}
 
 
 
//节点位置互换函数 -- 在向上向下调整操作中互换节点位置：
//接收要互换位置的两个节点的指针（p1 和 p2）
void Swap(HPDataType* p1, HPDataType* p2)
{
	//创建一个临时变量配合调换两节点值：
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
 
 
//在内部实现一个不对外声明的向上调整函数AdjustUp
//第一个参数接收 堆底层数组的首元素地址
//第二个参数接收 刚刚插入数组元素(子节点)的下标
void AdjustUp(HPDataType* a, int child)
{
	//使用之前讲到的公式，
	//通过子节点下标找到其父节点下标：
	int parent = (child - 1) / 2;
 
	//只要child还大于0就继续向上调整
	//需要向上层调整的话，上层节点的下标是比较小的
	//所以child不断调整就会越来越小
	while (child > 0)
	{
		//小堆中的向上调整：
		if (a[child] < a[parent])
			//小堆中子节点值比父节点值还小:
		//大堆中则把条件改为：
		//if (a[child] > a[parent])  //大堆的向上调整
		{
			//那就需要两者调换位置:
			Swap(&a[child], &a[parent]); 
 
			//值替换成功后，下标也要进行调整：
			//child移到上层后，下标为parent下标：
			child = parent;
 
			//child移到该层后，还可能是再上层父节点的子节点
			//可能还需要再向上调整，最坏的情况是移到成为堆的根节点：
			
			//再获得新父节点的下标：
			parent = (parent - 1) / 2;
		}
		else
			//如果小堆中子节点值已经大于等于父节点值了
			//即符合小堆的条件了
		{
			//那就不用进行向上调整，break退出循环：
			break;
		}
	}
}
 
//堆插入函数 -- 在堆类型中插入一个节点
//接收 堆类型指针（php）和插入节点的值（x）
void HeapPush(HP* php, HPDataType x)
{
	//assert断言接收的堆类型指针不为空：
	//确保有堆类型可以插入节点
	assert(php);
 
	//断言后要检查是否需要扩容：
	if (php->size == php->capacity)
		//堆当前节点个数 == 开辟空间单位
		//说明插入节点前需先进行扩容：
	{
		//创建变量存储新容量单位：
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//因为capacity初始化为0，所以可以使用三目操作符进行增容：
		//ps->capacity == 0 ? 4 : ps->capacity * 2
		//如果为0则直接增容到4，不为0则增容2倍
 
		//开辟动态空间：
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		//这里直接使用realloc函数进行动态空间开辟
		//如果realloc函数接收头指针（该函数第一个参数）为空，
		//那么它的作用相当于malloc函数
 
		//对开辟空间进行检查：
		if (tmp == NULL)
			//返回空指针，开辟失败：
		{
			//打印错误信息：
			perror("realloc fail");
			//终止程序：
			exit(-1);
		}
		
		//成功开辟空间后，将开辟空间的头指针赋给a：
		php->a = tmp;
		//将新容量单位赋给原容量单位：
		php->capacity = newCapacity;
	}
 
	//在堆中进行插入操作：
 
//堆：
//物理结构是个数组；逻辑结构是个树
//树就没有头插和尾插的概念了
//节点具体插入哪个位置要看情况
//只要插入值足够大或足够小，就可以一直往上一层替换
//节点插入堆后要保持还是一个堆，是从左到右连续的树
 
	//不论什么情况，先默认插入最尾部：
	//（即堆底层数组的末尾）
	//因为数组下标从0开始，
	//所以size即末尾插入节点下标：
	php->a[php->size] = x;
 
	//插入后堆当前节点个数size++：
	php->size++;
 
	//此时如果插入节点足够大（或足够小），
	//则刚好满足大堆（或小堆）的条件，
	//但如果不满足，就要将插入节点向树的上层调整,
	//且之后还会再执行该操作，
	//所以这里可以在文件内部定义一个向上调整函数AdjustUp
	//并进行调用：
	AdjustUp(php->a, php->size-1);
	//第一个参数接收 堆底层数组的首元素地址
	//第二个参数接收 刚刚插入数组元素(子节点)的下标
	// php->size-1 -- 前面插入节点后size++了
	// 所以这里的下标应-1 ，得到插入元素下标
}
 
 
 
//堆初始化函数2 -- 接收一个数组将其初始化为一个堆底层数组
// （给你底层数组的各个值，再向上调整形成堆）
//接收 堆类型指针（php）、数组首元素地址（a）、数组元素个数（n）
void HeapInitArray(HP* php, int* a, int n)
{
	//assert断言断言接收的堆类型指针不为空：
	//(确保有成功创建堆类型可以被初始化）
	assert(php);
	//assert断言数组a不为空：
	assert(a);
 
	//开辟动态空间：
	php->a = (HPDataType*)malloc(sizeof(HPDataType*) * n);
	//对开辟空间进行检查：
	if (php->a == NULL)
		//返回空指针，开辟失败：
	{
		//打印错误信息：
		perror("realloc fail");
		//终止程序：
		exit(-1);
	}
 
	//将堆当前节点个数置为n：
	php->size = n;
	//将堆当前开辟的空间单位置为n：
	php->capacity = n;
 
	//将数组元素拷贝作为堆底层数组元素：
	memcpy(php->a, a, sizeof(HPDataType) * n);
 
	//再循环向上调整堆中的节点（底层数组元素）进行建堆 ：
	for (int i = 1; i < n; i++)
	{
		AdjustUp(php->a, i);
	}
}
 
 
 
//在内部实现一个不对外声明的向下调整函数AdjustDown
//第一个参数接收 堆底层数组的首元素地址
//第二个参数接收 堆节点个数(底层数组元素个数)
//第三个参数接收 调换位置后的根节点（原尾节点）下标
void AdjustDown(HPDataType* a, int n, int parent)
{
	//（小堆中）向下调整需要获得比父节点parent小的子节点：
	// （该子节点要和其父节点调换位置）
 
	//可以先假设左子节点是比父节点小的：
	//获得根节点的左子节点（第一个子节点）下标：
	int child = parent * 2 + 1;
 
	//最坏情况：根节点成为叶子(没有子节点可以替换了)
	while (child < n)
		//左子节点下标如果>=堆节点个数(底层数组元素个数)
		//说明已经超出了数组范围，此时父节点已成为叶子无法再调换
	{
		//如果我们上面假设是错的：
		if (child + 1 < n  &&  a[child + 1] < a[child])
		//大堆中则把条件改为：
		//if (child + 1 < n  &&  a[child + 1] > a[child]) //大堆的向下调整
			// child+1 即右子节点的下标
				/*	左右子节点都存在才用比较出较小节点：	
				防止不存在的右子节点越界：child + 1 < n
				上面只要左子节点在数组就能进入while循环
				而左子节点可能就是数组最后一个元素了
				可能会出现左子节点存在而右子节点不存在的情况
				所以要在右子节点存在的情况下比较出较小节点
				/没有右子节点直接使用左子节点。
				*/
			//如果右子节点比左子节点小：
		{
			//就要获得右子节点（较小子节点）下标：
			++child; //自增后即右子节点下标
		}
 
		//到这里就获得较小节点的下标：
		//（不关心是左子节点还是右子节点，只要值小的节点）
 
		//（小堆中）如果较小节点比父节点还小
		if (a[child] < a[parent])
		//大堆中则把条件改为：
		//if (a[child] > a[parent]) //大堆的向下调整
		{
			//那就需要调换两者位置：
			Swap(&a[child], &a[parent]);
 
			//调换两节点值后，下标也要刷新：
			parent = child;
 
			//此时新的子节点下标为：
			child = parent * 2 + 1;
		}
		else
			//如果较小节点已经比父节点大了：
		{
			//那就符合小堆的条件，没必要调换：
			break; //退出循环
		}
		
	}
}
 
//堆删除函数 -- 删除堆类型根节点（删除当前堆中最值）
//接收 堆类型指针（php）
void HeapPop(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//确保有堆类型可以删除根节点
	assert(php);
	//assert断言堆节点个数（底层数组元素个数）不为0
	//确保有节点可以删除：
	assert(php->size > 0);
 
		/*
		如果进行挪动覆盖第一个位置的根节点
		会导致剩下的节点关系乱套（兄弟变父子）
		最终结果可能不一定是堆，
		而且数组中挪动覆盖效率本来就不高
		所以可以将根节点和尾节点交换位置
		再进行尾删，就实现了删除根节点
		且数组中尾删效率较高，
		*/
 
	//将根节点值和尾节点值交换:
	Swap(&php->a[0], &php->a[php->size - 1]);
	//	&php->a[0] ：根节点值
	//	&php->a[php->size - 1] ：尾结点值
 
	//再将移至尾部的原根节点删除：
	--php->size; //直接元素个数size-1即可
	
		/*
		此时堆的左右子树的结构没有变化
		左右子树依然是小堆（大堆）
		有了这个前提就可以进行向下调整：
		因为前面根节点和尾节点交换位置
		所以现在的根节点（原尾结点）可能就要比起子节点大了
		树整体不符合小堆条件，所以要进行向下调整
		（注：向上调整的前提是前面节点符合堆的条件）
		向下调整操作：
		成为根节点后，跟其两个子节点比较
		如果子节点比较小，则互换位置
		互换位置后再跟下一层子节点比较
		如果子节点比较小，则互换位置
		以此类推，最坏情况是到成为叶子为止
		（小堆中大的值往下移，小的值往上走）
		*/
 
	//所以这里可以在文件内部定义一个向下调整函数AdjustDown
	//并进行调用：
	AdjustDown(php->a, php->size, 0);
	//根节点在底层数组中下标是0
 
		/*
		* 该函数的意义和示例：
		该函数的意义是删除第一小的值（小堆中）
		再找到第二小的值，以此类推，可以依次找到数组的最小值
		示例：“该城市排名前10的蛋糕店” 小堆根元素就第一好的店，
		使用该函数后找到第二好的店，以此类推……
		*/
	
		/*
		* 该函数时间复杂度：
		向下或向上调整操作最好情况执行1次，最坏情况执行树的高度次
		即时间复杂度为 O(logN)，10亿个值只需调整30多次 -- 很优秀
		 （ log -- 默认以2为底 ）
		*/
 
}
 
 
 
//堆顶函数 -- 获取并返回推根节点值
//接收 堆类型指针（php）
HPDataType HeapTop(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//确保有堆类型可以获取根节点值
	assert(php);
	//assert断言堆节点个数（底层数组元素个数）不为0
	//确保堆类型中有节点：
	assert(php->size > 0);
 
	//直接返回根节点值：
	return php->a[0];
}
 
 
 
//判空函数 -- 判断堆类型是否为空
//接收 堆类型指针（php）
bool HeapEmpty(HP* php)
{
	//assert断言接收的堆类型指针不为空：
	//确保有堆类型可以获取根节点值
	assert(php);
 
	//如果堆节点个数（底层数组元素个数）为0则说明堆为空：
	return php->size == 0;
	//php->size = 0 -- 成立返回true，堆为空
	//php->size = 0 -- 不成立返回false，堆不为空 
}

---------------------------------------------------------------------------------------------

Test.c -- 测试文件


#define _CRT_SECURE_NO_WARNINGS 1
 
//包含堆头文件：
#include "Heap.h"
 
//测试函数 -- 未排序
void Test0()
{
	//创建一个数组创建要放入堆中的各节点值
	int a[] = { 65,100,70,32,50,60 };
	//计算数组长度：
	int alength = sizeof(a) / sizeof(int);
 
	//创建堆类型变量：
	HP hp;
 
	//使用HeapInit函数进行初始化：
	HeapInit(&hp);
 
 
	//使用for循环将数组各值放入堆类型变量中：
	for (int i = 0; i < alength; i++)
	{
		//堆类型变量hp在还没有HeapPush之前只是完全二叉树
		//在使用HeapPush函数插入并排序后就成了堆,
		//		所以建堆的方式之一就是一直push：
 
		//使用HeapPush函数插入节点：
		HeapPush(&hp, a[i]);
	}
 
	printf("当前堆:> ");
	//使用HeapPrint函数打印堆：
	HeapPrint(&hp);
 
	//使用HeapEmpty函数判断堆是否为空：
	while (!HeapEmpty(&hp))
		//不为空就获取堆根节点值：
	{
		//使用HeapTop函数获取堆根节点值并打印：
		printf("当前堆根节点值：> %d\n", HeapTop(&hp));
 
		//（小堆中）使用HeapPop函数删除当前根节点，
		// 并将第二小的节点设置为新的根节点：
		HeapPop(&hp);
	}
 
	//使用HeapDestroy函数进行销毁：
	HeapDestroy(&hp);
}
 
 
测试函数 -- 进行排序
//
堆排序函数（优化前） -- 利用堆类型对普通数组进行排序（升序或降序）
第一个参数：	接收堆底层数组的首元素地址
第二个参数：	堆底层数组的元素个数
//void HeapSort(int* a, int n)
//{
//	//创建堆类型变量：
//	HP hp;
//
//	//使用HeapInit函数进行初始化：
//	HeapInit(&hp);
//
//	//使用for循环将数组各值放入堆类型变量中：
//	for (int i = 0; i < n; i++)
//	{
//		//堆类型变量hp在还没有HeapPush之前只是完全二叉树
//		//在使用HeapPush函数插入并排序后就成了堆,
//		//		所以建堆的方式之一就是一直push：
//
//		//使用HeapPush函数插入节点：
//		HeapPush(&hp, a[i]);
//	}
//
//	//printf("当前堆:> ");
//	使用HeapPrint函数打印堆：
//	//HeapPrint(&hp);
//
//	int i = 0;
//	//使用HeapEmpty函数判断堆是否为空：
//	while (!HeapEmpty(&hp))
//		//不为空就获取堆根节点值：
//	{
//		//（小堆中）依次将堆类型的根节点值赋给数组a，
//		//运用堆实现将数组从小到大排序：
//		a[i++] = HeapTop(&hp);
//
//		//（小堆中）使用HeapPop函数删除当前根节点，
//		// 并将第二小的节点设置为新的根节点：
//		HeapPop(&hp);
//	}
//
//	//使用HeapDestroy函数进行销毁：
//	HeapDestroy(&hp);
//}
 这种排序的缺陷：
 1. 得先有一个堆的数据结构
 2. 空间复杂度的消耗
//void Test1()
//{
//	//创建一个堆底层数组 -- 节点值随机；未进行排序
//	int a[] = { 65,100,70,32,50,60 };
//
//	//计算数组长度：
//	int alength = sizeof(a) / sizeof(int);
//
//	printf("运用堆排序前的数组:> ");
//	//运用堆排序后前的数组：
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//	
//	//使用HeapSort函数对未进行排序的堆底层数组进行排序：
//	HeapSort(a, alength);
//
//	printf("运用堆排序后的数组:> ");
//	//运用堆排序后的数组：
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}
 
 
 
测试函数 -- 进行排序
//
堆排序函数（优化后） -- 利用堆类型的思路对普通数组进行排序（升序或降序）
第一个参数：	接收堆底层数组的首元素地址
第二个参数：	堆底层数组的元素个数
//void HeapSort(int* a, int n)
//{	
//	//之前是使用HeapPush函数创建堆类型后，
//	//再运用到普通数组的排序中，
//	//那我们也可以不用堆，
//	//直接使用HeapPush函数的思路将普通数组建成堆：
//	
//  //向上调整建堆 -- 时间复杂度 -- O(N*logN)
//	//将数组看做完全二叉树，再进行建堆：
//	//在AdjustUp中可设置为是大堆调整还是小堆调整
//	for (int i = 1; i < n; i++)
//		//从数组第二个元素（下标为1）开始排序，第一个元素默认为根节点，
//		//使用AdjustUp函数后再进行进一步调整：
//	{
//		//之前是在堆类型的操作中使用了AdjustUp调整函数
//		//这里在普通数组上也可以使用AdjustUp调整函数
//		//只是堆类型需要扩容，而普通数组不需要扩容而已
//		//把普通数组按大堆或小堆的方式进行调整：
//		AdjustUp(a, i);
//	}
//
//	//现在首元素就相当于（小堆）根节点，即最小值
//	//要想再选出次小的值，只能把剩下的数据看做堆
//	//但是父子关系全乱了，剩下数据也不一定还是堆
//	//可以再重新建堆，但是代价太大了
//
//	//还有一个思路：升序（从小到大）用大堆
//	//把数组建成大堆，把最大值选出来后，把最大值和最尾值交换
//	//这样升序中（从小到大）也排好了一个值，即最大值放尾部
//	//再把除最大值的其它值看做堆，进行向下调整，选出次大值
//	//放倒数第二个位置，循环这套操作 -- 时间复杂度NlogN
//	//（同样的道理，如果是降序（从大到小）就用小堆）
//
//	//以降序（从大到小）用小堆为例：
//
//	//先获得数组尾元素下标：
//	int end = n - 1;
//	//使用while循环进行排序：
//	while (end > 0)
//		//数组尾元素下标大于说明至少还有两个元素，继续排序：
//	{
//		//把最小值（小堆根节点）和尾元素进行交换：
//		Swap(&a[0], &a[end]);
//
//		//把除最小值的其它值看做堆，进行向下调整，选出次大小值：
//		AdjustDown(a, end, 0);
//		//end即是除最小值的其它值（数组前n-1个值）
//
//		//这样就调整好了最尾的一个值，end-1循环调整下一个：
//		end--;
//	}
//  
//}
//
//void Test2()
//{
//	//创建一个堆底层数组 -- 节点值随机；未进行排序
//	//int a[] = { 75,65,100,32,50,60 };
//	int a[] = { 2,3,5,7,4,6,8 };
//
//	//计算数组长度：
//	int alength = sizeof(a) / sizeof(int);
//
//	printf("运用堆排序前的数组:> ");
//	//运用堆排序后前的数组：
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//
//	//使用HeapSort函数对未进行排序的堆底层数组进行排序：
//	HeapSort(a, alength);
//
//	printf("运用堆排序后的数组:> ");
//	//运用堆排序后的数组：
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}
 
 
 
//测试函数 -- 进行排序
//堆排序函数（再再优化） -- 只用向下调整对普通数组进行排序（升序或降序）
//第一个参数：	接收堆底层数组的首元素地址
//第二个参数：	堆底层数组的元素个数
void HeapSort(int* a, int n)
{
	//向下调整建堆 -- 时间复杂度：O(N)
	//将要排序的数组看做一棵完全二叉树
	//从倒数第一个父节点（非叶子节点）开始向下调整：
	for (int i = (n-1-1)/2; i >= 0; i--)
		//(n-1-1)/2 -- n-1是最后叶子的下标，该叶子-1再/2（公式）
		//找到其父节点（倒数第一个父节点），调整好该父节点后i--
		//再调整上一父节点，直到向下调整到根节点
	{
		AdjustDown(a, n, i); //从i位置开始向下调整
	}
	//建堆最坏情况下执行次数：T(N) = N - log(N+1)
	//因此：建堆的时间复杂度为O(N)
 
	//开始排序：以降序（从大到小）用小堆为例：
 
	//先获得数组尾元素下标：
	int end = n - 1;
	//使用while循环进行排序：
	while (end > 0)
		//数组尾元素下标大于说明至少还有两个元素，继续排序：
	{
		//把最小值（小堆根节点）和尾元素进行交换：
		Swap(&a[0], &a[end]);
 
		//把除最小值的其它值看做堆，进行向下调整，选出次大小值：
		AdjustDown(a, end, 0);
		//end即是除最小值的其它值（数组前n-1个值）
 
		//这样就调整好了最尾的一个值，end-1循环调整下一个：
		end--;
	}
 
}
 
void Test3()
{
	//创建一个堆底层数组 -- 节点值随机；未进行排序
	//int a[] = { 75,65,100,32,50,60 };
	int a[] = { 2,3,5,7,4,6,8 };
 
	//计算数组长度：
	int alength = sizeof(a) / sizeof(int);
 
	printf("运用堆排序前的数组:> ");
	//运用堆排序后前的数组：
	for (int i = 0; i < alength; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
 
	//使用HeapSort函数对未进行排序的堆底层数组进行排序：
	HeapSort(a, alength);
 
	printf("运用堆排序后的数组:> ");
	//运用堆排序后的数组：
	for (int i = 0; i < alength; i++)
	{
		printf("%d ", a[i]);
	}
 
}
 
 
//主函数：
int main() 
{
	//Test0();
	//Test1();
	//Test2();
	Test3();
 
	return 0;
}

相关阅读:
java 多线程& notifyAll()方法：通知所有线程——73
fastTEXT入门自然语言处理NLP
Pandas常用操作命令（六）——数据分组groupby
三个pdf工具和浏览软件（pdftk，muppdf，epdfview）
校园表白墙源码修复版
 C++11 initializer_list 轻量级初始化列表的使用场景（让自定义类可以用初始化列表的形式来实例化对象）
Redis 常见问题
 解线性方程组python实现直接分解法（Doolittle，克劳特，追赶法）
5 分钟教你快速掌握 GitHub Actions 自动部署博客
 华为ensp模拟器实现通信安全（交换机）
原文地址：https://blog.csdn.net/weixin_63176266/article/details/133271039

【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）

1 . 非线性表里的 树(Tree)

树的概念及结构：

树的概念

树的结构

图示：

树的其它相关概念：

示例图：

树的存储（表示）：

树的表示方式：

（左）孩子（右）兄弟表示法结构：

这个表示法本质是用链表实现树：

使用示例图：

2 . 树中的 二叉树(Binary Tree)

二叉树的概念及结构：

二叉树的概念

二叉树的结构

图示：

注意：

特殊的二叉树

满二叉树

图示：

完全二叉树

简单理解:

注：

图示：

二叉树的存储结构

顺序结构

顺序结构(数学)规律：

图示：

3 . 完全二叉树中的 堆(Heap)

堆的概念及结构

堆的概念

则称为小堆（或大堆）

将根节点最大的堆叫做最大堆或大根堆 -- 大堆

根节点最小的堆叫做最小堆或小根堆 -- 小堆

简单理解：

堆的结构

图示：

4 . 堆的实现

使用二叉树的顺序结构实现堆

（详细解释在图片的注释中，代码分文件放下一标题处）

实现具体功能前的准备工作

图示

HeapInit函数 -- 对堆类型中的成员进行初始化

图示

HeapDestroy函数 -- 对堆类型进行销毁

图示

HeapPrint函数 -- 打印堆中各节点值

图示

Swap函数 -- 在向上向下调整操作中互换节点位置

图示

AdjustUp内部函数 -- 用于在插入节点后（HeapPush函数）向上调整该节点在堆中的位置

图示

（难）HeapPush函数 -- 在堆类型中插入一个节点

图示

HeapInitArray函数 -- 接收一个数组将其初始化为一个堆底层数组

图示

AdjustDown内部函数 -- 用于在删除根节点后（HeapPush函数）向下调整堆，使其还是一个堆

图示

（难）HeapPop函数 -- 删除堆类型根节点（删除当前堆中最值）

图示

HeapTop函数 -- 获取并返回推根节点值

图示

HeapEmpty函数 -- 判断堆类型是否为空

图示

总体测试：

HeapSort排序函数（难） -- 使用堆中向下调整的操作对普通数组进行排序（升序或降序）

图示

5 . 对应代码

Heap.h -- 头文件

Heap.c -- 实现文件

Test.c -- 测试文件

1 . 非线性表里的树(Tree)

2 . 树中的二叉树(Binary Tree)

3 . 完全二叉树中的堆(Heap)

AdjustUp内部函数
--
用于在插入节点后（HeapPush函数）向上调整该节点在堆中的位置

AdjustDown内部函数
--
用于在删除根节点后（HeapPush函数）向下调整堆，使其还是一个堆

HeapSort排序函数（难）
--
使用堆中向下调整的操作对普通数组进行排序（升序或降序）