1. 树的基本概念
树是一种非线性的数据结构，由一个根节点和若干互不相交的子树组成。每个子树的根节点有且只有一个前驱（父节点），但可以有多个后继（子节点）。
1.1 术语定义
- 根节点：没有前驱节点的节点。
- 度：节点拥有的子树数量称为该节点的度；树中最大的度称为树的度。
- 叶子节点：度为 0 的节点，也称为终端节点。
- 分支节点：度不为 0 的节点。
- 深度/高度：从根开始定义，根为第 1 层，最大层次即为树的高度。
- 路径：从树中任意节点出发，沿父节点到子节点连接到达另一节点的序列。
- 森林：由 m（m>0）棵互不相交的树的集合。
1.2 树的表示
实际应用中，树结构通常采用孩子兄弟表示法。这种表示法将每个节点分为两个指针：一个指向第一个孩子，另一个指向下一个兄弟。这种方式可以将复杂的树结构转化为二叉树形式处理。
struct TreeNode {
struct Node* child; // 左边开始的第一个孩子结点
struct Node* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据域
};
文件系统是树形结构的典型应用场景，通过父子关系组织文件夹层级。
2. 二叉树
二叉树是特殊的树，每个节点最多有两个子树，且左右顺序不可颠倒。
2.1 特点
- 不存在度大于 2 的节点。
- 左子树和右子树是有序的。
2.2 特殊二叉树
- 满二叉树：每一层的节点数都达到最大值。若层数为 K，则节点总数为 $2^K - 1$。
- 完全二叉树：除最后一层外，其余层都是满的，且最后一层的节点都靠左排列。完全二叉树是堆的基础结构，效率较高。
2.3 存储结构
- 顺序结构：使用数组存储，适合完全二叉树。根节点索引为 0，其左右孩子分别为
2*i+1和2*i+2。 - 链式结构：每个节点包含数据域和左右指针，灵活性高但空间开销稍大。
3. 堆的实现
堆是一种特殊的完全二叉树，常用于实现优先队列或排序算法。根据根节点大小不同，分为大堆和小堆。
- 小堆：根节点最小，每个节点都比父节点大。
- 大堆：根节点最大，每个节点都比父节点小。
3.1 核心接口设计
我们使用顺序表配合数组来实现堆，需要维护当前大小、容量以及数据指针。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* arr;
int size;
int capacity;
}HP;
void HPInit(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
void HPDestory(HP* php);
bool HPEmpty(HP* php);
3.2 初始化与扩容
初始化时分配内存并设置初始容量。插入元素时需检查容量，若不足则动态扩容，通常按 2 倍增长策略。
void HPInit(HP* php) {
php->arr = NULL;
php->capacity = php->size = 0;
}
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
void HPPush(HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
php->arr[php->size] = x;
AdjustUp(php);
++php->size;
}
3.3 向上调整算法
插入新元素后，需从末尾开始向上比较，若小于父节点则交换，直到满足堆序性质。
void AdjustUp(HP* php) {
int child = php->size - 1;
int parent = (child - 1) / 2;
while (child > 0) {
if (php->arr[parent] > php->arr[child]) {
Swap(&php->arr[parent], &php->arr[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
3.4 向下调整算法
删除堆顶元素时，将最后一个元素移至堆顶，然后从根节点开始向下调整。每次选择左右孩子中较小的一个进行比较，若父节点较大则交换，直至满足堆序。
void AdjustDown(HP* php) {
int parent = 0;
int child = 2 * parent + 1;
while (child < php->size) {
if (child + 1 < php->size && php->arr[child] > php->arr[child + 1]) {
child++;
}
if (php->arr[parent] > php->arr[child]) {
Swap(&php->arr[parent], &php->arr[child]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void HPPop(HP* php) {
Swap(&php->arr[0], &php->arr[php->size - 1]);
--php->size;
AdjustDown(php);
}
void HPDestory(HP* php) {
if (php->arr) free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
在实际运行中，注意边界条件判断，特别是空堆操作和单节点情况。堆的结构保证了插入和删除的时间复杂度均为 O(logN)，非常适合处理大规模数据的优先级管理问题。