一.堆的应用
1.1堆排序（向下调整在上一期）
向上调整算法建堆：
首先先回顾一下向上调整算法
void AdjustUP(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;//找到父结点的位置
while (child > 0)//循环，确保父结点一定小于（大于）子结点
{
//小堆:<
//大堆:>
// |
// V
if (arr[child] > arr[parent])
{
//调整位置
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}在上一期我们也学过了向下调整算法建堆，其是通过由下向上循环，通过确保父结点下方的是堆结构，而向上算法建队=堆就刚好反过来，是由上到下进行循环。
//堆排序
void HeapSort(int *arr,int n)
{
//建堆--向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDOWN(arr, i, n);
}
//建堆--向上调整
for (int i = 0; i < n; i++)
{
AdjustUP(arr, i);
}
//排序
int end = n - 1;
while (end > 0)
{
Swap(&arr[end], &arr[0]);
AdjustDOWN(arr, 0, end);
end--;
}
}
1.2.TOP-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是:如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下:
通过前面的学习可了解到，小堆的堆顶是数据的最小值，所以若想通过小堆找最小，就需要遍历所有的数据，在进行堆排序，这对于大数据肯定是不行的，
那么换一种思路，用小堆找最大数据：将前K个数据直接建小堆，然后再遍历剩下的n-k个数据，将其与堆顶进行比较，若比堆顶大，则替换堆顶，来回重复，最后构成一个新堆，该堆就是数据中前K大的数。
而找前K小的数据道理相同，所以就可以总结出：
找最大的前K个数据，建小堆
找最小的前K个数据，建大堆
实践：
先通过代码生成10万个数据，并保存在data.txt文件中
随后实现topK函数：
void TopK()
{
int k =0;
printf("请输入k:");
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail");
exit(1);
}
//找最大的前K个数据--建小堆
//找最小的前K个数据--建大堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
exit(1);
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
//minHeap -- 向下调整建堆
for (int i = (k - 2) / 2; i >=- 0; i--)
{
//找最大的前K个数据--建小堆
//找最小的前K个数据--建大堆
AdjustDOWN(minHeap, i, k);
}
//遍历剩下的n-k个数据，跟堆顶比较，堆顶小替换堆顶数据
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
//找最大>
//找最小<
if (x > minHeap[0])
{
minHeap[0] = x;
AdjustDOWN(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
printf("\n");
fclose(fout);
}先读取文件数据，取前K个保存在数组中，并构成堆，随后遍历剩下的n-k个数据，进行比较替换。
最后成功打印
二.实现链式结构二叉树
二叉树的相关知识需要用到递归知识，所以建议先学习递归后再来看以下文章！！！
2.1二叉树的插入与删除
数据的插入和删除可以在二叉树的任何位置，所以此时暂时不写文章，在后期学习到平衡树，红黑树等在进行编写。
2.2二叉树的遍历
二叉树的遍历有前序/中序/后序的遍历的递归结构遍历：
1）前序遍历：访问根节点的操作在遍历其左右子树之间
访问顺序为:根结点、左子树、右子树
2）中序遍历:访问根结点的操作发生在遍历其左右子树之中(间)
访问顺序为:左子树、根结点、右子树
3）后序遍历:访问根结点的操作发生在遍历其左右子树之后
访问顺序为:左子树、右子树、根结点
遍历的实现：
通过函数的递归实现遍历，需要先判断递归条件，当目前根节点为NULL时，递归中止，拿前序遍历为例，在目前根节点时，先访问根节点的data，随后根据前序遍历的顺序，分别访问左子树，右子树，进行递归。那么中序遍历与后序遍历也就很好写出来了。
构造文章上文的二叉树例子，然后进行遍历输出：
2.3二叉树的结点个数
1.运用二叉树遍历的知识，通过递归遍历每一个结点，然后size++,那么结果会是什么呢？
int BinaryTreeSize(BTNode* root)
{
int size = 0;
if (root == NULL)
{
return;
}
//结点非空，+1
size++;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}运行后可以发现，不管调用几次，size都为1，原因是因为，每次递归size都被初始化为0
2.那么把size设为全局变量后是不是就可以避免了？
int size = 0;
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return;
}
//结点非空，+1
size++;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}运行后发现，虽然第一次调用size的结果是正确的，但是经过多次调用，size的值就会越加越大。
3.这次换一种思路，直接把size设为参数进行调用。
int BinaryTreeSize(BTNode* root, int size)
{
if (root == NULL)
{
return;
}
//结点非空，+1
size++;
BinaryTreeSize(root->left,size);
BinaryTreeSize(root->right,size);
return size;
}这一次发现结果又变为三个1，分析原因，当递归回溯的时候，size的值会返回到上一步的值，例如当递归到4结点时，size=3，但是回溯到2结点时，size又回到了2
4.要解决这个问题，把传值调用改为传址调用就可解决。
int BinaryTreeSize(BTNode* root,int*size)
{
if (root == NULL)
{
return 0;
}
//结点非空，+1
(*size)++ ;
BinaryTreeSize(root->left,size);
BinaryTreeSize(root->right,size);
return *size;
}这时结果就正确了，但是，每次调用参数，都需要把size初始化为0，有一点麻烦，在对函数进行改造
分析二叉树可知，结点数 = 根结点+左子树的结点数+右子树的结点数
最终版：
//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
//结点非空，+1
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
2.4二叉树叶子结点数
叶子结点数 = 左子树叶子节点数 + 右子树叶子结点数
结合刚才学到的结点数的知识，可以写出：
//二叉树叶子节点数
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);
}
2.5二叉树第K层结点个数
//二叉树第K层结点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
2.6二叉树的深度
深度 = 根结点 + max（左子树的深度+右子树的深度）
//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right));
//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right));
}
2.7二叉树查找值为x的结点
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDtatatype x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode*leftFind = BinaryTreeFind(root->left, x);
if (leftFind)
{
return leftFind;
}
BTNode*rightFind = BinaryTreeFind(root->right, x);
if (rightFind)
{
return rightFind;
}
}
2.8二叉树的销毁
//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{
if (root == NULL)
{
return;
}
BinaryTreeDestroy(&((*root)->left));
BinaryTreeDestroy(&((*root)->right));
free(*root);
*root = NULL;
}二叉树的层序遍历
借助数据结构--队列
首先将之前所编写过的队列的.h和.c文件导入进来
注意：
1.要包含队列的头文件
2.修改队列的头文件：修改队列的保存类型，务必要加struct，为了告诉编译器BinaryTreeNode是个结构体。
2.9层序编列实现：
//层序遍历
void levelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode*top = QueueFront(&q);
QueuePop(&q);
printf("%c ", top->data);
//将左右孩子入队列
if (top->left)
QueuePush(&q, top->left);
if (top->right)
QueuePush(&q, top->right);
}
QueueDestrory(&q);
}
2.10判断是否为完全二叉树
前置知识：完全二叉树的特点：
1）最后一层节点个数不一定达到最大
2）结点从左到右依次排列
与二叉树的层序遍历相同，借助队列进行实现：
在第一个循环中，取队头，出对头，直到遇到第一个空结点出循环，并进入到第二个循环。
若在第二个循环中，从非空队列中取到了非空的队头结点，那么该二叉树一定不是完全二叉树，否则一定是完全二文树
//判断是否为完全二叉树
bool BinaryTreeComlete(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top == NULL)
{
break;
}
QueuePush(&q, top->left);
QueuePush(&q, top->right);
}
//队列不一定为空
while(!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top != NULL)
{
return false;
}
}
QueueDestrory(&q);
return true;
}
以上图做例子，应不是完全二叉树：符合预期
把G H I结点去掉后应为完全二叉树：符合预期
