1.Topk问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
1.用数据集合中前K个元素来建堆。
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
Alt

思路解答：假设求1亿个数中，前10个最大值。则建成10个数的小堆，剩余数与堆头数据比较，若比堆头数据大，则交换，向下调整成堆，小一点的数又排到对头，进行筛选，相当于建立了一个装载10个数的漏斗，进行筛选。

void CreatData()
{// 造数据int n = 100000;srand((unsigned int)time(0));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) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void topk()
{printf("请输入k：>");int k = 0;scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int val = 0;int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 建k个数据的小堆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 ", minheap[i]);}fclose(fout);}

时间复杂度：建立K个数的堆，建堆时间复杂度：O（k）,向下调整整成堆的时间复杂度：（N-k）* $log_2 k.,$ 则，合起来就是O（N） = O（k+（N-k） * $log_2 k$ ）。

2.二叉树的前序，中序，后序

二叉树的遍历，因为树不是线性结构，可以划分成子问题来求解，根据递归先后顺序不同，可以分为以下三种遍历顺序。
前序：根、左子树、右子树
中序：左子树、根、右子树
后序：左子树、右子树、根
Alt
再次说明一下，二叉树数是要依靠递归遍历的，根据遍历的顺序不同，分为三种情况。
上面二叉树的前序遍历如下。
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
代码如下：

typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;BTNode* BuyNode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}BTNode* CreatTree()
{BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);BTNode* n5 = BuyNode(5);BTNode* n6 = BuyNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}

因为是递归写的，刚学习不好理解。从大的层面来讲，先遍历根，在遍历左子树，在遍历右子树。
写好递归就两个条件：
<1>递归子问题
<2>返回条件
上面前序的遍历，遇到NULL就返回，因为走到头了，先访问根，在访问左子树，右子树。就整个遍历完了。
递归展开图如下。
Alt

在从代码执行的角度来理解，画递归展开图。
Alt

中序遍历如下：
NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL");return;}InOrder(root->left);printf("%d ",root->val);InOrder(root->right);
}

后序遍历如下：
NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1\

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

Alt

3.求二叉树的个数（TreeSize）。

<1>递归子问题:左子树的个数+右子树的个数+1（本身的个数）
<2>返回条件：遇到 NULL，结束，返回0

int TreeSize(BTNode* root)
{if (root == NULL)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}

4.求二叉树的最大深度（maxDepth）。

<1>递归子问题:左子树的高度和右子树的高度比较，取最大的，然后加自身的高度。（本身的个数）
<2>返回条件：遇到 NULL，结束，返回0

int  maxDepth(BTNode* root)
{if (root == NULL )return 0;int LeftDepth = maxDepth(root->left);int RightDepth = maxDepth(root->right);return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;
}

5.求二叉树的第K层的节点个数（TreeKLevel）。

<1>递归子问题:当前的第k层的个数 = 左子树的k-1层个数+右子树的k-1层个数
<2>返回条件：遇到NULL 返回0；不为NULL，k== 1,则就是要找的这一层的节点，返回1。

int TreeKLevel(BTNode* root,int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

6.查找二叉树的节点（FindNode）。

<1>递归子问题:先去左子树找，找不到，再去右子树找
<2>返回条件：为NULL，返回，NULL；找到，则返回节点地址。

BTNode* TreeFind(BTNode* root,int x)
{if (root == NULL)return NULL;if (root->val == x)return root;//找节点BTNode* leftNode = TreeFind(root->left, x);if (leftNode)return leftNode;BTNode* rightNode = TreeFind(root->right, x);if (rightNode)return rightNode;return NULL;
}

这个问题比上面的递归复杂一些，画递归展开图来理解找到钱目标值，怎么一步一步返回上去。
Alt

7.判断两棵树是否相同（isSameTree）。

<1>递归子问题:比较根，左，右子树是否相同
<2>返回条件：两棵树，同时遍历，都为NULL，True;其中一个不为NULL,false,两个比较的数不相等，直接false.

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL)return true;if(p == NULL || q == NULL)return false;if(p->val != q->val)return false;return isSameTree(p->right,q->right) && isSameTree(p->left,q->left);
}