本文阐述了树与二叉树的数据结构定义，涵盖父节点、子节点、度、深度等核心概念。详细介绍了满二叉树与完全二叉树的特性及其存储方式（顺序与链式）。重点讲解了堆（最大堆与最小堆）的构建、插入、删除及上下调整算法，并通过 TOP-K 问题演示了堆在大数据量筛选中的应用。此外，文章实现了二叉树的四种遍历方式（前序、中序、后序、层序），以及计算结点总数、叶子数、高度、查找指定值及销毁树等递归操作。所有示例代码均基于 C 语言编写，修正了部分逻辑错误以增强实用性。
树是一种非线性的数据结构，它是由 n 个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树。
例如：
用孩子兄弟表示法：
struct TreeNode {
struct TreeNode* child; // 左边开始的第一个孩子的结点
struct TreeNode* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据域
};
通过上述的结构我们可以比较清晰地了解该方法。
⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。
二叉树是树形结构的一种。
一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
例如：
二叉树的特点：
每一层的结点都达到最大值，则这个二叉树就是满二叉树。结点的总数就是 2^k - 1
完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
则该结构的特点是：假设二叉树的层次为 K 层，则除了第 K 层外，每层结点的个数达到最大结点数，第 K 层不一定达到最大结点数。
且完全二叉树结点的顺序是从左到右顺序放置的。
二叉树一般可以使用两种结构存储：一种是顺序结构，一种是链式结构。
顺序结构是使用数组来进行存储的，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树使用顺序结构进行存储。
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。后⾯课程学到⾼阶数据结构如红⿊树等会⽤到三叉链。
堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。
分为小跟堆和大根堆，我们通过图片来进行了解：
堆具有以下的性质：
二叉树的性质：
对于具有 n 个结点的完全二叉树，如果按照从上至下、从左至右的数组顺序对所有结点从 0 开始编号（例如上述的图片），则对于序号为 i 的结点有：
与前几次实现基本相同，这里省略分析过程。最终的代码会汇合在一起。
由于插入的数据是随机的，我们不确定插入数据的大小，而大堆和小堆之间的数据的顺序是有一定规律的，因此，我们要通过适当的方法来进行插入。用堆的向上调整方法。
这里对于堆的向上调整算法不再做过多的介绍，直接上代码：
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 HPPush(int* arr, int* size, int capacity, int x) {
// 判断空间是否足够
if (*size == capacity) {
int newCapacity = capacity == 0 ? 4 : 2 * capacity;
int* tmp = realloc(arr, newCapacity * sizeof(int));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
arr = tmp;
capacity = newCapacity;
}
arr[*size] = x;
AdjustUp(arr, *size);
++(*size);
}
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
与之前不同的是，在堆的删除中，我们删除的是堆顶的数据。
代码如下：
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 HPPop(int* arr, int* size) {
assert(arr && *size);
Swap(&arr[0], &arr[*size - 1]);
--(*size);
AdjustDown(arr, 0, *size);
}
TOP-K 问题：即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。
当数据量太大的时候，就不能用排序的方法，这时，我们可以用堆来解决问题。
思路：拿 K 个数据来建堆，然后让取到的数据分别与原始的 K 个数据进行比较，最后所得即为所求。时间复杂度为 O(N)，空间复杂度为 O(K)。根据上述的分析可得，找最小的 K 个数据，建大堆，找最大的 K 个数据，建小堆。
代码实现如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
// 假设 AdjustDown 已定义
void AdjustDown(int* arr, int parent, int n);
void CreateNDate() {
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL) {
perror("fopen error");
return;
}
for (int i = 0; i < n; i++) {
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void TOPK() {
int k = 0;
printf("请输入 K:");
scanf("%d", &k);
// 从文件中读取前 K 个数据
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL) {
perror("fopen fail!");
exit(1);
}
int* minHeap = (int*)malloc(k * sizeof(int));
if (minHeap == NULL) {
perror("malloc fail!");
exit(0);
}
for (int i = 0; i < k; i++) {
fscanf(fout, "%d", &minHeap[i]);
}
// 建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(minHeap, i, k);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF) {
if (x > minHeap[0]) {
minHeap[0] = x;
AdjustDown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main() {
// test01();
// CreateNDate();
TOPK();
return 0;
}
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
一般来说，我们用的是二叉链表的结构来实现的。
代码实现如下：
void PreOrder(BTNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
其本质是应用递归的方法。
代码如下：
void InOrder(BTNode* root) {
if (root == NULL) {
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
代码如下：
void PostOrder(BTNode* root) {
if (root == NULL) {
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
实现下列问题：
// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第 k 层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为 x 的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestroy(BTNode** root);
代码实现如下：
// 二叉树结点个数
int BinaryTreeSize(BTNode* root) {
if (root == NULL) {
return 0;
}
return (1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right));
}
// 二叉树叶子结点个数，即没有孩子结点的个数
int BinaryTreeLeafSize(BTNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第 k 层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {
// 思路：左子树第 K 层结点的个数 + 右子树第 K 层结点的个数
if (root == NULL) {
return 0;
}
if (k == 1) {
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树的深度/高度（即层数）
int BinaryTreeDepth(BTNode* root) {
// 1 + 左 + 右
if (root == NULL) {
return 0;
}
int leftdep = BinaryTreeDepth(root->left);
int rightdep = BinaryTreeDepth(root->right);
return leftdep > rightdep ? leftdep + 1 : rightdep + 1;
}
// 二叉树查找值为 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 BinaryTreeDestroy(BTNode** root) {
// 先左后右，最后根结点
if (*root == NULL) return;
BinaryTreeDestroy(&((*root)->left));
BinaryTreeDestroy(&((*root)->right));
free(*root);
*root = NULL;
}
设二叉树的根结点所在层数为 1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过就是层序遍历。
我们借助队列来解决。（先进先出）
代码实现如下：
// 层序遍历
void LevelOrder(BTNode* root) {
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* top = QueueFront(&q);
printf("%d ", top->data);
// 出队
QueuePop(&q);
if (top->left) {
QueuePush(&q, top->left);
}
if (top->right) {
QueuePush(&q, top->right);
}
}
QueueDestroy(&q);
}
涉及到层，所以我们还采用队列的方法来进行运算。
代码实现如下：
bool BinaryTreeComplete(BTNode* root) {
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL) break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL) {
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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