3.二叉树的顺序存储——堆
顺序存储就是使用数组来存储，一般只适用于完全二叉树，因为使用数组存储的时候，是一层一层存储的，如果不是完全二叉树的话，会造成空间浪费。在实际运用中，只有堆才会使用数组存储。
二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树
堆的概念
如果有一个关键码的集合K = { k0，k1，k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=K2i+1 且 Ki<=K2i+2 (Ki>=K2i+1 且 Ki>=K2i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆的实现
由于堆在物理上的存储是一个数组（顺序表），所以我们定义的堆的存储结构如下：
typedef int HPDataType; typedef struct Heap { HDataType* a;//保存堆内数据的数组 int size;//堆内数据个数 int capacity;//堆的容量 }Heap;
堆的接口：
1、初始化
就是顺序表的初始化，我们直接将结构体中的_a初始化为NULL，之后插入数据的时候再扩容。
void HeapCreate(Heap* php) { assert(php); php->_a = NULL; php->_capacity = php->_size = 0; }
2、销毁
销毁的过程就是将动态开辟的内存释放即可。
void HeapDestory(Heap* php) { free(php->_a); free(php); php->_a = NULL; php = NULL; }
3、插入数据并保持堆的结构
向上调整
我们是使用一个数组保存堆内数据的，所以插入数据的时候，肯定不会在头部或者中间位置插入，而是在数组尾部插入数据。我们的目的是为了插入数据后还保持堆的结构，那么插入数据之后就需要将堆内的最后一个数据向上调整。
对于上述的小堆，我们要在后面插入10，插入之后，显然不是堆了，所以我们要进行向上调整。首先要明确的是，我们插入数据之后，对堆的影响只是插入的这个数据的父节点，对其他兄弟节点是没有影响的，所以我们要判断插入的这个数据是否会使堆的结构发生变化，例如上图中我们插入10，但是10的父节点大于它，这显然不满足小堆的结构，那么我们就需要进行向上调整。现在问题又来了，在物理结构中，堆是用数组存储的，怎么找到他的父节点呢？这里有一个结论**lchild = 2*parent+1，rchild = 2*parent+1**,那么我们根据这个结论，可以推出来(children -1)/2得到的肯定是父节点，不管这个children是左节点还是右节点。所以向上调整的算法就有了
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustUp(HPDataType* a, int child)//向上调整 { int parent = (child - 1) / 2; while (child > 0) { if (a[parent] > a[child]) { Swap(&a[parent], &a[child]); child = parent; parent = (child - 1) / 2; } else { break; } } }
有了向上调整算法，那么我们push数据的接口也就很容易实现了。
void HeapPush(Heap* hp, HPDataType x) { if (hp->_capacity == hp->_size)//检查堆容量，决定是否扩容 { int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2; HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } hp->_a = tmp; hp->_capacity = newCapacity; } hp->_a[hp->_size] = x;//插入数据 hp->_size++; //向上调整 AdjustUp(hp->_a, hp->_size - 1); }
4、取出堆顶的数据
堆顶的数据也就是数组中的第一个元素，所以取出堆顶的数据就是返回数组中的首元素
HPDataType HeapTop(Heap* hp) { assert(hp); assert(!HeapEmpty(hp)); return hp->_a[0]; }
5、删除堆顶的数据
堆顶的数据也就是数组中的首元素，如果按照删除首元素的方式删除堆顶数据的话，我们还需要将后面的数据向前挪动，但是如果这样做，挪动数组的时间复杂度就已经是O(N)了，而且这个时候会将原本的堆的结构破坏。所以我们找到了一种新的方法将堆顶的数据与最后一个数据交换，让size–，然后向下调整堆。
向下调整
交换数据之后，堆顶的元素是不符合堆的结构的，已知删除堆顶的元素之后，次小或者次大的元素只会在堆顶的左右孩子中出现，所以我们应该在左右孩子中找到一个最大或者最小的数据代替堆顶的位置，然后一直向下，进行交换数据，直到符合堆的结构
void AdjustDown(HPDataType* a, int n, int parent)//向下调整 { int minChild = parent * 2 + 1; while (minChild < n) { //找到较小的孩子 if (minChild + 1 < n && a[minChild + 1] < a[minChild]) { minChild++; } if (a[minChild] < a[parent])//判断是否需要调整 { Swap(&a[minChild], &a[parent]); parent = minChild; minChild = parent * 2 + 1; } else { break; } } }
注意：只有左右子树都为小堆或者都为大堆的时候才能使用向下调整建堆。
有了向下调整的的接口，删除堆顶元素的接口就很容易实现了
void HeapPop(Heap* hp) { assert(hp); assert(!HeapEmpty(hp)); Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//交换数据，删除堆底数据 hp->_size--; AdjustDown(hp->_a, hp->_size, 0); }
6、判断堆是否位空
在上述的几个接口中，都用到了一个函数，就是判断是否为空，当size为0的时候就是堆为空的时候。
int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; }
7、返回堆内数据个数
堆内的数据个数在定义结构体的时候就已经确定，size保存的就是堆内数据个数。这个时候就会有人说了，反正有一行代码，为什么我们还要写一个函数呢？当我们调用函数的时候还会创建函数栈帧，降低效率，为什么不能直接访问结构体内部的size，这样不是更方便吗？
注意：这里之所以用一个函数返回堆内的数据个数，是出于封装的角度考虑的，如果我们直接访问结构体内部的数据，我们不会知道函数的实现者是怎么实现的，如果实现者在实现插入函数的时候没有将size++，那么size就是最后一个元素的下标，就不是数据个数，这样我们得到的数据就是错误的，所以我们应该直接调用函数来得到这个数据。
int HeapSize(Heap* hp) { assert(hp); return hp->_size; }
堆的应用
堆排序
在最常用的排序中就有一个排序叫做堆排序，它是一个效率达到O(N*logN)的排序算法，我们在之前实现堆的接口的时候，实现了删除堆顶的元素。根据堆的结构性质，我们知道堆顶的元素是整个堆中最大的或者最小的数，所以由此我们就可以通过每次删除堆顶的元素，从而达到排序的目的。
堆排序的步骤
- 建堆
- 升序建大堆
- 降序建小堆
- 利用堆删除的思想进行排序
如果我们要对一组数据进行升序排列，我们要建大堆还是小堆呢？一般情况，升序首先肯定找最小的，所以应该建小堆，但是如果建小堆的话，我们确实把最小的数据排好了，但是对于次小的数，我们要怎么找到呢？如果说把后面n-1个数据重新建堆的话，我们就利用不到之前建堆的优势了。而且建一个堆的时间复杂度最少是O(N)，如果真的按照这种方法进行下去，那么堆排序的时间复杂度就会是O(N2)，而且没有充分利用堆的结构。如果建大堆的话，我们每次找到最大的数，然后和最后一个数据进行交换，然后把前n-1个数据当作堆，这个时候,由于左右子树都为大堆，我们可以使用向下调整，就可以将前n-1个数据变成一个大堆，这样循环往复，就可以将整个数组按升序排好。
根据之前实现的堆的接口，我们知道建堆有两种方式：向上调整建堆和向下调整建堆。
向下调整建堆的时间复杂度
这里需要注意一下，最后一层是不需要调整的，因为向下调整的前提是左右子树都是大堆或者都是小堆，而叶子节点本身就可以看作是一个堆，所以我们只需要从最后一个非叶子节点开始调整就可以。这样的话，我们可以节省最多一半的时间（因为如果是满二叉树，最后一层节点的个数是整个二叉树节点的一半）。 所以时间复杂度是O(N).
向上调整建堆的时间复杂度
所以时间复杂度是O(N*logN).
所以我们在堆排序的时候选择的调整方式是向下调整建堆。
typedef int HPDataType; void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void AdjustDown(HPDataType* a, int n, int parent)//堆向下调整 { int minChild = parent * 2 + 1; while (minChild < n) { //找到较小的孩子 if (minChild + 1 < n && a[minChild + 1] > a[minChild]) { minChild++; } if (a[minChild] > a[parent]) { Swap(&a[minChild], &a[parent]); parent = minChild; minChild = parent * 2 + 1; } else { break; } } } // 对数组进行堆排序 void HeapSort(int* a, int n) { //从最后一个非叶子节点向下调整建堆 //升序建大堆，降序建小堆 for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(a, n, i); } //选数 for (int i = 1; i < n; i++) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); } }
Top-K问题
找出N个数里面最大/最小的前K个问题。
比如：西安排名前10的泡馍，王者荣耀全服排名前10的韩信，等等问题都是Top-k问题。
对于Top-K问题，我们能想到最直接的办法就是将数据全部排序，然后取出前K个大或者前K个小的数据，但是如果遇到数据量非常大的情况，他们甚至都不能一次性全部加载到内存中，这时候最佳的方案就是建堆,既然我们要找出前K大或者前K小的数，那么我们就建一个K个数的堆。然后通过遍历整个数组，对这K个数进行处理，从而达到前K个数就是我们要找的最大或者最小的数。建堆的时候，为了方便，我们就用N的数的前K个数建堆。
基本思路如下
- 用数据集合中前K个元素来建堆
- 找最大的前K个，建立K个数的小堆
- 找最小的前K个，建立K个数的大堆
- 用剩下的N-K个元素依次与堆顶的元素比较，不满足则替换堆顶元素
注：我们要找到最大的前K个，如果建小堆，那么就可以知道我们选出的前K个数的最小的那个，遍历后面的数据的时候，就与堆顶的数据比较，如果有任意数据大于堆顶的数，那么就替换堆顶元素，然后再执行向下调整堆顶的元素，使堆的结构保持不变。
代码实现：
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(HPDataType* a, int n, int parent)//向下调整 { int minChild = parent * 2 + 1; while (minChild < n) { //找到较小的孩子 if (minChild + 1 < n && a[minChild + 1] < a[minChild]) { minChild++; } if (a[minChild] < a[parent]) { Swap(&a[minChild], &a[parent]); parent = minChild; minChild = parent * 2 + 1; } else { break; } } } void PrintTopK(int* a, int n, int k) { //建立k个数的小堆 for (int j = (k - 2) / 2; j > 0; --j) { AdjustDown(a, k, j); } //继续遍历后面N-k个数 int val = 0; for (int i = k; i < n; ++i) { if (a[i] > a[0]) { Swap(&a[0], &a[i]); AdjustDown(a, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", a[i]); } }
4.二叉树的链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们只关注二叉链，后面讲到红黑树等会用到三叉链。
二叉树的遍历
前序、中序、后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
代码实现：
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) printf("NULL "); else { printf("%c ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) printf("NULL "); else { BinaryTreeInOrder(root->_left); printf("%c ", root->_data); BinaryTreeInOrder(root->_right); } } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) printf("NULL "); else { BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%c ", root->_data); } }
层序遍历
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。由于要一层一层的访问节点，所以我们需要记住需要访问的节点的父节点，然后根据访问该节点父节点的次序依次访问子节点，所以这里需要借助队列来实现层序遍历。
算法思想：
首先将二叉树的根节点指针入队列，然后如果队列不为空的话就取出对头数据，然后访问对头节点的数据域，这就是我们需要访问的二叉树的节点，然后再把这个节点的左右子树的根节点指针入队列，然后再递归这个算法，即可完成二叉树的层序遍历。
代码实现：
void BinaryTreeLevelOrder(BTNode* root) { Queue q;//创建队列 QueueInit(&q);//队列初始化 if (root == NULL) return; else { QueuePush(&q, root);//入队列 while (!QueueEmpty(&q))//判断队列是否为空 { BTNode* front = QueueFront(&q);//获得对头元素 QueuePop(&q);//出队列 printf("%c ", front->_data); //下一层入队列 if(front->_left) QueuePush(&q, front->_left); if (front->_right) QueuePush(&q, front->_right); } } QueueDestory(&q);//队列销毁 }
节点个数与高度、查找节点等接口
对于这一类问题，我们都可以使用递归分治的思想来解决
1、二叉树的节点个数
二叉树的节点个数就是该树的左子树的节点个数+右子树的节点个数+1，所以就可以以此类推递归下去
int BinaryTreeSize(BTNode* root) { if (root == NULL) return 0; else return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; }
2、二叉树叶子节点个数
计算叶子节点个数和计算节点个数是类似的，要注意的就是要判断该节点是否为叶子节点，如果不是就再次调用该函数找到该节点左右子树的叶子节点。
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->_left == NULL && root->_right == NULL) return 1; return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right); }
3、二叉树第k层节点个数
由于我们要使用递归的方式解决这个问题，那么递归的结束条件就是当k不大于1。否则就递归下去计算该节点左右子树的第k-1层节点个数。
int BinaryTreeLevelKSize(BTNode* root, int k) { //assert(k < 1); if (k <= 1) return root == NULL ? 0 : 1; else if (root == NULL) return 0; else return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1); }
4、二叉树查找值为x的节点
我们要查找值为x的节点，就要先遍历节点，依次与x相比较，当data==x的时候就return结果，但是与遍历不同的是这次我们有返回值需要通过递归带回来，那么我们怎么将值带回来呢？我们可以创建一个临时变量ret，如果该节点是空的就return NULL，如果该节点的data就是我们要找的data，那么我们就直接return root，如果该节点不是我们要找的，那么就再次调用该函数去该节点的左子树找，然后把返回值赋值给ret，此时如果找到了我们要的节点，那么ret就不为NULL，就return ret，程序结束，否则再去该节点的右子树寻找，然后return ret。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { BTNode* ret = NULL; if (root == NULL) return NULL; if (root->_data == x) return root; ret = BinaryTreeFind(root->_left, x); if (ret != NULL) return ret; ret = BinaryTreeFind(root->_right, x); return ret; }
二叉树的创建和销毁
1、二叉树的创建
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树（#表示空树）
BTNode* BTCreate(BTDataType* a, int* pi) { if (a[*pi] != '#') { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->val = a[*pi]; (*pi)++; tmp->left = BTCreate(a, pi); tmp->right = BTCreate(a, pi); return tmp; } else { (*pi)++; return NULL; } }
2、二叉树的销毁
由于二叉树是链式存储的，那么就要一个节点一个节点的释放，所以需要遍历节点、
void BinaryTreeDestory(BTNode** proot) { assert(proot); if (*proot == NULL) return; BinaryTreeDestory(&((*proot)->_left)); BinaryTreeDestory(&((*proot)->_right)); free(*proot); }
