二叉树（C 语言）
目录
- 一、树
- 1. 树的概念
- 2. 树的表示方法
- 3. 树在实际当中的应用
- 二、二叉树
- 1. 二叉树的定义
- 2. 现实中的二叉树
- 3. 特殊的二叉树
- 4. 二叉树的性质
- 5. 二叉树的存储结构
- 三、堆 —— 完全二叉树的顺序存储
- 1. 堆的概念
- 2. 堆的性质
- 3. 堆的设计思路
- 4. 堆的实现代码
- 四、堆排序
- 1. 堆排序的设计思路
- 2. 堆排序的实现代码
- 五、二叉树的链式存储
- 1. 二叉树的结构声明
- 2. 二叉树的四种遍历方式
- 3. 四种遍历方式的实现
- 4. 二叉树的销毁
一、树
在现实生活中，我们对树并不陌生，因为树随处可见。而数据结构中也拥有属于它的树。
1. 树的概念
可以把数据结构中的树想象成现实生活中的树倒过来的模样：
那么就可以把根当作一个节点，然后长出它的枝干，枝干再长出它的枝干，如此往复，直到长出叶子为止。那么把枝干和叶子也当作一个节点，一颗数据结构中的树就成形了：
在上图中，节点 A 是这颗树的根，下一层就是 A 的枝干。如此往复，节点 P 和 Q 就是叶子。
下面就通过这张图，来了解数据结构中数的相关概念：
- 节点的度： 该节点含有的子树的个数，也就是孩子的个数。如：A 节点的度是 6，包含 B、C、D、E、F 和 G 六颗子树。
- 叶节点或者终端节点： 度为 0 的节点，也就是没有子树（孩子）的节点，如：节点 P 和 Q 等。
- 非终端节点或分支节点： 度不为 0 的节点，如：D、E、F 和 G。
- 双亲节点或父节点： 该节点向上延伸的第一个节点就是该节点的双亲节点。除了根节点以外，其他节点都有双亲节点，且只有一个，因为在树结构中，一个节点只能和它的双亲节点或者孩子节点相连。如：A 是 B、C、D、E、F 和 G 节点的父节点，且它们只有 A 这一个父节点。
- 孩子节点或子节点： 当前结点向下延伸的第一层节点，如：B、C、D、E、F 和 G 节点都是 A 的孩子节点。
- 兄弟节点：具有相同父亲节点的节点互为兄弟节点，如：B、C、D、E、F 和 G 节点互为兄弟节点。
- 树的度： 一颗数中，最大的节点的度称为树的度。上图中树的度为：
- 节点的层次： 上图中根节点 A 为第 1 层，B、C、D、E、F 和 G 节点是第 2 层，以此类推。
- 树的高度或深度： 树中节点的最大层次，上图中树的深度为：4
- 堂兄弟节点：双亲互为兄弟的节点称为堂兄弟节点，如：H、I、J、K、L、M 和 N 这些节点互为堂兄弟节点。
- 祖先：从根节点到该节点路径上的所有节点。如：A 是所有节点的祖先。
- 森林：由 m （m > 0）棵互不相交的树的集合称为森林。
只要记住上面加粗标记的就行了，身下的在二叉树阶段用处不大。
2. 树的表示方法
下面介绍一种简单常用的孩子兄弟表示法：
// 孩子兄弟表示法
// 类型声明
typedef int DataType;
// 树节点声明
typedef struct TreeNode
{
DataType data; // 当前节点的数据
struct TreeNode* next_brother; // 下一个兄弟节点
struct TreeNode* first_child; // 第一个孩子节点
}TreeNode;
可以把下一个兄弟节点和第一个孩子节点都想象成一个链表的开头，遇到 NULL 就结束。
这个结构的思路大概就是上图这样。（下次还是偷课件的图算了，自己画图太累了）
下面给出遍历用孩子兄弟表示法表示的二叉树的代码：
// 遍历孩子兄弟表示法的树
void PrintTree(TreeNode* root)
{
// 空树返回
if (NULL == root)
return;
// 前序遍历
// 打印当前节点
printf("%d ", root->data);
// 打印第一个孩子节点
PrintTree("d ", root->first_child);
// 打印下一个兄弟节点
PrintTree("d ", root->next_brother);
}
如果用此方法打印上图数据，那么结果如下：
A B D E G F C
3. 树在实际当中的应用
其实电脑上文件系统就是使用树来完成的：
还是偷课件的图爽！
二、二叉树
二叉树二叉树，顾名思义，每个枝干都应该有两个分支嘛。
1. 二叉树的定义
二叉树是一颗特殊的树，这棵树的度为 2。也就是说，该树的每个节点（包括根节点）最多只能有两颗子树。
从上述图片中，我们可以得出四个结论：
- 二叉树的度为 2，每个节点最多只能有两个孩子
- 二叉树的每个节点都有左子树和右子树，如：A 有左子树 B，右子树 C，那么相应的 B 和 C 也有自己的左右子树。D 的左右子树都为空树。
- 二叉树的子树有左右之分，且次序不能颠倒，所以二叉树是有序树。
- 二叉树只有一下四种状态：空树、只有左树、只有右树和左右树都有。
2. 现实中的二叉树
下面是现实中两颗经典的二叉树：
别问图片哪里来的，问就是从课件偷的。
3. 特殊的二叉树
在二叉树中又存在两种特殊的二叉树：满二叉树和完全二叉树。
-
满二叉树： 每个节点都拥有两个孩子，也可以说该树的每层都是满的。假设该树的高度为 h，那么它的节点个数为 2h-1。（等比数列，自己算一下哈）
-
完全二叉树： 除了最后一层外，其他层都是满的，而且最后一层必须是连续的。假设该树的高度为 h，那么它的节点的个数范围是 [2h-1, 2h-1]。（最少是前面 h-1 层加 1，最多是 h 层全满）
如下图所示：
4. 二叉树的性质
- 若规定根节点的层数为 1，那么该一颗非空二叉树第 n 层上最多有 2n-1 个节点。
- 若规定根节点的层数为 1，那么一颗高为 h 的树的节点范围在 [h, 2h-1]。
- 对于任意一颗二叉树而言，如果它的度为 0 的叶子节点的个数为 n0，那么度为 2 的分支节点的个数为 n2，且 n0 = n2 + 1
- 若规定根节点的层数为 1，那么具有 n 个节点的满二叉树的深度 h = log2(n+1)
- 对于具有 n 个节点的完全二叉树，如果从根节点开始从上到下从左到右开始从 0 编号，那么对于序列号为 i 的节点便有如下结论：
（1）若 i > 0，它的双亲节点的序列号为 (i-1)/2，i = 0 为根节点，根节点没有双亲节点
（2）若 2*i+1 < n，那么序列号为 i 的节点的左孩子的序列号为 2*i +1 ，同理它的右孩子就在左孩子的右边第一位。如果 2*i+1 >= n，那么当前结点为叶子节点，没有孩子。
5. 二叉树的存储结构
二叉树有两种存储方式：顺序存储和链式存储。
1. 顺序存储： 顺序存储就是开辟一个动态数组，然后把二叉树从根节点开始，从上到下从左往右放入数组中。而顺序存储一般只用来存储完全二叉树，因为存储非完全二叉树会有空间的浪费。
1.1 顺序存储的优点： 可以通过公式计算当前下标为 i 的节点的双亲节点和孩子节点的下标并且可以快速访问。
双亲节点：(i-1)/2
孩子节点：2*i+1
2.2 顺序存储的缺点： 通常用来存储完全二叉树，种类单一。且使用数组为底层实现，容量不够的时候需要增容，增容后可能会有一定的空间浪费。
2. 链式存储： 可以参考链表的实现方式，因为每个节点最多只有两个孩子节点。而且当前树由根节点和它的左子树和右子树构成，而根节点的左孩子可以当作左子树的根节点，根节点的右孩子可以当作右子树的根节点，如此往复，直到空树。
那么该数的节点就应该包含三个成员：当前结点的数据 data，左孩子的位置 left，右孩子的位置（也可以是左右树的位置）。如下代码：
// 二叉树节点声明
typedef struct BinaryTreeNode
{
DataType data; // 数据
struct BinaryTreeNode* left; // 左孩子的位置
struct BinaryTreeNode* right; // 右孩子的位置
}BTNode;
该链式存储方式被称为二叉链，如果再添加一个双亲节点的指针就是三叉链。
// 二叉树三叉链节点声明
typedef struct BinaryTreeNode
{
DataType data; // 数据
struct BinaryTreeNode* parent; // 双亲的位置
struct BinaryTreeNode* left; // 左孩子的位置
struct BinaryTreeNode* right // 右孩子的位置
};
2.1 链式存储的优点： 可以存储所有种类的二叉树，左右子树分开，层次分明。不需要扩容，且可以前序、中序、后序和层序遍历。
2.2 链式存储的缺点： 不能从当前节点找到其双亲节点，访问节点的速度没有顺序存储快。
三、堆 —— 完全二叉树的顺序存储
1. 堆的概念
这里的堆是一种二叉树，是一种数据结构，不是内存里的堆。如果一个元素的集合按照二叉树顺序存储的方式存储在一个一维数组中，并且满足所有双亲节点大于（小于）孩子节点，那么该堆被称为大堆（小堆）。将根节点最大的堆叫做最大堆或者大根堆，根节点最小的堆叫做最小堆或者小根堆。
2. 堆的性质
（1）堆中节点的值总是大于等于或者小于等于其双亲节点。
（2）堆总是一颗完全二叉树
3. 堆的设计思路
1. 堆结构设计思路：
首先，堆的底层是使用数组来实现的，那么堆的结构中应该包含指向数据的指针 pdata，其次还需要扩容，那么还需要当前数据个数 size 和当前容量 capacity，共计三个成员。
// 堆
// 类型声明
typedef int DataType;
// 常量声明
#define CAPACITY_INIT 8
// 堆结构声明
typedef struct Heap
{
DataType* pdata; // 数据
size_t size; // 当前数据个数
size_t capacity; // 当前容量
}Heap;
2. 堆方法设计思路：
下面是堆要实现的功能：
// 方法
// 构建堆
void HeapCreate(Heap* hp);
// 销毁堆
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, DataType data);
// 堆的删除
void HeapPop(Heap* hp);
// 返回堆顶的元素
DataType HeapTop(const Heap* hp);
// 返回堆中的元素个数
size_t HeapSize(const Heap* hp);
// 空堆判断
bool HeapEmpty(const Heap* hp);
上面的功能大部分都非常简单，只有插入和删除这两个操作稍微复杂一些，因为要保证在插入和删除之后，还要保持原来堆的属性，也就是大堆或者小堆。
堆的插入：
堆的插入是在堆的末尾进行插入的，假设现在有一个大堆，需要往其中插入一个元素：
可以看到，在插入元素 80 之前，该堆是一个大堆，如何保证在插入元素 80 之后仍是一个大堆？
可以通过从该节点向上调整，使得整个堆继续保持大堆。也就是该节点和它的双亲节点进行比较，如果比双亲节点大，那么就交换，交换之后再继续和它的双亲节点进行比较，直到比双亲节点小或者达到根节点就停止，调整完成之后仍是一个大堆。
堆的删除：
堆的删除是在堆顶进行删除，那么如何在删除之后保持原来的大堆呢？
首先，把堆顶的元素和堆底的元素进行交换，然后把当前元素个数 size 减 1：
此时，除了根节点以外，它的左子树和右子树均是一个大堆，那么让堆顶的数据向下调整，向下调整如果是大堆需要和孩子节点中较大的数进行比较，如果是小堆需要和孩子节点中较小的节点进行比较。
4. 堆的实现代码
（1）头文件：Heap.h
#pragma once
// 头文件
#include <stdio.h>
#include <stdbool.h>
// 堆
// 类型声明
typedef int DataType;
// 常量声明
#define CAPACITY_INIT 8
// 堆结构声明
typedef struct Heap
{
DataType* pdata; // 数据
size_t size; // 当前数据个数
size_t capacity; // 当前容量
}Heap;
// 方法
// 构建堆
void HeapInit(Heap* hp);
// 销毁堆
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, DataType data);
// 堆的删除
void HeapPop(Heap* hp);
// 返回堆顶的元素
DataType HeapTop(const Heap* hp);
// 返回堆中的元素个数
size_t HeapSize(const Heap* hp);
// 空堆判断
bool HeapEmpty(const Heap* hp);
（2）方法实现文件：Heap.c
// 头文件
#include "Heap.h"
#include <assert.h>
#include <stdlib.h>
// 方法
// 构建堆
void HeapInit(Heap* hp)
{
assert(hp);
// 申请数据空间
hp->pdata = (DataType*)malloc(sizeof(DataType)*CAPACITY_INIT);
if (NULL == hp->pdata)
{
perror("HeapCreate::malloc: ");
return;
}
// 成员初始化
hp->capacity = CAPACITY_INIT;
hp->size = 0;
}
// 销毁堆
void HeapDestory(Heap* hp)
{
assert(hp);
// 释放数据空间
free(hp->pdata);
hp->pdata = NULL;
// 成员置零
hp->size = hp->capacity = 0;
}
// 交换
void Swap(DataType* d1, DataType* d2)
{
DataType tmp = *d1;
*d1 = *d2;
*d2 = tmp;
}
// 向上调整（大堆）
void AdjustUp(DataType* arr, size_t child)
{
assert(arr);
// 找双亲节点下标
size_t parent = (child - 1) / 2;
// 开始调整
while (child > 0) // child 为 0 时是根节点，没有双亲节点
{
if (arr[child] > arr[parent])
{
// 交换
Swap(&arr[child], &arr[parent]);
// 下一组
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(Heap* hp, DataType data)
{
assert(hp);
// 增容判断
if (hp->size == hp->capacity)
{
DataType* tmp = (DataType*)realloc(hp->pdata, sizeof(DataType) * hp->capacity * 2);
if (NULL == tmp)
{
perror("HeapPush::realloc: ");
return;
}
// 成功，更新成员
hp->pdata = tmp;
hp->capacity *= 2;
}
// 插入
hp->pdata[hp->size++] = data;
// 向上调整
AdjustUp(hp->pdata, hp->size - 1);
}
// 向下调整
void AdjustDown(DataType* arr, size_t n, size_t parent)
{
assert(arr);
// 找左孩子节点下标
size_t 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 = child * 2 + 1;
}
else
{
break;
}
}
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
// 空堆判断
if (0 == hp->size)
{
printf("Emtpty Heap! Cant't Pop!\n");
return;
}
// 交换堆顶和堆底
Swap(&hp->pdata[0], &hp->pdata[hp->size - 1]);
// 元素个数 -1
--hp->size;
// 堆顶向下调整
AdjustDown(hp->pdata, hp->size, 0);
}
// 返回堆顶的元素
DataType HeapTop(const Heap* hp)
{
assert(hp);
// 空堆判断
if (0 == hp->size)
{
printf("Empty Heap!\n");
exit(-1);
}
// 返回
return hp->pdata[0];
}
// 返回堆中的元素个数
size_t HeapSize(const Heap* hp)
{
assert(hp);
// 返回
return hp->size;
}
// 空堆判断
bool HeapEmpty(const Heap* hp)
{
assert(hp);
// 返回
return (0 == hp->size);
}
（3）测试文件：test.c
// 头文件
#include "Heap.h"
#include <stdlib.h>
#include <time.h>
int main()
{
// 设置随机数种子
srand((unsigned)time(0));
// 创建堆
Heap hp;
// 初始化堆
HeapInit(&hp);
// 堆的插入
// 随机生成值为 11 - 99 的 10 个数
int i;
for (i = 0; i < 10; ++i)
{
int tmp = rand() % 89 + 11;
printf("%d ", tmp);
HeapPush(&hp, tmp);
}
printf("\n");
// 堆的删除
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
// 销毁堆
HeapDestory(&hp);
return 0;
}
（4）测试结果：
通过观察可以发现，如果是大堆，每次删除的都是当前堆中最大的数，如果是小堆每次删除的都是当前堆中最小的数。所以，把删除的数据打印出来，如果有序，则证明代码基本上没有问题。
四、堆排序
从上面的堆实现的测试结果中发现，堆好像可以给数据进行排序。因为如果是大堆的话，每次删除都会把最大的数据放在最后面；如果是小堆的话，每次删除都会把最小的数据放在最后面。
所以，排升序需要使用大堆，排降序需要使用小堆。
1. 堆排序的设计思路
首先，排序是传给你一个数组，然后使用对应的方法进行排序是数组中的数据变得有序。那么数组中的原数据是随机的，如果要进行堆的删除，首先要确保原数组是一个堆，那么第一步就是建堆。
（1）建堆
建堆有两种方法，一种是向上调整建堆，另一种是向下调整建堆。
向上调整建堆： 把数组的第一个元素看成一个堆，然后把第二个元素向上调整，接着把前面两个元素看成一个堆，把第三个元素向上调整，直到调整完数组的最后一个元素。调整完成后，该数组就是一个大（小）堆。
向下调整： 从数组的第一个非叶子节点开始向下调整，因为第一个非叶子节点的左右子树要么只有一个节点，要么就是空树，所以它的左右子树都是大（小）堆，而根节点向下调整之后该根节点表示的这颗树就是大（小）堆了。然后继续调整前一个节点，直到调整完所有节点。调整完成之后，该数组就是一个大（小）堆。
（2）开始堆的删除，直到删除完数组的第二个元素位置
假设数组元素个数为 n，那么大的 n-1 个数已经有序排在后面了，当前数组首元素就是最小的数了。
由于向下调整建堆的速度比向上调整建堆块，所以一般使用向下调整建堆。
2. 堆排序的实现代码
（1）头文件：HeapSort.h
#pragma once
// 函数声明
// 堆排序
void HeapSort(int* arr, int sz);
// 打印数组
void PrintArr(int* arr, int sz);
// 交换
void Swap(int* a, int* b);
（2）方法实现文件：HeapSort.c
// 头文件
#include "HeapSort.h"
#include <stdio.h>
// 函数定义
// 向下调整
void AdjustDown(int* arr, size_t sz, size_t parent)
{
// 找到左孩子的下标
size_t child = parent * 2 + 1;
// 开始调整
while (child < sz)
{
// 找到大孩子
if ((child + 1) < sz && arr[child] < arr[child + 1])
++child;
// 比较
if (arr[child] > arr[parent])
{
// 交换
Swap(&arr[child], &arr[parent]);
// 下一组
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
// 堆排序
void HeapSort(int* arr, int sz)
{
// 向下调整建堆
int i = 0;
for (i = (sz - 2) / 2; i >= 0; --i)
{
// 向下调整
AdjustDown(arr, sz, i);
}
// 堆的删除，直到只剩最后一个元素
int n = sz - 1;
while (n--)
{
// 交换堆顶和堆底
Swap(&arr[0], &arr[n + 1]);
// 堆顶向下调整
AdjustDown(arr, n + 1, 0);
}
}
// 打印数组
void PrintArr(int* arr, int sz)
{
int i = 0;
for (i = 0; i < sz; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// 交换
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
（3）测试文件：test.c
// 头文件
#include "HeapSort.h"
#include <stdlib.h>
#include <time.h>
// 堆排序测试
int main()
{
// 设置随机数种子
srand((unsigned)time(0));
// 随机生成 20 个 1 - 99 之间的数字
int arr[20];
size_t sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
for (i = 0; i < 20; ++i)
arr[i] = rand() % 99 + 1;
// 堆排序
HeapSort(arr, sz);
// 打印验证
PrintArr(arr, sz);
return 0;
}
（4）测试结果：
五、二叉树的链式存储
1. 二叉树的结构声明
// 二叉树
// 类型声明
typedef int DataType;
// 二叉树结构声明
typedef struct TreeNode
{
DataType data; // 数据
struct TreeNode* left; // 左子树
struct TreeNode* right; // 右子树
}TreeNode;
（1）若根节点为空，则为空树
（2）根节点不为空，那么该二叉树就分为根节点，左子树和右子树。左子树和右子树可以继续按照该方法往下分。
总结得出：二叉树的定义方式和递归很相似。递归的本质是将一个复杂的大问题逐步分解为规模更小、与原问题相似的子问题来求解，直到子问题简单到可以直接得出答案。而二叉树把原树分为根节点左子树和右子树，其子树继续往下分，直到空树为止。
所以，对二叉树的操作应该都和递归有关。
2. 二叉树的四种遍历方式
二叉树有前序、中序、后序和层序四种遍历方式。其中，前序、中序和后序遍历的差别是访问根节点的顺序不同，而层序遍历是从根节点开始从上到下，从左往右依次遍历每个节点。
前序遍历： 先访问根节点，然后访问左子树，最后访问右子树
中序遍历： 先访问左子树，然后访问根节点，最后访问右子树
后序遍历： 先访问左子树，然后访问右子树，最后访问根节点
下面对前序遍历给出递归顺序图，中序和后序读者根据前序依葫芦画瓢。
3. 四种遍历方式的实现
1. 前序遍历
// 前序遍历
void PreOrder(const TreeNode* root)
{
// 空树
if (NULL == root)
return;
// 打印根节点
printf("%d", root->data);
// 左子树
PreOrder(root->left);
// 右子树
PreOrder(root->right);
}
递归过程图：
（1）自己画的
（2）课件偷的
2. 中序遍历：
// 中序遍历
void InOrder(const TreeNode* root)
{
// 空树
if (NULL == root)
return;
// 左子树
InOrder(root->left);
// 打印根节点
printf("%d ", root->data);
// 右子树
InOrder(root->right);
}
3. 后序遍历
// 后序遍历
void PostOrder(const TreeNode* root)
{
// 空树
if (NULL == root)
return;
// 左子树
PostOrder(root->left);
// 右子树
PostOrder(root->right);
// 打印根节点
printf("%d ", root->data);
}
4. 层序遍历
层序遍历需要借助队列实现，先把根节点放进去，然后每次出一个节点就把它的孩子入队，直到队列为空，这样就能实现层序遍历。
出入过程图：
代码如下：
// 层序遍历
void LevelOrder(const TreeNode* root)
{
assert(root);
// 创建队列
Queue q;
// 初始化队列
QueueInit(&q);
// 根节点入队
QueuePush(&q, root);
// 开始层序遍历
while (!QueueEmpty(&q))
{
// 出队
TreeNode* cur = QueueFront(&q);
QueuePop(&q);
// 打印
printf("%d ", cur->data);
// 入其孩子节点
if (cur->left)
QueuePush(&q, cur->left);
if (cur->right)
QueuePush(&q, cur->right);
}
}
4. 二叉树的销毁
二叉树的销毁只能选择后序遍历的方式，因为根节点要留在最后删除。
// 销毁二叉树
void TreeDestory(TreeNode* root)
{
// 空树
if (NULL == root)
return;
// 释放左子树
TreeDestory(root->left);
// 释放右子树
TreeDestory(root->right);
// 释放根节点
free(root);
}