引言
在计算机科学中，二叉树是一种重要的数据结构，广泛应用于各种算法和程序设计中。本文将探讨二叉树的顺序实现，特别是堆的实现方式。
C算法
二叉树的顺序实现与堆结构详解
二叉树的基础概念、术语及存储结构，重点讲解了基于数组的顺序实现方式——堆。内容涵盖最小堆与最大堆的定义，堆的向上调整与向下调整算法原理，以及插入、删除、判空等核心操作的 C 语言实现。通过完整代码示例展示了如何构建小堆并测试基本功能，帮助读者理解堆在优先队列等场景中的应用。
二叉树的基础概念、术语及存储结构，重点讲解了基于数组的顺序实现方式——堆。内容涵盖最小堆与最大堆的定义，堆的向上调整与向下调整算法原理，以及插入、删除、判空等核心操作的 C 语言实现。通过完整代码示例展示了如何构建小堆并测试基本功能，帮助读者理解堆在优先队列等场景中的应用。
在计算机科学中，二叉树是一种重要的数据结构，广泛应用于各种算法和程序设计中。本文将探讨二叉树的顺序实现，特别是堆的实现方式。
树是一种非线性的数据结构，它是由 n(n>=0) 个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 有一个特殊的结点，称为根结点，根结点没有前驱结点。 • 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。因此，树是递归定义的。
树形结构中，子树之间不能有交集，否则就不是树形结构。
非树形结构：
总结： • 子树是不相交的（如果存在相交就是图了） • 除了根结点外，每个结点有且仅有一个父结点 • 一棵 N 个结点的树有 N-1 条边
孩子兄弟表示法：树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法
struct TreeNode {
struct Node* child; // 最左边的孩子结点
struct Node* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据域
};
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。
二叉树（binary tree）是一种非线性数据结构，代表'祖先'与'后代'之间的派生关系，体现了'一分为二'的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。
总结：
- 二叉树不存在度大于 2 的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的
节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。
完美二叉树 (perfect binary tree) 所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0，其余所有节点的度都为 2；若树的高度为 h，则节点总数为 2^(h+1) - 1，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
完全二叉树 (complete binary tree) 只有最底层的节点未被填满，且最底层节点尽量靠左填充。
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。（红黑树等会用到三叉链。）
一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。
堆是一种完全二叉树，具有以下性质：
最小堆：每个节点的值都小于或等于其子节点的值。
最大堆：每个节点的值都大于或等于其子节点的值。
堆常用于实现优先队列，因为它能有效地支持插入和删除操作。
总结 • 堆中某个结点的值总是不大于或不小于其父结点的值； • 堆总是一棵完全二叉树。
我们以小堆为例进行实现：
二叉树的顺序存储通常使用数组来实现。对于一个节点在数组中的索引
i，可以通过以下方式找到其父节点和子节点的索引： 父节点：(i - 1) / 2（取整） 左子节点：2 * i + 1右子节点：2 * i + 2
typedef struct Heap {
DataType *arr;
int size;
int capacity;
} HP;
这里可以看到堆的底层结构和动态顺序表一样。
// 初始化
void HPInit(HP* p) {
assert(p);
p->arr = NULL;
p->size = p->capacity = 0;
}
// 销毁
void HPDestroy(HP* p) {
assert(p);
if (p->arr) {
free(p->arr);
}
p->arr = NULL;
p->size = p->capacity = 0;
}
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
💡 向上调整算法 • 先将元素插入到堆的末尾，即最后一个孩子之后 • 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双亲往上调整到合适位置即可
// 堆的向上调整
void AdjustUp(DataType* arr, int child) {
int parent = (child - 1) / 2; // 父节点
while (child > 0) { // 注意 child 可能会被调整到根节点，这时候就不能再调整了
if (arr[child] < arr[parent]) { // 如果条件语句不成立，就说明堆已经成型
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2; // 循环以上步骤
} else {
break;
}
}
}
将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。
// 插入
void HPPush(HP* p, DataType x) {
assert(p);
if (p->size == p->capacity) { // 判断空间是否足够
// 扩容
int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
p->arr = tmp;
p->capacity = NewCap;
}
p->arr[p->size] = x;
AdjustUp(p->arr, p->size);
++p->size;
}
💡 向下调整算法 • 将堆顶元素与堆中最后一个元素进行交换 • 删除堆中最后一个元素 • 将堆顶元素向下调整到满足堆特性为止 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
// 堆的向下调整
void AdjustDown(DataType* 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 HPPop(HP* p) {
assert(p && p->size);
Swap(&p->arr[0], &p->arr[p->size - 1]);
--p->size;
AdjustDown(p->arr, 0, p->size);
}
// 判空
bool HPEmpty(HP* p) {
assert(p);
return p->size == 0;
}
// 返回堆顶元素
DataType HPTop(HP* p) {
assert(p && p->size);
return p->arr[0];
}
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
// 定义堆的结构--数组
typedef int DataType;
typedef struct Heap {// 小堆为例
DataType *arr;
int size;
int capacity;
} HP;
// 初始化
void HPInit(HP* p);
// 销毁
void HPDestroy(HP* p);
// 插入
void HPPush(HP* p, DataType x);
// 删除，出堆顶数据
void HPPop(HP* p);
// 判空
bool HPEmpty(HP* p);
// 返回堆顶元素
DataType HPTop(HP* p);
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
// 初始化
void HPInit(HP* p) {
assert(p);
p->arr = NULL;
p->size = p->capacity = 0;
}
// 销毁
void HPDestroy(HP* p) {
assert(p);
if (p->arr) {
free(p->arr);
}
p->arr = NULL;
p->size = p->capacity = 0;
}
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 堆的向上调整
void AdjustUp(DataType* arr, int child) {
int parent = (child - 1) / 2; // 父节点
while (child > 0) { // 注意 child 可能会被调整到根节点，这时候就不能再调整了
if (arr[child] < arr[parent]) { // 如果条件语句不成立，就说明堆已经成型
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2; // 循环以上步骤
} else {
break;
}
}
}
// 插入
void HPPush(HP* p, DataType x) {
assert(p);
if (p->size == p->capacity) { // 判断空间是否足够
// 扩容
int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
p->arr = tmp;
p->capacity = NewCap;
}
p->arr[p->size] = x;
AdjustUp(p->arr, p->size);
++p->size;
}
// 堆的向下调整
void AdjustDown(DataType* 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 HPPop(HP* p) {
assert(p && p->size);
Swap(&p->arr[0], &p->arr[p->size - 1]);
--p->size;
AdjustDown(p->arr, 0, p->size);
}
// 判空
bool HPEmpty(HP* p) {
assert(p);
return p->size == 0;
}
// 返回堆顶元素
DataType HPTop(HP* p) {
assert(p && p->size);
return p->arr[0];
}
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void test01() {
HP hp;
HPInit(&hp);
int arr[] = { 17, 20, 10, 13, 19, 15 };
for (int i = 0; i < 6; i++) {
HPPush(&hp, arr[i]);
}
// HPPop(&hp);
while (!HPEmpty(&hp)) {
printf("%d-", HPTop(&hp));
HPPop(&hp);
}
HPDestroy(&hp);
}
int main() {
test01();
return 0;
}
通过顺序实现的方式，我们可以高效地存储和操作二叉树。堆作为一种特殊的二叉树，提供了快速的插入和删除操作，非常适合优先队列的实现。在许多应用场景中，如任务调度、图算法等，堆结构都发挥着重要作用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online