二叉树的概念
一棵二叉树是节点的一个有限集合，该集合或者为空或者由根节点加上两棵别称为左子树和柚子树的二叉树组成。
从图中可以看出：
1、二叉树不存在度大于2的节点。
2、二叉树的子树有左右之分，次序不可颠倒，因此二叉树为有序树。
注意：对于任意的二叉树都是由以下几种情况复合而成的，这种符合类似于函数的嵌套：
特殊二叉树
1、满二叉树：一个二叉树如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且节点总数为2^k-1，则它就是满二叉树。
2、完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为k，且有n个节点的二叉树，当且仅当每个节点都与深度为k的满二叉树中编号从1至n的节点 一 一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质
1、若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
2、若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h - 1.
3、对任意一棵二叉树来说，如果度为0其叶节点个数为No，度为1的节点个数为N1，度为2的分支节点个数为N2，则有No = N2 + 1。
* 假设二叉树有N个结点
* 从总结点数角度考虑：N = No + N1 + N2 ①
* 从边的角度考虑，N个结点的任意二叉树，总共有N-1条边。
* 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边， 因此N个结点的二叉树总共有N-1条边。
* 因为度为0的结点没有孩子，故度为0的结点不产生边; 度为1的结点只有一个孩子，故每个度为1的结点产生一条边; 度为2的结点有2个孩子，故每个度为2的结点产生两条边，所以总边数为：N1+2*N2。
* 故从边的角度考虑：N-1 = N1 + 2*N2 ②
* 结合① 和 ②得：No + N1 + N2 = N1 + 2*N2 - 1。
* 即：N0 = N2 + 1。
4、若规定根节点的层数为1，具有n个节点的满二叉树的深度，h = log以2为底n+1的对数。
5、对于具有n个节点的完全二叉树，如果按照从上到下，从左到右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：
1. 若i>0，i位置结点的双亲序号则为：(i-1)/2；若i=0，i为根结点编号，无双亲结点。
2. 若2i+1<n，左孩子序号：2i+1，若2i+1>=n否则无左孩子。
3. 若2i+2<n，右孩子序号：2i+2，若2i+2>=n否则无右孩子。
二叉树的存储结构
二叉树的存储一般分为顺序和链式两种存储结构。
二叉树的顺序存储结构
顺序结构存储就是使用数组来存储二叉树的节点，一般使用数组结构的是完全二叉树，因为不是完全二叉树会有空间上的浪费。而现实中使用只有堆这一结构才会使用数组来存储，关于堆我们下面会进行专门讲解，二叉树顺序存储在物理结构上是一个数组，在逻辑结构上是一棵二叉树。
二叉树的链式存储结构
二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链表来指示元素之间的逻辑关系。通常的方法是链表中每个节点由三个域组成：数据域和左右指针域，左右指针分别用来存放该节点的左孩子和右孩子所在的链表节点的存储地址。链式结构又分为二叉链和三叉链，当前我们在学习中一般都是用二叉链，后续在高阶的数据结构如红黑树等会用到三叉链，所以我们后面再讲。
其结构代码演示如下：
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}；在对二叉树有了基本的了解之后，我们就来深入了解一下二叉树的顺序存储结构。 链式二叉树我们下章讲。
二叉树的顺序结构及实现
结构
普通的二叉树是不适合使用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序存储结构。现实中我们通常把堆(一种二叉树)使用顺序结构来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间懂得堆区不同，这里的堆是一种数据结构，而堆区是操作系统中管理内存的一块区域分段。
堆
如果有一个关键码的集合K = { k0，k1，k2，……，kn-1 }，把它的所以元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足:Ki <= K(2*i+2) 且 Ki <= K(2*i+2)，则称为小堆(反之称为大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：1、堆中某个节点的值总是不大于或不小于其双亲节点的值；
2、堆总是一棵完全二叉树。
堆的实现
我们将堆的实现分为两部分：第一部分包括代码中需要的库函数包含的头文件，小堆的结构体的结构和函数的声明。第二部分就是各种函数的具体实现，这里会详细讲解。
堆的向下调整算法：
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
堆的向上调整算法与向下调整有相似之处，我们会在代码中讲解。
heap.h:
//以小堆为例
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
// 堆的初始化
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);heap.c:
// 堆的初始化
//初始化就是将结构体中的变量进行初步赋值，保证后续操作的正常进行
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
// 堆的销毁
//销毁操作也是必不可少的，若空间不释放则会导致内存泄漏
void HeapDestory(Heap* php)
{
assert(php);
//释放空间
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整建小堆
//双亲节点的位置是（孩子节点-1）/2
//因为是向上调整节点，我们需要找到循环的结束条件，这里举了一个错误的例子：parent >= 0
//通过计算我们会发现child = 0时，parent = -1/2 = 0，也就是说循环不会结束，但是当再次进入循环
//后我们会发现循环会通过break巧妙结束，这也算是误打误撞了。
//正确的方法是child > 0，进入循环后判断child节点的值是否较小，如果较小就交换，否则跳出循环
void AdjustUp(HPDataType* a,int child)
{
assert(a);
int parent = (child - 1) / 2;
//while(parent >= 0) 存在逻辑漏洞，但是能顺利运行
while (child > 0)
{
//起始条件->中间过程->结束条件
if (a[child] < a[parent])
{
//交换
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{//如果孩子节点大于双亲节点，就跳出循环
break;
}
}
}
// 堆的插入函数
//在函数中我们先断言检查指针有效性，然后因为是数组，所以需要判断是否需要扩容的问题
//再push结束后我们还要进行向上调整操作，因为我们建的是小堆，所以如果我们插入的叶子结点小于该节点
//的双亲节点，我们就需要为他们交换位置。
//调整函数的参数为需要调整的数组和孩子节点的下标，这里并没有必要传入结构体，后面会讲。
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
//判断是否需要扩容
if (php->capacity == php->size)
{
int newcapacity = (php->capacity == 0) ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
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);
}
//向下调整建小堆
//向下调整的思路与向上调整有所差异，参数分别为数组，数组的长度以及双亲节点的位置
//孩子节点的位置：child = parent*2 + 1
//因为是向下调整，所以循环的结束是child < size
//进入循环后，我们要判断双亲是否大于孩子节点，但是我们还没有确定到底哪个孩子节点更小
//因此在循环的开始我们要找到更小的孩子节点，然后再判断与双亲节点的大小比较
//后续操作与上相似，不在过多阐述。
void AdjustDown(HPDataType* a, int size, int parent)
{
assert(a);
int child = parent*2 + 1;
while (child < size)
{
//找较小的孩子节点
if (child+1 < size && a[child] > a[child + 1])
{
child++;
}
//调整双亲节点和孩子节点的关系
if (a[child] < a[parent])
{//交换
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{//退出
break;
}
}
}
// 堆顶的删除
//对于删除操作，我们首先要知道，删除堆尾的操作只需一步就能完成，因为并不会影响其他的数组元素
//所以我们讲的删除大多数都是删除堆顶，而删除堆顶我们想到第一步是从前向后一次向前覆盖一个元素
//但是这样会导致之前建的小堆的所有顺序发生错乱，再重新调整极为麻烦，因此前人钻研出了更好的方法
//首先是讲队尾和堆顶的元素进行交换，然后--size删除原堆顶元素，随后将新的堆顶元素进行向下调整
//我们就完成了我们想要的操作，此操作也为堆排序打下了基础，是堆排序的前身。
void HeapPop(Heap* php)
{
assert(php);
//堆顶和堆尾交换
Swap(&php->a[0], &php->a[php->size - 1]);
//删除堆尾
php->size--;
//向下调整建小堆
AdjustDown(php->a, php->size, 0);
}
//后面的操作较为简单，不在赘述了。
// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
// 堆的数据个数
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php)
{
assert(php);
if (php->size == 0)
return 0;
else
return 1;
}建堆的时间复杂度问题：
因为堆是完全二叉树，而满二叉树也是完全二叉树的一种， 时间复杂度通常看的是最坏情况下所用的时间，所以这里使用最坏情况计算，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：
在建堆研究的初期，人们首先发明的是向上调整算法建堆，方法就是将数据一个一个按顺序从堆尾插入（push），每插入一个数据就进行一次向上调整到建堆。代码如下：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
void Heaptop1()
{
//向上调整算法建(小)堆
//任意创建数组
int arr[] = { 4,5,8,7,4,8,1,9,4,8,1,1,6,999,555,666 };
int sz = sizeof(arr) / sizeof(arr[0]);
//创建结构体
Heap hp;
//初始化结构体
HeapInit(&hp);
//建堆
for (int i = 0;i < sz; i++)
{
HeapPush(&hp, arr[i]);
}
//打印
for (int j = 0; j < sz; j++)
{
printf("%d ", hp.a[j]);
}
}
随着计算机技术的发展，人们有发明了更高效的建堆算法，即向下调整算法建堆。思路相交于上面的算法略有不同，我们首先将所有的数据全部压入堆中，然后在最后一个根节点开始向前遍历，在遍历到的每个节点通过向下调整函数进行调整，直到遍历完根节点。
很多人可能听到这里会有疑惑，因为单凭肉眼很难看出两种算法的计算次数差距，不要着急，我们先来看看代码：
void Heaptop2()
{
//向下调整算法建(小)堆
int arr[] = { 4,5,8,7,4,8,1,9,4,8,1,1,6,999,555,666 };
int sz = sizeof(arr) / sizeof(arr[0]);
Heap hp;
HeapInit(&hp);
//sz-1是最后一个叶子节点的下标，其双亲节点就是最后一个根节点
for (int i = 0; i < sz; i++)
{
//这里的push函数和向上调整算法里的push函数有所区别。
//上方的函数中在最后有向上调整函数，此处没有，所以只是单纯的将数据插入堆中
HeapPush(&hp, arr[i]);
}
for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(hp.a, sz, i);
}
//打印
for (int j = 0; j < sz; j++)
{
printf("%d ", hp.a[j]);
}
}
我们可以看到两种建堆方式的结果有略微差异，但都符合建堆的条件。
通过计算我们可以看出向下调整建堆的效率优于向上调整建堆，因此在未来我们大多数情况下都会使用向下调整建堆来进行后续操作。
堆排序
堆排序是一种新的排序方式，通过堆排序我们能更快的对所有数据进行调整，代码如下：
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
//建堆后的调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i); //N*logN
}
//排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]); //O(1)
AdjustDown(a, end, 0); //logN
end--;
}
}
思路：这里的建堆思路与排序的要求有关，以降序排列为例，我们如果想要得到降序排列的数组，就要建小堆，然后将第一个数据(根节点)与最后一个(第n个)节点的数据进行交换，对前n-1个数据进行重新向下调整，此时的根节点就是第二小的数据，随后重复之前操作。
综上，我们能够看出堆排序的时间复杂度为N*logN，相比于之前的冒泡排序，极大的提高了排序效率。
TOP-K问题
TOP-K问题：即求数据结合中前k个最大元素或最小元素，一般情况下数据量较大。
对于TOP-K问题，我们目前能想到的最简单直接的方式就是排序，但是如果数据量非常的大，排序就不太可取了(数据太多可能导致数据无法一次性全部加载到内存中)。
最佳的方式是用堆来解决，而建堆也分建大堆和小堆，我们常用的思路是：如果要得到的是最大的前k个数，我们就应该用降序来排列数据，这样前k个数就是最大的前k个。但是从大局来看，如果我们要这样计算，那我们就需要建一个能够储存所有数据的大堆，如果数据的数量远大于我们拥有的内存，这种方式就不可取了。到这里我们可能就没有思路了，那我们就来看一下前辈们是怎么想的。
基本思路如下：
1、用数据集合中的前K个元素来建堆，如果是前K个最大的元素，则建小堆；如果是前K个最小的元素，则建大堆。
2、用剩余的N-K个元素依次与堆顶元素来比较，当遍历到的元素满足条件时，则替换堆顶元素。将剩余的N-K个元素依次与堆顶元素比较完之后，堆中剩余的K个元素就是所求的前K个最小或最大的元素。
我们来举个例子：当一个文本文件中有10亿个数据，我们需要找到里面最大的前10个数据，根据上述思路，我们先建一个能存十个数的堆，因为我们要找的是最大的数，所以我们要建立小堆，这样可以将大数存放到根节点下面，根节点在堆中就是最小的数，然后遍历剩余数与根节点比较，如果遍历到的数大于根节点，就将此数赋值给根节点，然后向下调整，找出堆中下一个最小的数放到根节点，继续执行上述操作，直到遍历结束。这样堆中的数就是最大的前十个了。
代码演示：
//首先我们通过文件操作在data.txt文件中创建一个文本。
//通过随机种子随机创建n个数据，因为时间戳的特性，我们将生成的随机数进行+i
//这样有利于随机数的分散。
void CreateNDate()
{
// 造数据
int n = 100000;
srand((unsigned int)time(NULL));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//接下来就是对文本文件中的数据进行TOP-K操作了。
//我们首先确定堆的大小，然后开辟一块该大小的空间
//通过文件操作先将前k个数据放入堆中，然后对堆进行向下调整、
//随后遍历剩余n-k个数据与堆顶进行比较，最终得到topk。
void HeapTop3()
{
int k = 0;
printf("请输入k值:>");
scanf("%d", &k);
int* a = (int*)malloc(sizeof(int) * k);
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
//向堆中入k个数据
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &a[i]); //k
}
//对堆中数据进行调整
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, k, i); //logk
}
//核心操作：遍历文本与堆顶比较
int n = 0;
while (fscanf(fout, "%d", &n) > 0)
{
if (n > a[0])
{
a[0] = n;
AdjustDown(a, k, 0); //（n-k）*logk
}
}
//关闭文件
fclose(fout);
//打印topk
for (int i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
}由代码中注释可知topk算法的时间复杂度为O(N)。
