1. TOP-K问题
TOP-K问题：求数据结合中前K个最大或者最小的数据
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等
思路：
1. 用数据集合中前K个数据来建堆：
a. 前k个最大的数据，则建小堆
b. 前k个最小的数据，则建大堆
一般推荐建小堆
2. 用剩余的数据依次与堆顶的数据来比较，如果比堆顶的数据大就替换堆顶数据（覆盖位置，向下调整）
将剩余的数据依次与堆顶元素比完之后，堆中剩余的数据就是所求的前K个最小或最大的元素
通俗来讲就是：用前K个数建立一个小堆，然后剩下的数依次遍历和堆顶最小的数据比较，如果比堆顶的数据大,就把大的数赋给堆顶，再向下调整，最后堆里剩下的K个数就是最大的K个 ，因为小堆的堆顶一定是最小的数，只要随便拿个数比他大就交换他俩，大的那个数进入堆后再建小堆，大的数就沉在最下面，所以最后堆里面一定是K个最大的数
#include <stdio.h>
#include <stdlib.h>
#include <time.h>void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {if (child + 1 < size && 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 CreateNData()
{int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; i++) {int x = rand() % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}// 建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");fclose(fout);
}int main()
{CreateNData();PrintTopK(5);return 0;
}2. 二叉树（BinaryTree）
2.1 介绍
前面我们的完全二叉树和满二叉树是使用数组来存储，如果不是完全二叉树和满二叉树就不适合使用数组存储，更适合链式结构来存储
二叉树是：
1. 空树
2. 非空：根结点，根结点的左子树、根结点的右子树组成的
3.二叉树是递归结构
二叉树是整棵树拆分为根和子树，然后拆分过的子树再作为根继续拆分 ，一直这样持续至最后一个没有子树的根
在遍历之前先手搓一个二叉树的基础模板（Creat Binary Tree）：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<stdbool.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->val = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//node1的左和右指向node2和node4node1->left = node2;node1->right = node4;//node1的左指向node3node2->left = node3;//node4的左和右指向node5和node6node4->left = node5;node4->right = node6;return node1;
}int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();return 0;
}2.2 二叉树的遍历
前序遍历 （Prer Order）
访问顺序：（根 左子树 右子树 )任何一棵树的访问，都要符合前序，被拆成根 左子树 右子树
访问顺序为：
//前序
void PrerOrder(BTNode* root)
{//如果根为空if (root == NULL){printf("N ");return;}else{//打印根的数printf("%d\n", root->val);//打印完之后访问根的左子树和右子树PrerOrder(root->left);PrerOrder(root->right);}
}
代码执行完成之后就进行递归调用，一直到遇到空根结束
int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();PrerOrder(root);printf("\n");return 0;
}
中序遍历（In Order）
访问顺序：（左子树 根 右子树 ）任何一棵树的访问，都要符合中序，被拆成左子树 根 右子树
访问顺序为：
//中序
void InOrder(BTNode* root)
{//如果根为空if (root == NULL){printf("N ");return;}else{//先访问左子树InOrder(root->left);//打印根的数printf("%d\n", root->val);//打印完之后访问根的右子树InOrder(root->right);}
}
int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();//中序//InOrder(root);printf("\n");return 0;
}
后序遍历（Post Order）
访问顺序：（左子树 右子树 根）任何一棵树的访问，都要符合后序，被拆成左子树 右子树 根
访问顺序为：
//后序
void PostOrder(BTNode* root)
{//如果根为空if (root == NULL){printf("N ");return;}else{//先访问左子树和右子树PostOrder(root->left); PostOrder(root->right);//再打印根的数printf("%d\n", root->val);}
}int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();//前序//PrerOrder(root);//中序//InOrder(root);//后序PostOrder(root);printf("\n");return 0;
}
求二叉树节点的个数 （Tree Size）：
节点个数：
1.如果为空，则为0
2.如果不为空，则是左子树 + 右子树 + 1
//求整棵树节点的个数
int TreeSize(BTNode* root)
{//如果为空则返回0，不为空则返回左子树加右子树加1return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}
int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();//前序//PrerOrder(root);//中序//InOrder(root);//后序//PostOrder(root);//printf("\n");//求整棵树节点的个数printf("TreeSize:%d\n", TreeSize(root));return 0;
}获取叶子节点个数（Tree Leaf Size）：
叶子：就是度为0，不包括任何子节点，通俗来讲就是没有孩子的节点
//获取叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left)+ TreeLeafSize(root->right);
}int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();//前序//PrerOrder(root);//中序//InOrder(root);//后序//PostOrder(root);//printf("\n");//求整棵树节点的个数//printf("TreeSize:%d\n", TreeSize(root));//获取叶子节点个数printf("TreeLeafSize:%d\n", TreeLeafSize(root));return 0;
}二叉树的高度 （Tree Height）：
二叉树的高度是有几层高度就是几
//二叉树的高度
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;//使用两个变量记录下来，避免重复计算int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ?leftHeight + 1 : rightHeight + 1;
}
int main()
{//root:根 CreatBinaryTree：创建二叉树BTNode* root = CreatBinaryTree();//前序//PrerOrder(root);//中序//InOrder(root);//后序//PostOrder(root);//printf("\n");//求整棵树节点的个数//printf("TreeSize:%d\n", TreeSize(root));//获取叶子节点个数//printf("TreeLeafSize:%d\n", TreeLeafSize(root));//二叉树的高度printf("TreeHeight:%d\n", TreeHeight(root));return 0;
}二叉树第k层结点个数：
// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;// 子问题return TreeLevelKSize(root->left, k - 1)+ TreeLevelKSize(root->right, k - 1);
}二叉树查找值为x的结点：
// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret1 = TreeFind(root->left, x);//如果找到了直接返回数值，没有找到直接返回空if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);//如果找到了直接返回数值，没有找到直接返回空if (ret2)return ret2;return NULL;
}休息一下，马上回来~
