1.Topk問題

?TOP-K問題：即求數據結合中前K個最大的元素或者最小的元素，一般情況下數據量都比較大。
?1.用數據集合中前K個元素來建堆。
?前k個最大的元素，則建小堆
?前k個最小的元素，則建大堆

?思路解答：假設求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.二叉樹的前序，中序，后序

? 二叉樹的遍歷，因為樹不是線性結構，可以劃分成子問題來求解，根據遞歸先后順序不同，可以分為以下三種遍歷順序。
??前序：根、左子樹、右子樹
??中序：左子樹、根、右子樹
??后序：左子樹、右子樹、根

?再次說明一下，二叉樹數是要依靠遞歸遍歷的，根據遍歷的順序不同，分為三種情況。
?上面二叉樹的前序遍歷如下。
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就返回，因為走到頭了，先訪問根，在訪問左子樹，右子樹。就整個遍歷完了。
?遞歸展開圖如下。

?在從代碼執行的角度來理解，畫遞歸展開圖。

?中序遍歷如下：
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);
}

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;
}

?這個問題比上面的遞歸復雜一些，畫遞歸展開圖來理解找到錢目標值，怎么一步一步返回上去。

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);
}

?完結！ ?