C语言数据结构-----二叉树(2)堆的深入理解及应用、链式二叉树的讲解及代码实现

前言

本篇文章讲述的内容有部分是上一节写过的。重复内容不会再进行说明，大家可以看上一节内容
链接: C语言数据结构-----二叉树(1)认识数、二叉树、堆及堆的代码实现

---

1.使用堆解决TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

#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){// 假设左孩子小，如果解设错了，更新一下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()//创建随机数文本
{// 造数据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;}// 建一个k个数小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}// 读取前k个，建小堆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.向下调整堆的时间复杂度与向上调整堆的时间复杂度对比

总体而言
①向下调整堆的时间复杂度为：O[N-log₂(N+1)]，当N足够大时，约等于O(N)

②向上调整堆的时间复杂度为：

3.堆排序问题

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

#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){// 假设左孩子小，如果解设错了，更新一下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)
{// 建大堆，向下调整// O(N*logN)/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*///建小堆，向上调整// 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.链式二叉树

4.1 三种遍历二叉树

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

以下是分别堆前序遍历、中序遍历、后序遍历的详细剖析！



前序遍历、中序遍历、后序遍历的代码实现：

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

如图所示，结果和我们上面写的一样！

4.2 求二叉树节点的个数

错误法:

修改：

最优解：
也是递归思想

int TreeSize(TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) +TreeSize(root->right) + 1;//如果是空那么节点为0，否则就是左子树的节点+右子树的节点+1(根节点)
}

4.3 求二叉树叶子节点(度为0的节点)的个数

int TreeLeafSize(TreeNode* root)//叶子节点的个数
{// 空 返回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);//记录数据int rightHeight = TreeHeight(root->right);//记录数据return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

注意这里记录数据很重要，如果不记录数据直接使用三目的话，会导致效率低下。只知道谁大，不知道具体数值是多少,要输出具体数值的时候要重新进行计算，会大大降低效率！！！！

4.5 求二叉树第K层的节点个数

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的结点

错误思想：

修改：

TreeNode* TreeFind(TreeNode* root, BTDataType x)// 二叉树查找值为x的结点
{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;
}

其依然是一个复杂的递归，不过这里有记录了，返回也不是直接返回到最外面，而是返回到上一层递归！

4.7 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

这样构建一棵树非常低效，我们可以利用前序遍历的值，直接构建好一棵树，这样效率大大提升！

TreeNode* TreeCreate(char* a, int* pi)// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
{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;
}

这同样也是一个递归构建树的思路！

4.8 销毁链式二叉树

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

摧毁二叉树用的是后序遍历的思想，从底层开始销毁!
摧毁后置空！

4.9 层序遍历

层序遍历就是一层一层的读数据！具体过程如下：

但是层序遍历的本质是一个队列，我们要实现需要队列的代码，之前我介绍过队列，文章链接如下：
链接: C语言数据结构-----栈和队列(概念，代码实现及简单练习)

void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;//每一层的数据个数，控制一层一层出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);//读取每一层的数据个数}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;
}