一、定义
树是一种非线性结构，由若干个结点构成，具有以下特点：
•一个根节点，没有前驱结点
•除根结点外，其余结点被分成 M(M>0)个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti(1 <= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有。个或多个后继。因此，树是递归定义的。
•没有环，层级关系明显，子树是不相交的
•除了根结点外，每个结点有且仅有一个父结点
•一棵N个结点的树有N-1条边
二、树的基本术语
•父结点：若一个结点含有子结点，则这个结点成为其子结点的父结点；如上图：A是B的父结点
•孩子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
•结点的度：一个结点有几个孩子，他的度就是多少;比如A的度为6，F的度为2，K的度为0
•树的度:棵树中，最大的结点的度称为树的度;如上图:树的度为6
•叶子结点/终端结点:度为 。的结点称为叶结点;如上图: B、C、H、I...等结点为叶结点
•分支结点/非终端结点:度不为0的结点;如上图:D、E、F、G...等结点为分支结点
•兄弟结点:具有相同父结点的结点互称为兄弟结点(亲兄弟);如上图:B、C是兄弟结点
•结点的层次:从根开始定义起，根为第1层，根的子结点为第2层，以此类推
•树的高度或深度:树中结点的最大层次;如上图:树的高度为4
•结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
•路径:一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列;比如A到Q的路径为:A-E-J-Q;H到Q的路径H-D-A-E-J-Q
•子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙
•森林:由m(m>0)棵互不相交的树的集合称为森林;
三、二叉树
上面讲的是树的通用概念，实际学习和做题时，我们最常接触的是二叉树。
这是树的一种特殊形式，每个结点最多只有两个子结点，通常称为左孩子和右孩子。
二叉树不存在度大于2 的结点
二叉树的子树有左右之分，次序不能颠倒，因此二又树是有序树
由于结构简洁，便于递归和存储，很多重要的数据结构和算法（如：二叉搜索树、堆、哈夫曼树等）都是基于二叉树实现的。
所以本次笔记重点整理关于二叉树的相关知识点。
3.1特殊的二叉树
1. 满二叉树
如果一棵二叉树中，每一层的结点数都达到了最大值（也就是没有空位），那这棵树就是满二叉树。
通俗理解就是：所有结点不是有两个孩子，就是一个不缺的叶子结点，整个树长得特别对称、饱满。
如果一棵树的层数是 k，那它的结点总数必须是 2^k - 1，才可能是满二叉树。
2. 完全二叉树
完全二叉树是从满二叉树“稍微松一点”的版本，但它依然非常规整。它的定义可以简单理解为：
> 从上到下、从左到右地把结点填满，中间不能有空位。
也就是说，除了最后一层可能不满，其它层都必须是满的，并且最后一层的结点必须集中在左边，不能“东缺一个西缺一个”。
完全二叉树的好处是：
它可以用数组非常高效地存储（堆就是用完全二叉树构建的）
编号有规律：如果一个结点编号是 i，那它的左孩子是 2i + 1，右孩子是 2i + 2
需要注意的是： 满二叉树其实就是一种特殊的完全二叉树。
3.2二叉树的性质
•对于具有 n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从
0 开始编号，则对于序号为 i的结点有:
1. 若 i>0 ，i位置结点的双亲序号:(i-1)/2; i=0,i为根结点编号，无父结点
2.若 2i+1<n，左孩子序号: 2i+1，2i+1>=n则无左孩子
3.若 2i+1<n，右孩子序号：2i+2, 2i+2>=n则无右孩子
在二叉树的存储方式中，我们主要采用的是“父子结点”结构，也就是每个结点通过指针（或下标）记录它的左孩子和右孩子，不记录兄弟或父结点。这种方式最直观，也是最常见的处理方式，特别适合用来实现递归操作和遍历算法。接下来我们写的二叉树用的都是这种结构。
3.3二叉树的存储结构
1. 顺序存储结构（仅适用于完全二叉树）
顺序存储就是用一个一维数组来存储二叉树的结点，按照从上到下、从左到右的顺序依次编号。
这种方式的前提是：二叉树的结构必须足够规整，比如完全二叉树或满二叉树，否则会出现大量数组空间浪费。
数组下标与结点之间的对应关系如下：
假设某个结点在数组下标为 i 的位置上（从0开始编号），那么：
它的父结点下标是 (i - 1) / 2（i ≠ 0 时）
它的左孩子下标是 2 * i + 1（若存在）
它的右孩子下标是 2 * i + 2（若存在）
实际应用中，像“堆排序”、“优先队列”等结构中用的就是这种顺序存储方式。不过在我们写代码处理普通的二叉树（不一定是完全的）时，大多数情况还是使用链式存储结构更灵活，支持动态扩展，也更适合递归处理。
2.链式存储结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
因此，接下来我们所使用的二叉树结构，都是基于父子关系的二叉链式存储：每个结点只记录它的左孩子和右孩子，不记录父结点或兄弟结点，这种结构简洁直观，特别适合递归实现和遍历操作。
3.4二叉树的基本操作与递归实现
构建一棵二叉树（递归建树）
3.4.1头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>//定义链式结构的二叉树//BTDataType 是一个自定义类型名，这里被定义为 char 类型
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data; // 节点存储的数据，类型为上面定义的BTDataTypestruct BinaryTreeNode* left;// 指向左子树节点的指针，若没有左子树则为NULLstruct BinaryTreeNode* right;// 指向右子树节点的指针，若没有右子树则为NULL
}BTNode;// 使用BTNode作为struct BinaryTreeNode的别名//创建一个结点
BTNode* buyNode(BTDataType x);//递归输入构建二叉树（先序输入，空结点用"#"表示）
BTNode* CreateBinaryTree();//前序遍历——根左右
void preOrder(BTNode* root);//中序遍历
void inOrder(BTNode* root);//后序遍历
void postOrder(BTNode* root);// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);//int BinaryTreeSize(BTNode* root,int* psize);// ⼆叉树叶⼦结点个数int BinaryTreeLeafSize(BTNode* root);// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);//层序遍历
void leverOrder(BTNode* root);
3.4.2创建单个结点
// 创建一个新的二叉树结点，数据为 x，左右孩子为空
BTNode* buyNode(BTDataType x) {BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL) {perror("malloc failed");exit(EXIT_FAILURE);}node->data = x;// 存储传入的数据node->left = NULL; // 左子树初始化为空node->right = NULL; // 右子树初始化为空return node;// 返回指向新结点的指针
}
}3.4.3递归创建二叉树
// 根据先序输入创建一棵二叉树，空结点用 '#' 表示
BTNode* CreateBinaryTree() {char ch;scanf(" %c", &ch); // 注意前面有空格，吸收换行if (ch == '#') {return NULL;}BTNode* root = buyNode(ch);//创建一个新的二叉树结点，并将输入字符 ch 作为结点的数据存储起来root->left = CreateBinaryTree(); // 构建左子树root->right = CreateBinaryTree(); // 构建右子树return root;
}3.4.5前序遍历——根左右
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}3.4.6中序遍历——左根右
void inOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}inOrder(root->left);printf("%c ", root->data);inOrder(root->right);
}3.4.7后序遍历——左右根
void postOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}postOrder(root->left);postOrder(root->right);printf("%c ", root->data);
}关于前中后序遍历常考：
1.中序+前序推后序：
•前序第一个一定是根结点
•在中序序列中找到这个根的位置，它左边的部分就是左子树的节点，右边的部分是右子树的节点；然后在前序中分别对应左子树和右子树部分，继续递归找子树的根结点。
•对左右子树递归构建
•遍历构建好的树得到后序序列
2.中序+后序推前序：
•后序最后一个是根；
•同理，去中序中找根的位置，划分出左右子树；递归找子树的根结点
•递归构建左右子树；
•遍历构建好的树得到前序序列。
3.前序 + 后序 → 无法唯一确定树（中序缺失）
这是一个易错点！
> 比如：
前序：A B
后序：B A
可能是：
A 是根，B 是左孩子
A 是根，B 是右孩子
所以不唯一！
3.4.8求二叉树结点个数
/*1. 空树的节点数为 0（递归终止条件）2. 非空树的节点数 = 1（根结点） + 左子树结点数 + 右子树结点数3. 通过后序遍历递归计算每个子树的节点数*/
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}求结点个数递归展开演示
目标二叉树：
A/ \B C/ \
D E计算过程：
根节点 A：
1 + BinaryTreeSize(B) + BinaryTreeSize(C)左子树 B 的计算：
1 + BinaryTreeSize(D) + BinaryTreeSize(E)
= 1 + 1（D是叶子） + 1（E是叶子）
= 3右子树 C 的计算：
1 + 0（无左子树） + 0（无右子树）
= 1最终结果：
1（A） + 3（B子树） + 1（C子树） = 53.4.9求⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}// 如果当前节点没有左右子节点，它是叶子节点，返回1if (root->left == NULL && root->right == NULL){return 1;}// 递归计算左子树和右子树的叶子节点数量，并返回总和return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}演示
如下二叉树
A/ \B C/ / \D E F计算过程：
1.根节点 A：
BinaryTreeLeafSize(A) = BinaryTreeLeafSize(B) + BinaryTreeLeafSize(C)2.左子树 B：
BinaryTreeLeafSize(B) = BinaryTreeLeafSize(D) + BinaryTreeLeafSize(NULL)= 1 + 0 // D 是叶子节点，返回 1= 13.右子树 C：
BinaryTreeLeafSize(C) = BinaryTreeLeafSize(E) + BinaryTreeLeafSize(F)= 1 + 1 // E 和 F 都是叶子节点= 24.汇总：
BinaryTreeLeafSize(A) = 1 + 2 = 33.4.10求二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}// 当k递减到1时，表示当前层是目标层，返回1个节点if (k == 1){return 1;}// 递归计算左子树和右子树的第k-1层节点数量，并返回总和// 每递归一层，k减1，直到k=1时停止递归return BinaryTreeLevelKSize(root->left, k - 1)+ BinaryTreeLevelKSize(root->right, k - 1);
}演示：
如下二叉树
A(1)/ \B(2) C(2)/ \ \D(3) E(3) F(3)
//括号里面的数字代表层数目标是计算第 3 层（k=3）的节点数。
递归调用展开过程
1.初始调用BinaryTreeLevelKSize(A, 3)
当前节点是 A，k=3，不满足终止条件，递归调用：
return BinaryTreeLevelKSize(B, 2) + BinaryTreeLevelKSize(C, 2);2.左子树递归：BinaryTreeLevelKSize(B, 2)
当前节点是 B，k=2，仍不满足终止条件，继续递归：
return BinaryTreeLevelKSize(D, 1) + BinaryTreeLevelKSize(E, 1);左子树的左子树 BinaryTreeLevelKSize(D, 1)：k=1满足终止条件，返回1
左子树的右子树 BinaryTreeLevelKSize(E, 1)：k=1满足终止条件，返回1
汇总：1+1=2
3.右子树递归：BinaryTreeLevelKSize(C, 2)
当前节点是 C，k=2，继续递归：
return BinaryTreeLevelKSize(NULL, 1) + BinaryTreeLevelKSize(F, 1);右子树的左子树 BinaryTreeLevelKSize(NULL, 1)：结点为空，返回0
右子树的左子树 BinaryTreeLevelKSize(F, 1)：k=1，满足终止条件，返回1
汇总：0+1=1
4.最终汇总：初始调用结果为：2（左子树）+1（右子树）=3
3.4.11⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}// 递归计算左子树的深度int leftDep = BinaryTreeDepth(root->left);// 递归计算右子树的深度int rightDep = BinaryTreeDepth(root->right);// 当前树的深度为左右子树深度的最大值加1（加上当前根节点）return 1 + (leftDep > rightDep ? leftDep : rightDep);
}演示：
如下二叉树：
A(1)/ \B(2) C(2)/ / \D(3) E(3) F(3)|G(4)括号内的数字表示节点的实际深度（从根节点 1 开始计数）。我们的目标是计算这棵树的最大深度。
递归调用展开过程
1.初始调用 BinaryTreeDepth(A)
// 当前节点：A，k=1
int leftDep = BinaryTreeDepth(B); // 递归计算左子树B的深度
int rightDep = BinaryTreeDepth(C); // 递归计算右子树C的深度
return 1 + max(leftDep, rightDep); // 等待子树结果返回后计算2.递归计算左子树 BinaryTreeDepth(B)
// 当前节点：B，k=2
int leftDep = BinaryTreeDepth(D); // 递归计算D的深度
int rightDep = BinaryTreeDepth(NULL); // 右子树为空
return 1 + max(leftDep, rightDep);3.递归计算 BinaryTreeDepth(D)
// 当前节点：D，k=3（叶子节点）
int leftDep = BinaryTreeDepth(NULL); // 左子树为空 → 返回0
int rightDep = BinaryTreeDepth(NULL); // 右子树为空 → 返回0
return 1 + max(0, 0) = 1; // D的深度为1，返回给上层4.回溯到 B 节点
// B的左子树深度为1（来自D），右子树深度为0（空）
return 1 + max(1, 0) = 2; // B的深度为2，返回给上层5.递归计算右子树 BinaryTreeDepth(C)
// 当前节点：C，k=2
int leftDep = BinaryTreeDepth(E); // 递归计算E的深度
int rightDep = BinaryTreeDepth(F); // 递归计算F的深度
return 1 + max(leftDep, rightDep);6.递归计算 BinaryTreeDepth(E)
// 当前节点：E，k=3
int leftDep = BinaryTreeDepth(G); // 递归计算G的深度
int rightDep = BinaryTreeDepth(NULL); // 右子树为空
return 1 + max(leftDep, rightDep);7.递归计算 BinaryTreeDepth(G)
// 当前节点：G，k=4（叶子节点）
int leftDep = BinaryTreeDepth(NULL); // 左子树为空 → 返回0
int rightDep = BinaryTreeDepth(NULL); // 右子树为空 → 返回0
return 1 + max(0, 0) = 1; // G的深度为1，返回给上层8.回溯到 E 节点
// E的左子树深度为1（来自G），右子树深度为0（空）
return 1 + max(1, 0) = 2; // E的深度为2，返回给上层9.递归计算 BinaryTreeDepth(F)
// 当前节点：F，k=3（叶子节点）
int leftDep = BinaryTreeDepth(NULL); // 左子树为空 → 返回0
int rightDep = BinaryTreeDepth(NULL); // 右子树为空 → 返回0
return 1 + max(0, 0) = 1; // F的深度为1，返回给上层10.回溯到 C 节点
// C的左子树深度为2（来自E），右子树深度为1（来自F）
return 1 + max(2, 1) = 3; // C的深度为3，返回给上层11.最终回溯到根节点 A
// A的左子树深度为2（来自B），右子树深度为3（来自C）
return 1 + max(2, 3) = 4; // 整棵树的最大深度为4递归调用可视化
BinaryTreeDepth(A)-> BinaryTreeDepth(B)-> BinaryTreeDepth(D)-> BinaryTreeDepth(NULL) → 返回0-> BinaryTreeDepth(NULL) → 返回0→ 返回1 + max(0,0) = 1-> BinaryTreeDepth(NULL) → 返回0→ 返回1 + max(1,0) = 2-> BinaryTreeDepth(C)-> BinaryTreeDepth(E)-> BinaryTreeDepth(G)-> BinaryTreeDepth(NULL) → 返回0-> BinaryTreeDepth(NULL) → 返回0→ 返回1 + max(0,0) = 1-> BinaryTreeDepth(NULL) → 返回0→ 返回1 + max(1,0) = 2-> BinaryTreeDepth(F)-> BinaryTreeDepth(NULL) → 返回0-> BinaryTreeDepth(NULL) → 返回0→ 返回1 + max(0,0) = 1→ 返回1 + max(2,1) = 3
→ 返回1 + max(2,3) = 43.4.12⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}二叉树的销毁
// ⼆叉树销毁--左右根
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}层序遍历——按照从上到下、从左到右的顺序逐层访问二叉树的结点
void leverOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);//将队头非空左右孩子入队列if (top->left)QueuePush(&q, top->left);if (top->right)QueuePush(&q, top->right);}QueueDestroy(&q);
}四、堆
堆是一种特殊的完全二叉树结构，它在结构上规整、在数值上有序，常被用作优先队列的底层实现。在数据结构和算法中，堆也是实现堆排序、任务调度、哈夫曼编码等问题的关键工具。
堆具有以下几个核心性质：
1. 结构性质：
堆必须是完全二叉树，也就是说除了最后一层外，其他层必须填满，最后一层节点从左往右依次排列，不允许出现“右有左无”。
2. 堆序性质：
大根堆： 每个结点的值都大于等于其左右孩子的值；
小根堆： 每个结点的值都小于等于其左右孩子的值。
3. 存储实现：
由于堆是完全二叉树，通常用数组顺序存储，便于通过下标快速找到父子关系：
父节点下标为 i，则左孩子为 2i + 1，右孩子为 2i + 2；
孩子节点下标为 i，则父节点为 (i - 1) / 2（向下取整）。
堆的实现
头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size; //有效数据个数int capacity; //空间大小
}HP;void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPrint(HP* php);void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);// 判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
初始化&销毁&打印堆
void HPInit(HP* php)
{php->arr = NULL;php->size = php->capacity = 0;
}
void HPDestroy(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}堆的调整与排序
在使用堆解决实际问题时，一个核心操作就是维护它的有序结构。我们常通过向上调整(AdjustUp)和向下调整(AdjustDown)来完成堆的构建与维护。了解这两个过程，是掌握堆排序的基础。
一、建堆（Heapify）
建堆就是将一组无序的数据调整成一个满足堆性质的结构。常见方法有两种：
•向上调整建堆（适合插入新元素时维持堆结构）
每次将元素插入到堆的尾部，然后通过与父节点比较，不断上移直到满足堆的性质。
•向下调整建堆（适合一次性建堆）
从最后一个非叶子结点开始，依次向下调整每个结点的位置，最终构造出完整的堆。
人话：是从某个“父结点”除法，让它和它的孩子比较，把较大的（或较小的）往上提，使得这个结点变成一个合法的堆的结点。
二、堆排序
堆排序正是基于完全二叉树的结构 + 向下调整来实现的。（堆排序不需要用到向上调整建堆）
基本步骤如下：
1. 建堆阶段：从最后一个非叶子结点（因为叶子节点没有孩子，天然满足堆的性质）开始，依次向前对每个结点进行向下调整，把整个数组原地调整成一个大根堆；
2. 排序阶段：将当前堆顶元素（最大值）与堆尾元素交换，把最大值“放到正确位置”；
3. 缩小堆的有效范围，对新的堆顶元素继续进行向下调整，维持剩余部分的大根堆结构；
4. 重复步骤 2 和 3，直到堆大小变为 1，排序完成。
大顶堆实现从小到大排序，小顶堆实现从大到小排序。
堆排序的时间复杂度为 O(n log n)，空间复杂度为 O(1)，是一种不稳定的排序算法。
向上调整建堆
//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;// 计算父节点下标（完全二叉树特性）while (child > 0){//大堆：>//小堆：<// 循环直到child到达根节点（下标0）if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);// 更新指针：子节点上移到父节点位置child = parent;// 重新计算新的父节点下标parent = (child - 1) / 2;}else {// 若当前节点已满足堆性质，提前结束调整break;}}
}向下调整建堆
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//大堆：<//小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆: >//小堆：<if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}堆排序的实现：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 向上调整（用于插入新元素）
void AdjustUp(int* arr, int child)
{int parent = (child - 1) / 2; // 计算父节点下标while (child > 0){if (arr[child] > arr[parent]) // 大堆：子节点 > 父节点则交换{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break; // 已满足堆性质，提前结束}}
}// 向下调整（用于建堆和排序）
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1; // 左孩子while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]) // 大堆：选较大子节点{child++;}if (arr[child] > arr[parent]) // 大堆：子节点 > 父节点则交换{Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break; // 已满足堆性质，提前结束}}
}// 堆排序函数
void HeapSort(int* arr, int n)
{if (n <= 1) return; // 无需排序// 1. 构建大顶堆（使用向下调整法）for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(arr, i, n);}// 2. 交换堆顶与末尾元素，并调整剩余堆for (int i = n - 1; i > 0; i--){Swap(&arr[0], &arr[i]); // 将最大值交换到末尾AdjustDown(arr, 0, i); // 调整剩余堆（长度减1）}
}// 测试代码
void TestHeapSort()
{int arr[] = {5, 3, 8, 4, 6, 2, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");HeapSort(arr, n);printf("排序后: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{TestHeapSort();return 0;
}堆排序演示（从小到大排序）：
假设我们要对数组 [5, 3, 8, 4, 6, 2, 7] 进行升序排序。堆排序的核心是利用大顶堆（父节点 ≥ 子节点）的特性，每次将最大值交换到末尾。
1.构建初始大顶堆
使用向下调整法，从最后一个非叶子结点开始调整。
数组：[5, 3, 8, 4, 6, 2, 7]树结构：5(0)/ \3(1) 8(2)/ \ / \4(3) 6(4) 2(5) 7(6)调整节点 8 (2)：无需调整（子节点 2 和 7 均小于 8）。
调整节点 3 (1)：子节点 6 (4) 更大，交换 3 和 6。
交换后数组：[5, 6, 8, 4, 3, 2, 7]树结构：5(0)/ \6(1) 8(2)/ \ / \4(3) 3(4) 2(5) 7(6)调整根节点 5 (0)：子节点 8 (2) 更大，交换 5 和 8
交换后数组：[8, 6, 5, 4, 3, 2, 7]树结构：8(0)/ \6(1) 5(2)/ \ / \4(3) 3(4) 2(5) 7(6)最终大顶堆：[8, 6, 7, 4, 3, 2, 5]
调整节点5(2)：子节点7(6)更大，交换5和7。最终树结构：8(0)/ \6(1) 7(2)/ \ / \4(3) 3(4) 2(5) 5(6)步骤 2：交换堆顶与末尾元素，调整剩余堆
第一次交换（8 与 5 交换）
交换后数组：[5, 6, 7, 4, 3, 2, 8]树结构（剩余堆）：5(0)/ \6(1) 7(2)/ \ /4(3) 3(4) 2(5) [8](已排序)调整剩余堆：交换5和7，得到[7, 6, 5, 4, 3, 2, 8]第二次交换（7 与 2 交换）
交换后数组：[2, 6, 5, 4, 3, 7, 8]树结构（剩余堆）：2(0)/ \6(1) 5(2)/ \4(3) 3(4) [7, 8](已排序)调整剩余堆：交换2和6，得到[6, 3, 5, 4, 2, 7, 8]第三次交换（6 与 2 交换）
交换后数组：[2, 3, 5, 4, 6, 7, 8]树结构（剩余堆）：2(0)/ \3(1) 5(2)/4(3) [6, 7, 8](已排序)调整剩余堆：交换2和5，得到[5, 3, 2, 4, 6, 7, 8]...以此类推
其他堆的操作
堆的删除操作
void HPPop(HP* php)
{assert(!HPEmpty(php));// 0 php->size-1Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下调整AdjustDown(php->arr, 0, php->size);
}取堆顶元素
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}求size
int HPSize(HP* php)
{assert(php);return php->size;
}五、哈夫曼树（Huffman Tree）
在信息传输和压缩中，编码方式的选择直接影响传输效率和存储大小。如果我们为每个字符分配相同长度的二进制码，比如每个字母都用 8 位表示（固定长度编码），这种方式虽然简单，但有明显的缺点：
没有考虑字符出现的频率差异，比如在一篇英文文章中，e 出现的频率远远高于 z，但两者却用一样长的编码，造成空间浪费。
无法压缩数据，高频字符没能“享受”短编码，低频字符却占用了相同的存储长度。
为了解决这个问题，哈夫曼编码应运而生。它是一种 前缀编码（Prefix Code），能够根据字符出现的频率，自动生成一种更高效的编码方式：
出现频率越高的字符，编码越短
出现频率越低的字符，编码越长
生成的编码不会出现“前缀冲突”，可以被唯一解码
这种编码的核心原理就是——哈夫曼树（Huffman Tree）。接下来我们就来介绍如何通过构建一棵哈夫曼树，生成最优的哈夫曼编码。
如何构建一棵哈夫曼树
1.统计频率
对每个字符统计其出现的频率（或权值），作为构造哈夫曼树的初始结点。
例如：A:3,B:2,C:2,D:1
2. 初始化节点
将每个字符及其频率转换为独立的结点
节点列表：[A:3, B:2, C:2, D:1]3. 重复合并最小的两个节点
合并D(1)和B（2）
合并为新节点N1，权值为1+2=3
剩余结点：[A:3,C:2,N1:3]
N1:3/ \D:1 B:2合并 C (2) 和 N1 (3)
继续选择最小的两个结点合并为新结点
N2:5/ \C:2 N1:3/ \D:1 B:2合并剩余的两个结点 A (3) 和 N2 (5)为根结点Root,权值为3+5=8
完成
Root:8/ \A:3 N2:5/ \C:2 N1:3/ \D:1 B:2如何利用构造出来的哈夫曼树进行编码
编码规则：
从根结点出发，向左分支记为0，向右分支记为1
把路上经过的0和1一次拼接，得到该字符的编码
编码过程如下：
A：根 → 左 → 0
C：根 → 右 → 左 → 10
D：根 → 右 → 右 → 左 → 110
B：根 → 右 → 右 → 右 → 111
最终哈夫曼编码为：
A: 0
C: 10
D: 110
B: 111
