树
概念
树是一种常见的非线性的数据结构，，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
相关的基本概念
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；
一些概念类似于祖辈关系；
起始结点称为根节点，也就是图中的A；
树可以分为很多种子树，子树部分可以也有自己的根节点；
树是递归定义的。
树的表示
对于树来说，结构比较复杂，存储起来比较困难；既要保存数据，又要保证节点与节点之间的联系；在实际中，有这几种表示方法：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
这里介绍其中的一种：孩子兄弟表示法：
typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };
二叉树
概念
二叉树是一种特殊的树结构，每个节点最多可以有两个子节点。且这两个节点分别称之为左子树和右子树（左孩子和右孩子）；节点也可以没有子节点和只有一个子节点；
二叉树是有左右之分的，是一种有序树；
特殊情况：
特殊二叉树
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
. 
性质
1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n2＝ n0＋1.
看下面一道例题：
堆
二叉树的顺序结构
一般的二叉树，是不适合用数组的存储结构来表示的，只有完全二叉树这种连续性的树结构才适合，在现实中，堆就是用这种结构来存储的。
注意：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
堆的概念
堆其实就是一颗完全二叉树，除最后一层的叶节点，其他层的节点全是满的。堆又分为大堆和小堆。在小堆中，对于任意节点i，父节点的值小于等于子节点的值；在大堆中，对于任意节点i，父节点的值大于等于子节点的值。实际中，堆还是数组，只是存储的逻辑顺序是完全二叉树的从上到下的顺序。
堆的实现
这是堆结构
typedef int HPDataType; typedef struct Heap { HPDataType* a; //存储的数组 int size; //存储的大小 int capacity; //数组的大小 }HP;
初始化
void HeapInit(HP* php) { assert(php); php->a = NULL; php->capacity = php->size = 0; }
将数组初始化为空，存储量和容量都设为0即可；
数组初始化为堆
有时我们会将一个数组变成堆的存储结构；
void HeapInitArray(HP* php, int* a, int n) { assert(php); assert(a); //先将堆的数组创建空间 php->a = (HPDataType*)malloc(sizeof(HPDataType)*n); if (php->a == NULL) { perror("HeapInit Fail"); exit(-1); } php->capacity = php->size = n; //复制过去 memcpy(php->a, a,sizeof(HPDataType)* n); //建堆 for (int i = 1; i < n; i++) { AdjustUp(php->a, i);//向上调整 } }
向上调整是孩子可能会变化为父亲，所以从第1个下标开始，而不是第0个；
向上调整
这里先说一下父亲与孩子下标的关系：
由于堆的概念，当我们插入一个数据进去或者想将数组变化为数组时，需要对这个存储的数据进行调整；而我们调整的逻辑，就是根据堆的结构去调整的。
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustUp(HPDataType* a, int child) { assert(a); //父亲节点 HPDataType parent = (child - 1) / 2; while (child > 0) { //孩子节点的值比父亲节点的值小就交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } else { break; } } }
利用循环来进行调整，这种调整，前提是前面的结构是堆，时间复杂度为O（logN）；
向下调整
有向上调整，自然有向下调整，对于堆顶的值的插入，就需要进行向下调整。
void AdjustDown(HPDataType* a, int n, int parent) { assert(a); HPDataType 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 = child * 2 + 1; } else { break; } } }
这里以左孩子为主，当右孩子比左孩子大时，就将右孩子与父亲节点进行比较；
插入
我们会在数组的size的后面进行插入，也就是堆底；
void HeapPush(HP* 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"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } //插入 php->a[php->size] = x; php->size++; //向上调整 AdjustUp(php->a, php->size - 1); }
删除
我们删除的是堆顶的数据，如果按常规想法，删除堆顶数据，然后进行移动，可不可行呢？
显然是不行的，解决方法是先将最后一个数据与堆顶数据交换，然后对交换后的堆顶值进行向下调整。因为调换删除后，除了堆顶，下面的数据都满足堆的条件。
void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //堆顶与删除数据交换 Swap(&php->a[0], &php->a[php->size - 1]); //删除 php->size--; //向下调整 AdjustDown(php->a, php->size, 0); }
打印、摧毁、判空、获取堆顶数据
//打印 void HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); } //摧毁 void HeapDestory(HP* php) { assert(php); free(php->a); php->a = NULL; php->capacity = php->size = 0; } HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; } bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
验证
接下来就来进行验证
先验证数组初始化为堆：
int main() { int a[] = { 65,100,70,32,50,60 }; HP heap; HeapInitArray(&heap, a, 6); HeapPrint(&heap); return 0 }
接着依次验证插入删除和获取堆顶数据：
int main() { HeapInit(&heap); for (int i = 0; i < 6; i++) { HeapPush(&heap, a[i]); } HeapPrint(&heap); HeapPop(&heap); HeapPrint(&heap); printf("%d", HeapTop(&heap)); HeapDestory(&heap); return 0; }
堆的应用
接着说堆比较常用的两个应用，堆排序和TopK问题。
堆排序
第一种方法，我们的思路是，先建立一个堆结构，然后利用堆的删除思想进行排序。
//小堆 void HeapSort(int* a, int n) { //建堆 HP hp; HeapInit(&hp); for (int i = 0; i < n; i++) { HeapPush(&hp, a[i]); } //利用堆删除原理来进行排序 int i = 0; while (!HeapEmpty(&hp)) { a[i++] = HeapTop(&hp); HeapPop(&hp); } HeapDestory(&hp); } int main() { int a[] = { 2,3,5,7,4,6,8 }; HeapSort(a, sizeof(a) / sizeof(a[0])); return 0; }
这种方法，小堆对应的是升序；利用堆顶是最小的，然后对它取值后删除的原理进行排序，时间复杂度为O(N* logN * N);
还有一种方法，先对数组进行建堆，将堆顶与最后一个数据进行替换，以升序建大堆为例，最大的值与堆底替换后，那么最大的值就放在了最后的空间里了，再对数组长度做限制，那就可以完成排序了；
//小堆 void HeapSort(int* a, int n) { //升序：大堆 降序：小堆 for (int i = 1; i < n; i++) { AdjustUp(a, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] = { 2,3,5,7,4,6,8 }; HeapSort(a, sizeof(a) / sizeof(a[0])); return 0; }
时间复杂度O(N)=N*logN
显然下面方法排序的更快。
TopK问题
即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopk(const char* filename, int k) { //建堆 FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fout fail"); exit(-1); } int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("minheap fail"); exit(-1); } //数据输入 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); } //建堆 /*for (int i = 1; i < k; i++) { AdjustUp(minheap, i); }*/ 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\n", minheap[i]); } fclose(fout); } //数据创建 void CreateNDate() { int n = 1000000; srand(time(NULL)); const char* file = "data.txt"; FILE* bin = fopen(file, "w"); if (bin == NULL) { perror("FILE Fail"); exit(-1); } for (int i = 0; i < n; i++) { int x = (rand() + i) % 1000000; fprintf(bin, "%d\n", x); } fclose(bin); } int main() { //CreateNDate(); PrintTopk("data.txt", 5); return 0; }
先利用随机数创建一个数据文件，然后先将k个数据存储进数组中，接着建堆，最后将n-k个数据与堆顶进行比较，大于堆顶就进堆；
这里有两种建堆方法，一种是向上调整的建堆，另一种是向下调整的建堆；
向上调整的建堆：
向下调整的建堆：
时间复杂度T(N)=N;
从简单的角度来看，向上调整时，堆底的最底层数据几乎是堆的一半，都需要向上调整；而向下调整，堆顶只有一个，相比之下，向下调整肯定所用时间比较少。
