二叉树详解（1）
1. 树的概念及结构
1.1 树的相关概念
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点（没有孩子的节点）
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点（亲兄弟）
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
注：数组的下标从零开始是因为要和指针更好的匹配：a[i] = *(a + i)；而在这里我们更习惯把根定义为第一层，当然，定义成第零层也是可以的
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林（并查集）
注： 现在我们看到树就要把它进行拆分成：根和n棵子树（n>=0）；树是按照递归定义的，也就是说子树也要按照这个方式进行拆分。
也就是说树是不能有环的，有环的就称为图。
通过以上学习，我们总结一下树的概念：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点。
- 除根节点外，其余结点被分成 M(M>0) 个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
- 因此，树是递归定义的。
1.2 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系。
//树的度是N
#define N 6
struct TreeNode
{
int val;
struct TreeNode* subA[N];
};但是这样定义太浪费空间了，因为并不是每个节点的度都达到了N。
因此，我们可以借助顺序表来解决这个问题：
struct TreeNode
{
int val;
//顺序表
struct TreeNode** subA;
int size;
int capacity;
};但这种表示也不是最常见的，接下来我们介绍一种新的定义方式：
//左孩子 右兄弟
struct TreeNode
{
int val;
struct TreeNode* leftChild;
struct TreeNode* nextBrother;
};第一个指针永远指向从左往右数的第一个孩子，第二个指针指向它自己右边的亲兄弟。
那么一个父亲如何找到他所有的孩子呢？
其实还有一种表示方式，这里我们先了解一下就可以：
用数组存储数据，数组的每个元素都是一个结构体，每个结构体包含节点的值和父亲所在的下标；这种表示法可以用来表示森林。
它的物理结构：数组（内存中如何存储）
逻辑结构：森林（想象出来的）
1.3 树在实际中的运用（表示文件系统的目录树结构）
数据结构分为表示形和存储形，树这种数据结构就属于表示形，主要是用来表示某种结构。
在Windows系统中也是一样的，比如C盘作为根，里面包含了很多文件夹，每个文件夹中又包含了很多文件夹，它们的底层就是通过树这种数据结构来实现的。
2. 二叉树的概念及结构
2.1 概念
一棵二叉树是结点的一个有限集合，该集合:
- 或者为空
- 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出：
- 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注： 对于任意的二叉树都是由以下几种情况复合而成的：
二叉树单纯存储数据是没啥价值，不如顺序表/链表，那我们为什么要学二叉树呢？
但是它也存在不足，在极端情况下可能会变成这样：
因此，我们后面还要学AVL树和红黑树；同时还会有多叉树：M阶B树，多用于数据库的引擎
2.2 特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树；也就是说，如果一个二叉树的层数为K，且结点总数是 2的k次方 - 1 ，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树，要注意的是满二叉树是一种特殊的完全二叉树。
简单来说： 满二叉树就是前 n - 1 层都是满（度为2），最后一层是叶子结点；完全二叉树就是前 n - 1 层都是满，最后一层不一定满，但要求从左到右的节点是连续的。
2.3 二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
- 顺序存储 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
- 链式存储 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面我们学到高阶数据结构如红黑树等会用到三叉链。
3. 二叉树的顺序结构及实现
3.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费；而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
3.2 堆的概念及结构
3.3 堆的实现
我们先以小堆为例（大堆就是 ‘<’ 改成 ‘>’）：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;堆的插入：
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType* tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)//这样写是不对的，parent永远都是 >= 0 的
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = 0 == php->capacity ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
if (NULL == tmp)
{
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)
{
//假设法，选出左右孩子中小的那个孩子
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;
}
}
}
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);
}完整代码：
//Heap.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HPInit(HP* php);
void HPDestroy(HP* php);
//插入后保持数据是堆
void HPPush(HP* php, HPDataType x);
HPDataType HPTop(HP* php);
//删除堆顶的数据
void HPPop(HP* php);
bool HPEmpty(HP* php);//Heap.c
#include "Heap.h"
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType* tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)//这样写是不对的，parent永远都是 >= 0 的
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//时间复杂度：logN
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = 0 == php->capacity ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
if (NULL == tmp)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (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);
}
bool HPEmpty(HP* php)
{
assert(php);
return 0 == php->size;
}//Test.c
#include "Heap.h"
int main()
{
//如何把以下数组变成一个堆
//int a[] = { 50, 100, 70, 65, 60, 32 };
int a[] = { 60, 70, 65, 50, 32, 100 };
HP hp;
HPInit(&hp);
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]);
}
//printf("%d\n", HPTop(&hp));
//HPPop(&hp);
//printf("%d\n", HPTop(&hp));
while (!HPEmpty(&hp))
{
printf("%d\n", HPTop(&hp));
HPPop(&hp);
}
HPDestroy(&hp);
return 0;
}堆插入和删除的时间复杂度：
如果一开始就给了一个数组，如何给它初始化成堆呢？
- 模拟插入，向上调整建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (NULL == php->a)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->capacity = php->size = n;
//向上调整，建堆 O(N*logN)
for (int i = 1; i < php->size; i++)
{
AdjustUp(php->a, i);
}
}时间复杂度：
总结： 节点数量越多的时候，调整次数也越多
- 向下调整建堆
向下调整建堆的前提是它的左右子树都已经是大/小堆了，所有不能从第一个节点开始向下调整，而是从最后一个节点开始向下调整，但是最后一层是叶子节点，不需要调整就已经是堆了，所有就从倒数第一个非叶子节点开始向下调整。
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (NULL == php->a)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->capacity = php->size = n;
//向下调整，建堆 O(N)
for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
}时间复杂度：
总结： 节点数量多的时候，调整次数少
因此，直接给一个数组让它建堆比一个一个插入，向上调整建堆效率要高。
int main()
{
//如何把以下数组变成一个堆
//int a[] = { 50, 100, 70, 65, 60, 32 };
int a[] = { 60, 70, 65, 50, 32, 100 };
HP hp;
HPInitArray(&hp, a, sizeof(a) / sizeof(int));
while (!HPEmpty(&hp))
{
printf("%d\n", HPTop(&hp));
HPPop(&hp);
}
HPDestroy(&hp);
return 0;
}3.4 堆的应用
3.4.1 堆排序
根据我们上面所讲的，我们可以很容易想到这种写法：
void HeapSort(int* a, int n)
{
HP hp;
HPInitArray(&hp, a, n);
int i = 0;
while (!HPEmpty(&hp))
{
a[i++] = HPTop(&hp);
HPPop(&hp);
}
HPDestroy(&hp);
}
int main()
{
int a[] = { 60, 70, 65, 50, 32, 100 };
HeapSort(a, sizeof(a) / sizeof(int));
return 0;
}但是这样写有两个问题：
- 需要堆的数据结构
- 空间复杂度 O(N)
可以这样改进：
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (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;
}
}
}
//升序，建大堆还是小堆呢？大堆
//O(N * logN)
void HeapSort(int* a, int n)
{
//a数组直接建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
//O(N * logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 3, 6, 1, 5, 8, 9, 2, 7, 4, 0 };
HeapSort(a, sizeof(a) / sizeof(int));
return 0;
}之前在写堆的代码时，可能会存在这样的疑问：为什么向下调整函数的参数不传堆的结构体指针，而是只传数组的地址进去呢？
这里就体现出来了：因为这个函数在堆排序的时候还需要用到，如果传了堆的结构体指针，那这里就不好复用了。（这个函数不仅仅用来服务堆这个数据结构，还需要服务于堆排序）
3.4.2 TOP-K问题
100亿个数据，找出最大的前10个（N个数据里面找最大的前K个，N远大于K）
注： 如果N和K差不多大，可以直接排序解决
最容易想到的方法就是把这100亿个数据建一个大堆，每次找出最大的，然后将它删掉，再找次大的，一直循环10次。
但是这种方法存在问题：
- 时间复杂度：N + K * logN
- 最主要的问题是空间复杂度，堆底层就是个数组，它开不出这么大的一个数组，内存空间不够
因此，我们就要换一种方法：
void CreateNDate()
{
//造数据
int n = 100000;
srand((unsigned int)time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (NULL == fin)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
//随机数系统规定只有三万多个
//+i 是为了让数据的随机性更大一点
//%1000000 是为了让数据在1000000以内，这样我们可以手动让几个数据大于1000000，以此来验证我们程序的正确性
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void topk()
{
printf("请输入k:>");
int k = 0;
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (NULL == fout)
{
perror("fopen error");
return;
}
int* minheap = (int*)malloc(sizeof(int) * k);
if (NULL == minheap)
{
perror("malloc error");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
//建k个数据的小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minheap, k, i);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
//读取剩余数据，比堆顶的值大，就替换它进堆
if (x > minheap[0])
{
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
fclose(fout);
free(minheap);
minheap = NULL;
}
int main()
{
CreateNDate();
topk();
return 0;
}腾讯云开发者
