前言

本篇文章講述的內(nèi)容有部分是上一節(jié)寫過的。重復(fù)內(nèi)容不會再進(jìn)行說明，大家可以看上一節(jié)內(nèi)容
鏈接: C語言數(shù)據(jù)結(jié)構(gòu)-----二叉樹(1)認(rèn)識數(shù)、二叉樹、堆及堆的代碼實(shí)現(xiàn)

---

1.使用堆解決TOP-K問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：

1. 用數(shù)據(jù)集合中前K個(gè)元素來建堆
   前k個(gè)最大的元素，則建小堆
   前k個(gè)最小的元素，則建大堆
2. 用剩余的N-K個(gè)元素依次與堆頂元素來比較，不滿足則替換堆頂元素
   將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;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){// 假設(shè)左孩子小，如果解設(shè)錯(cuò)了，更新一下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 AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;//child = (child - 1) / 2;//parent = (parent - 1) / 2;}else{break;}}
}void CreateNDate()//創(chuàng)建隨機(jī)數(shù)文本
{// 造數(shù)據(jù)int n = 10000000;srand(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) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 建一個(gè)k個(gè)數(shù)小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}// 讀取前k個(gè)，建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);AdjustUp(minheap, 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]);}printf("\n");free(minheap);fclose(fout);
}int main()
{CreateNDate();PrintTopK("Data.txt", 5);return 0;
}

2.向下調(diào)整堆的時(shí)間復(fù)雜度與向上調(diào)整堆的時(shí)間復(fù)雜度對比

總體而言
①向下調(diào)整堆的時(shí)間復(fù)雜度為：O[N-log₂(N+1)]，當(dāng)N足夠大時(shí)，約等于O(N)

②向上調(diào)整堆的時(shí)間復(fù)雜度為：

3.堆排序問題

堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個(gè)步驟：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆刪除思想來進(jìn)行排序 建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;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){// 假設(shè)左孩子小，如果解設(shè)錯(cuò)了，更新一下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 AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;//child = (child - 1) / 2;//parent = (parent - 1) / 2;}else{break;}}
}void HeapSort(int* a, int n)
{// 建大堆，向下調(diào)整// O(N*logN)/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*///建小堆，向上調(diào)整// O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] = { 4, 6, 2, 1, 5, 8, 2, 9 };HeapSort(a, sizeof(a)/sizeof(int));for (int i = 0; i < sizeof(a)/sizeof(int); i++){printf("%d ", a[i]);}printf("\n");return 0;
}

4.鏈?zhǔn)蕉鏄?/h2>

4.1 三種遍歷二叉樹

學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
2. 中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。
3. 后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

以下是分別堆前序遍歷、中序遍歷、后序遍歷的詳細(xì)剖析！



前序遍歷、中序遍歷、后序遍歷的代碼實(shí)現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;TreeNode* BuyTreeNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}TreeNode* CreateTree()
{TreeNode* node1 = BuyTreeNode(1);TreeNode* node2 = BuyTreeNode(2);TreeNode* node3 = BuyTreeNode(3);TreeNode* node4 = BuyTreeNode(4);TreeNode* node5 = BuyTreeNode(5);TreeNode* node6 = BuyTreeNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}void PrevOrder(TreeNode* root)//前序遍歷
{if (root == NULL){printf("N ");//空return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(TreeNode* root)//中序遍歷
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void AfterOrder(TreeNode* root)//后序遍歷
{if (root == NULL){printf("N ");return;}AfterOrder(root->left);AfterOrder(root->right);printf("%d ", root->data);
}int main()
{TreeNode* root = CreateTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");AfterOrder(root);printf("\n");return 0;
}

如圖所示，結(jié)果和我們上面寫的一樣！

4.2 求二叉樹節(jié)點(diǎn)的個(gè)數(shù)

錯(cuò)誤法:

修改：

最優(yōu)解：
也是遞歸思想

int TreeSize(TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) +TreeSize(root->right) + 1;//如果是空那么節(jié)點(diǎn)為0，否則就是左子樹的節(jié)點(diǎn)+右子樹的節(jié)點(diǎn)+1(根節(jié)點(diǎn))
}

4.3 求二叉樹葉子節(jié)點(diǎn)(度為0的節(jié)點(diǎn))的個(gè)數(shù)

int TreeLeafSize(TreeNode* root)//葉子節(jié)點(diǎn)的個(gè)數(shù)
{// 空 返回0if (root == NULL)return 0;// 不是空，是葉子 返回1if (root->left == NULL && root->right == NULL)return 1;// 不是空 也不是葉子  分治=左右子樹葉子之和return TreeLeafSize(root->left) +TreeLeafSize(root->right);
}

4.4 求二叉樹的高度

int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);//記錄數(shù)據(jù)int rightHeight = TreeHeight(root->right);//記錄數(shù)據(jù)return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

注意這里記錄數(shù)據(jù)很重要，如果不記錄數(shù)據(jù)直接使用三目的話，會導(dǎo)致效率低下。只知道誰大，不知道具體數(shù)值是多少,要輸出具體數(shù)值的時(shí)候要重新進(jìn)行計(jì)算，會大大降低效率！！！！

4.5 求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)

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

4.6 求二叉樹查找值為x的結(jié)點(diǎn)

錯(cuò)誤思想：

修改：

TreeNode* TreeFind(TreeNode* root, BTDataType x)// 二叉樹查找值為x的結(jié)點(diǎn)
{if (root == NULL)return NULL;if (root->data == x)return root;TreeNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;TreeNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

其依然是一個(gè)復(fù)雜的遞歸，不過這里有記錄了，返回也不是直接返回到最外面，而是返回到上一層遞歸！

4.7 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹

這樣構(gòu)建一棵樹非常低效，我們可以利用前序遍歷的值，直接構(gòu)建好一棵樹，這樣效率大大提升！

TreeNode* TreeCreate(char* a, int* pi)// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
{if (a[*pi] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreate(a, pi);root->right = TreeCreate(a, pi);return root;
}

這同樣也是一個(gè)遞歸構(gòu)建樹的思路！

4.8 銷毀鏈?zhǔn)蕉鏄?/h3>

void DestroyTree(TreeNode* root)
{if (root == NULL)return;DestroyTree(root->left);DestroyTree(root->right);free(root);
}

摧毀二叉樹用的是后序遍歷的思想，從底層開始銷毀!
摧毀后置空！

4.9 層序遍歷

層序遍歷就是一層一層的讀數(shù)據(jù)！具體過程如下：

但是層序遍歷的本質(zhì)是一個(gè)隊(duì)列，我們要實(shí)現(xiàn)需要隊(duì)列的代碼，之前我介紹過隊(duì)列，文章鏈接如下：
鏈接: C語言數(shù)據(jù)結(jié)構(gòu)-----棧和隊(duì)列(概念，代碼實(shí)現(xiàn)及簡單練習(xí))

void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;//每一層的數(shù)據(jù)個(gè)數(shù)，控制一層一層出while (!QueueEmpty(&q)){// 一層一層出while (levelSize--){TreeNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");levelSize = QueueSize(&q);//讀取每一層的數(shù)據(jù)個(gè)數(shù)}printf("\n");QueueDestroy(&q);
}

4.10 判斷是否為完全二叉樹

// 判斷二叉樹是否是完全二叉樹
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面還有非空就不是完全二叉樹while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}