树是一种非线性数据结构，由有限结点组成层次关系集合。二叉树作为特殊树形结构，具有左右子树之分，包含满二叉树和完全二叉树等类型。文章详细阐述了二叉树的五大性质及其推导过程，重点讲解了堆这种顺序存储结构的特性。通过 C 语言代码展示了堆的初始化、销毁、插入、删除及上下调整算法的具体实现，为理解优先队列等高级数据结构奠定基础。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1<= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，因此，树是递归定义的。
有一点需要注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
孩子兄弟表达法：
typedef int type;
struct Node {
struct Node* firstChild; // 第一个孩子节点
struct Node* NextBrother; // 指向其下一个兄弟节点
type data; // 数据
};
假设二叉树有 N 个结点： 从总结点数角度考虑：N = n0 + n1 + n2 ①//n1 为度为 1 的节点 从边的角度考虑，N 个结点的任意二叉树，总共有 N-1 条边 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边 因此 N 个结点的二叉树总共有 N-1 条边 因为度为 0 的结点没有孩子，故度为 0 的结点不产生边; 度为 1 的结点只有一个孩子，故每个度为 1 的结点产生一条边; 度为 2 的结点有 2 个孩子，故每个度为 2 的结点产生两条边，所以总边数为：n1+2n2 故从边的角度考虑：N-1 = n1 + 2n2 ② 结合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1 即：n0 = n2 + 1
- 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199
根据性质 3 可以得出 n0=n2+1,答案为：B
- 下列数据结构中，不适合采用顺序存储结构的是（ ） A 非完全二叉树 B 堆 C 队列 D 栈
堆的底层是数组，栈底层是数组，队列也可以用数组来实现，而非完全二叉树不适用，满二叉树和完全二叉树可以按顺序储存，答案为：A
- 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2
可以根据公式进行推导，假设 n0 是度为 0 的结点总数（即叶子结点数），n1 是度为 1 的结点总数，n2 是度为 2 的结点总数，则： ① n= n0+n1+n2（其中 n 为完全二叉树的结点总数）；又因为一个度为 2 的结点会有 2 个子结点，一个度为 1 的结点会有 1 个子结点，除根结点外其他结点都有父结点， ② n= 1+n1+2n2；由①、②两式把 n2 消去得：n= 2n0+n1-1，由于完全二叉树中度为 1 的结点数只有两种可能 0 或 1，由此得到 n0=n/2 或 n0=(n+1)/2。 简便来算，就是 n0=n/2，其中 n 为奇数时（n1=0）向上取整；n 为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。所以答案为：A
- 一棵完全二叉树的结点数位为 531 个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12
根据性质 4 得出：答案为 B
- 一个具有 767 个结点的完全二叉树，其叶子结点个数为（） A 383 B 384 C 385 D 386
简便来算，就是 n0=n/2，其中 n 为奇数时（n1=0）向上取整；n 为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。所以答案为：B
顺序存储 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
堆的性质：
堆中某个结点的值总是不大于或不小于其父结点的值； 堆总是一棵完全二叉树。
- 下列关键字序列为堆的是：（） A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32
答案为：A
- 已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。 A 1 B 2 C 3 D 4
8 与 12 交换位置后，12 与 15 比较，在与 10 比较，交换 10 与 12，最后 12 在与 16 比较 一共比较了 3 次 答案为 C
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。
int a[] = {1, 5, 3, 8, 7, 6};
先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。
删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
typedef int HPDataType;
struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);
// 堆接口实现
void HPInit(HP* php) {
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HPDestroy(HP* php) {
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2) {
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child) {
// 初始条件
// 中间过程
// 结束条件
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
void HPPush(HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL) {
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int n, int parent) {
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n 说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] > a[child]) {
++child;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
// logN
void HPPop(HP* php) {
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
HPDataType HPTop(HP* php) {
assert(php);
assert(php->size > 0);
return php->a[0];
}
bool HPEmpty(HP* php) {
assert(php);
return php->size == 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