数据结构中的树与二叉树基础，涵盖树的概念、术语、存储结构及特殊二叉树类型。重点讲解了堆（Heap）的概念、性质及基于数组的顺序存储实现。内容包括最大堆与小根堆的区别、堆的初始化、销毁、插入数据及向上调整算法，并提供了完整的 C 语言代码示例与测试验证。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根结点没有前驱结点。除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。因此，树是递归定义的。注：树形结构中，子树之间不能有交集，否则就不是树形结构。
根据上述定义：
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既需要保存值域部分，也要保存结点和结点之间的关系，实际中树有很多种表示方式，接下来，就将对结构一一介绍：
核心思想：用数组存储每个节点，每个节点记录其双亲节点的数组下标。
#define MAX_TREE_SIZE 100
typedef struct PTNode {
int data; // 数据域
int parent; // 双亲节点的数组下标（根节点为 -1）
} PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE]; // 节点数组
int r, n; // 根节点位置、总节点数
} PTree;
核心思想：每个节点的所有孩子节点用单链表存储，再用数组记录每个节点的数据和孩子链表的头指针。
typedef struct CTNode {
int child; // 孩子节点的数组下标
struct CTNode* next; // 指向下一个孩子
} ChildPtr;
typedef struct {
int data; // 数据域
ChildPtr* firstchild; // 孩子链表头指针
} CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE]; // 节点数组
int r, n; // 根节点位置、总节点数
} CTree;
核心思想：结合前两种方法，每个节点同时记录双亲下标和孩子链表头指针，兼顾双亲与孩子的查询效率。
typedef struct CTNode {
int child; // 孩子节点的数组下标
struct CTNode* next; // 指向下一个孩子
} ChildPtr;
typedef struct {
int data; // 数据域
int parent; // 双亲节点的数组下标
ChildPtr* firstchild; // 孩子链表头指针
} CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE]; // 节点数组
int r, n; // 根节点位置、总节点数
} CTree;
| 特性 | 双亲表示法 | 孩子表示法 | 孩子双亲表示法 |
|---|---|---|---|
| 查找双亲 | O(1) | O(n) | O(1) |
| 查找孩子 | O(n) | O(k) | O(k) |
| 内存占用 | 低 | 中 | 高 |
| 结构复杂度 | 简单 | 中等 | 复杂 |
其中最常用的孩子兄弟表示法。此部分作为了解部分，在实际应用中很少使用这种复杂的树结果，像二叉树这种结构的应用相对来说更广泛。
在树形结构中，我们最常用的就是二叉树，定义为：
二叉树是由
n（n≥0）个节点组成的有限集合，满足：空集合（空二叉树）；或由一个根节点和两棵互不相交的左子树、右子树组成，左、右子树本身也是二叉树。
基本形态：
基本形态
二叉树有 5 种基本形态：空二叉树、仅含根节点、根节点 + 左子树、根节点 + 右子树、根节点 + 左子树 + 右子树。
补充说明：
- 二叉树不存在度大于 2 的结点。
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
特殊二叉树是在普通二叉树基础上，通过结构约束或功能特性形成的特定形态，本文讲解常见的特殊二叉树类型，包括满二叉树、完全二叉树。
一个二叉树如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树层次为 k，其结点总数就是 2^k-1，则它就是满二叉树。
注：判断方法：
深度为
k且节点总数为2ᵏ - 1的二叉树，每一层节点数达到最大值（第i层有2^(i-1)个节点），所有叶子节点集中在最底层。每个节点要么是叶子节点（度为 0），要么有两个子节点（度为 2），不存在度为 1 的节点。结构对称，节点数必为奇数，叶子节点仅在最底层。
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而来的。对于深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。注意满二叉树是一种特殊的完全二叉树。
完全二叉树注意：
叶子节点仅在最后两层，且最底层叶子靠左连续排列；（因为完全二叉树会注重节点的顺序）若有度为 1 的节点，最多 1 个且仅含左孩子；满二叉树是完全二叉树的特殊情况，但反之不成立。
若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2 ^(i−1) 个结点 若规定根结点的层数为 1，则深度为 h 的二叉树的最大结点数是 2 ^h − 1 若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度 h = log(n + 1) ( log 以 2 为底，n+1 为对数)
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
实现结构取决于树的数据情况，接下来，将讲解该部分知识：
顺序结构存储实际上就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。
至于为什么完全二叉树更适合使用顺序结构存储，与它的值的结构有关，顺序结构存储实际上就是使用数组来存储，为了访问到各个节点，需要将所有的节点存入数组中，但如果树中有很多的空节点，不存储任何值，我们也需要为空节点开辟空间，那样会造成空间上的浪费的。
应用：
现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
堆结构，在下面会有所讲解，所以先说到这。
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法 是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩⼦和右孩 ⼦所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。到后面讲解高阶数据结构如红黑树等会用到三叉链。所以目前专心讲解二叉树知识。
一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。
概念：
如果有一个关键码的集合 K = {k0, k1, k2, ... , kn-1} 顺序存储，在一个一维数组中，并满足：Ki <= K2i+1 且 Ki <= K2i+2，i = 0、1、2...，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆 叫做最小堆或小根堆。
简单来说：大根堆的根节点值最大，小根堆的根节点值最小。堆中某个结点的值总是不大于或不小于其父结点的值；堆总是一棵完全二叉树。性质：对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：若 i>0，i 的位置结点的双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点若 2i+1<n，左孩子序号：2i+1，2i+1>=n，则无左孩子若 2i+2<n，右孩子序号：2i+2，2i+2>=n，则无右孩子
堆底层结构为数组，因此定义堆的结构也与顺序表相同：
typedef int type;
typedef struct Heap {
type* a;
int size;
int capacity;
} HP;
操作方面，也与顺序表相同，不同点是，堆是有大根堆，小根堆的结构要求的，所以实现时也不是那么容易。
堆的初始化是创建一个空堆并设置其初始容量、指针等基本属性的过程，通常分为大顶堆（父节点值≥子节点）和小顶堆（父节点值≤子节点）两种类型。本次实现选取大堆为例。
函数：
void HPInit(HP* h);
实现代码：
void HPInit(HP* h) {
assert(h);
h->a = NULL;
h->capacity = h->size = 0;
}
讲解：
由于，堆的底层是顺序表，所以，初始化的实现与顺序表的实现基本一致。
堆的销毁函数核心目标是释放动态分配的内存，避免内存泄漏，并将堆重置为空状态，实现也与顺序表一样。
函数：
void HPDestroy(HP* h)
代码：
void HPDestroy(HP* h) {
assert(h);
if (h->a) {
free(h->a);
}
h->capacity = h->size = 0;
}
讲解：
接下来，将逐行讲解：
注意：堆的插入，是有大根堆、小根堆要求的，所以每当我们插入一个值时，都要进行堆调整。
需遵循**'先插入元素，再向上调整'**的核心逻辑。
至于：向上调整，举例：
未插入之前：
插入值：
调整之后：
在每次插入之前，我们认为是符合该（大根堆或小根堆）结构的状态，插如的值如果使树不符合该（**大根堆或小根堆）结构，则需让新插入的元素'上浮'到正确位置，恢复堆的性质。
所应用的函数：
void HPPush(HP* h, type x) //插入函数 void AdjustUp(type* a, int child) //向上调整算法 void swap(int* a, int* b); //交换值函数
代码：（由于只有入堆会引起扩容，所以扩容代码，我将其写在了插入函数内）
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void AdjustUp(type* a, int child) {
assert(a);
int parent = (child - 1) / 2;
while (child > 0) {
if (a[parent] < a[child]) {
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
void HPPush(HP* h, type x) {
assert(h);
if (h->capacity == h->size) {
int n = h->capacity == 0 ? 4 : 2 * h->capacity;
type* tmp = (type*)realloc(h->a, n*sizeof(type));
if (tmp == NULL) {
perror("realloc failed");
return;
}
h->a = tmp;
h->capacity = n;
}
h->a[h->size++] = x;
AdjustUp(h->a, h->size - 1);
}
讲解：
堆的插入操作实现，包含
swap（交换）、AdjustUp（向上调整）和HPPush（堆插入）三个函数，核心是通过'扩容→插入→调整'维持堆的性质（以大顶堆为例）。swap函数：交换两个整数的辅助函数****AdjustUp函数：向上调整****HPPush函数：堆的插入入口
堆打印值实际上与顺序表的值的打印一样，只是，结果是按照堆的值的顺序。
函数：
void HPPrint(HP* h);
代码：
void HPPrint(HP* h) {
assert(h);
int i;
for (i = 0; i < h->size; i++) {
printf("%d ", h->a[i]);
}
printf("\n");
}
讲解：
前面文章已讲过，这里不过多讲解。
接下来，我将展示我已经写完的代码部分：
本代码分三个文件完成：
1.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int type;
typedef struct Heap {
type* a;
int size;
int capacity;
} HP;
void HPInit(HP* h);
void HPDestroy(HP* h);
void HPPush(HP* h, type x);
void AdjustUp(type* a,int child);
void swap(int* a, int* b);
void HPPrint(HP* h);
1.c
#include"1.h"
void HPInit(HP* h) {
assert(h);
h->a = NULL;
h->capacity = h->size = 0;
}
void HPDestroy(HP* h) {
assert(h);
if (h->a) {
free(h->a);
}
h->capacity = h->size = 0;
}
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void AdjustUp(type* a, int child) {
assert(a);
int parent = (child - 1) / 2;
while (child > 0) {
if (a[parent] < a[child]) {
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
void HPPush(HP* h, type x) {
assert(h);
if (h->capacity == h->size) {
int n = h->capacity == 0 ? 4 : 2 * h->capacity;
type* tmp = (type*)realloc(h->a, n*sizeof(type));
if (tmp == NULL) {
perror("realloc failed");
return;
}
h->a = tmp;
h->capacity = n;
}
h->a[h->size++] = x;
AdjustUp(h->a, h->size - 1);
}
void HPPrint(HP* h) {
assert(h);
int i;
for (i = 0; i < h->size; i++) {
printf("%d ", h->a[i]);
}
printf("\n");
}
main.c
#include"1.h"
void test() {
HP h;
HPInit(&h);
HPPush(&h, 10); //10
HPPush(&h, 20); //20 10
HPPush(&h, 6); //20 10 6
HPPrint(&h);
HPPush(&h, 30); //30 20 6 10
HPPrint(&h);
HPPush(&h, 60); //60 30 6 10 20
HPPrint(&h);
HPDestroy(&h);
}
int main() {
test();
}
测试结果：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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