1 树
1.1 树的概念与结构
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。 具有以下特点：
- 具有根节点，且根节点无前驱结点。
除根结点外，其余结点被分成 M(M>0) 个互不相交的集合，每一 个集合又是 一棵结构与树类似的子树。每棵子树的根结点仅有一个前驱结点，但可以有多个互不相交的后驱结点。(若存在相交就是图了)
1.2 相关术语
- 子结点/孩子结点：一个结点的子树的根结点称子结点；如上图：B 是 A 的子结点。
- 父结点/双亲结点：含有子结点的结点称为其子结点的父结点；如上图：A 是 B 的父结点。
- 结点的度：一个结点有几个子结点，度就是多少；如 A 的度为 3，F 的度为 0。
- 树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为 3。
- 叶子结点/终端结点：度为 0 的结点称为叶结点；如上图：J、K、L…等结点为叶结点。
- 分支结点/非终端结点：度不为 0 的结点；如上图：A、B、C、D…等结点为分支结点。
- 兄弟结点：具有相同父结点的结点互称为兄弟结点 (亲兄弟)；如上图：E、F 是兄弟结点。
- 结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推。
- 树的高度或深度：树中结点的最大层次；如上图：树的高度为 4。
- 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A 是所有结点的祖先。
- 子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是 A 的子孙
- 路径：一条从树中任意节点出发，沿父节点 - 子节点连接，达到任意节点的序列；如 A 到 J 的路径为：A-B-E-J。
- 森林：由 m（m>0）棵互不相交的树的集合称为森林。
1.3 树的表示与运用场景
树的表示有很多种，最常用的便是孩子兄弟表示法，其很好地解决了结点和结点之间的关系。
struct TreeNode {
struct Node* child; // 左边开始的第一个孩子结点
struct Node* brother; // 指向其右边的下一个兄弟结点
int data; // 结点中的数据域
};
1.3.1 运用场景
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和⼦结点之间的关系来表示不同层级的文件和文件夹之间的关联。
2 二叉树
2.1 概念与结构
一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。
特点：
- 不存在大于度大于 2 的结点；
- 二叉树有左右之分，次序不能颠倒。
2.1.1 满二叉树
如果每一个层的结点数都达到最大值或满足结点总数是 2^k-1 则这个二叉树就是满二叉树。 2^k-1 的公式推导：
总的结点数：2^0 + 2^1 + 2^2+……+2^(k-1) = 1 * (1 - 2^k) / (1 - 2) = 2^k-1
2.1.2 完全二叉树
规定根结点的层数为 1:
- 一棵非空二叉树的第 i 层上最多有 2^(i−1) 个结点
- 深度为 h 的二叉树的最大结点数是 2^h − 1
- 具有 n 个结点的满二叉树的深度 h = log2(n + 1) (log 以 2 为底，n+1 为对数) -->满二叉树是特殊的完全二叉树。
3 顺序结构二叉树
顺序结构存储是使用数组来存储，在实现完全二叉树能减少空间浪费。
3.1 堆的引入
3.1.1 概念与结构
- 对于序号 i 对应的结点，若 i>0，则(i-1)/2 为父结点；若 i=0，则无父结点；
- 若 2*i+1<n，则对应其左孩子；
- 若 2*i+2<n，则对应其右孩子。
3.2 功能实现
3.2.1 堆的结构
由于堆底层是用数组实现的，因此相似于顺序表，其结构定义如下：
typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
HPDataType* arr;
int size; // 有效数据个数
int capacity; // 容量
} HP;
3.2.2 初始化、销毁
这些代码实现已经在顺序表中介绍到。
// 堆的初始化
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
// 堆的销毁
void HPDestroy(HP* php) {
assert(php);
if (php->arr) free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
3.3 堆的插入数据
熟悉了堆的概念与结构后，我们清楚堆要不就是大根堆，要不就是小根堆。问题在于插入数据后，我们如何通过代码实现化成大根堆或者小根堆的形式？由此我们提出了向上 (下) 调整算法，也会带大家分析这两种算法哪种更好。
3.3.1 向上调整算法
3.4 堆是否为空
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
3.5 删除堆顶数据
- 在删除堆顶数据时，先要判断堆是否为空，因此采用 assert。
删除堆顶数据后，如何让其再次成为大 (小) 根堆。
由此我们引入了向下调整算法。
3.5.1 向下调整算法
前提：左右⼦树必须是⼀个堆，才能调整。
3.5.2 获取堆顶数据
HPDataType HPTop(HP* php) {
assert(!HPEmpty(php));
return php->arr[0];
}
3.5.2.1 求有效数据个数
int HPSize(HP* php) {
assert(php);
return php->size;
}
3.6 向上 (下) 调整算法的复杂度比较
3.6.1 向上调整算法时间复杂度
根据大 O 表示法，则 O(n*log2n) -->详见算法复杂度篇章
3.6.2 向下调整算法时间复杂度
根据大 O 表示法可见时间复杂度为 O(n)
因此向下调整算法的时间复杂度更优。
4 代码实现
Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
HPDataType* arr;
int size; // 有效数据个数
int capacity; // 容量
} HP;
// 堆的初始化
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);
// 求 size
int HPSize(HP* php);
// 向上调整
void AdjustUp(HPDataType* arr, int child);
// 向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
// 交换
void Swap(int* x, int* y);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
// 堆的初始化
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
// 堆的销毁
void HPDestroy(HP* php) {
assert(php);
if (php->arr) free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
// 交换
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整
void AdjustUp(HPDataType* 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(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, sizeof(HPDataType) * newCapacity);
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
// realloc 成功
php->arr = tmp;
php->capacity = newCapacity;
}
php->arr[php->size] = x;
// 向上调整
AdjustUp(php->arr, php->size - 1);
php->size++;
}
// 向下调整
void AdjustDown(HPDataType* 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[parent] < arr[child]) {
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
// 删除堆顶数据
void HPPop(HP* php) {
assert(!HPEmpty(php));
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
// 向下调整
AdjustDown(php->arr, 0, php->size);
}
// 获取堆顶数据
HPDataType HPTop(HP* php) {
assert(!HPEmpty(php));
return php->arr[0];
}
// 判空
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
// 求 size
int HPSize(HP* php) {
assert(php);
return php->size;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void test() {
HP hp;
HPInit(&hp);
HPPush(&hp, 1);
HPPush(&hp, 3);
HPPush(&hp, 2);
HPPush(&hp, 4);
/*HPPop(&hp); HPPop(&hp); HPPop(&hp); HPPop(&hp);*/
while (!HPEmpty(&hp)) {
printf("%d ", HPTop(&hp));
HPPop(&hp);
}
HPDestroy(&hp);
}
void test01() {
int arr[] = { 14, 51, 31, 21, 23, 32 };
int n = sizeof(arr) / sizeof(arr[0]);
HP hp;
HPInit(&hp);
// 调用 push 将数组中的数据建堆
for (int i = 0; i < n; i++) {
HPPush(&hp, arr[i]);
}
int i = 0;
while (!HPEmpty(&hp)) {
arr[i++] = HPTop(&hp);
HPPop(&hp);
}
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
HPDestroy(&hp);
}
int main() {
// test();
// test01();
return 0;
}
