二叉树的实现（上）：https://developer.aliyun.com/article/1389394
🪐代码总结
🌠Heap.h头文件
//包含头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> #include<time.h> #include<stdbool.h> //定义数据类型 typedef int HPDataType; //二叉树堆的实现 typedef struct Heap { //下一个节点 HPDataType* a; //元素个数 int size; //初始化个数 int capacity; }HP; //初始化 void HeapInit(HP* php); //建立二叉树 void HeapInitArray(HP* php, int* a, int n); //销毁 void HeapDestroy(HP* php); //实现交换元素的函数 void Swap(HPDataType* p1, HPDataType* p2); //实现向上调整建小堆 void AdjustUp(HPDataType* a, int child); //实现向下调整建大堆 void AdjustDown(HPDataType* a, int n, int parent); //打印元素 void HeapPrint(HP* php); //添加元素 void HeapPush(HP* php, HPDataType x); //删除元素（这里可以实现排序 （从小到大） ） void HeapPop(HP* php); //返回第一个元素 HPDataType HeapTop(HP* php); //判断不能没有元素 bool HeapEmpty(HP* php);
🌠Heap.c源文件
//包含头文件 #include"Heap.h" //初始化 void HeapInit(HP* php) { //断言 assert(php); //初始化 php->a = NULL; php->size = 0; php->capacity = 0; } //建立二叉树 void HeapInitArray(HP* php, int* a, int n) { //断言 assert(php); assert(a); //开辟空间 php->a = (HPDataType*)malloc(sizeof(HPDataType) * n); //判断 if (php->a == NULL) { perror("malloc fail"); exit(-1); } //赋值 php->size = n; php->capacity = n; //把a的元素拷贝的开辟的二叉树中 memcpy(php->a, a, sizeof(HPDataType) * n); // 建堆 for (int i = 1; i < n; i++) { //向上调整建小堆 实现取出最小的元素（后面会实现） AdjustUp(php->a, i); } } //销毁 void HeapDestroy(HP* php) { //断言 assert(php); //释放内存 free(php->a); php->a = NULL; php->size = php->capacity = 0; } //实现交换元素的函数 void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //实现向上调整建小堆 void AdjustUp(HPDataType* a, int child) { //父亲和孩子的关系 int parent = (child - 1) / 2; while (child > 0) { //实现向上调整元素 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } else { break; } } } //实现向下调整建大堆 void AdjustDown(HPDataType* a, int n, int parent) { //孩子和父亲的关系 int child = parent * 2 + 1; while (child < n) { //找出小的那个孩子 if (child + 1 < n && 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 HeapPrint(HP* php) { //断言 assert(php); for (size_t i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); } //添加元素 void HeapPush(HP* php, HPDataType x) { //断言 assert(php); //扩容（这里实现元素一个添加在堆中） //（需要主函数整个循环） if (php->size == php->capacity) { //实现扩容 int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; //开辟空间 HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); //判断 if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newCapacity; } php->a[php->size] = x; php->size++; //添加元素后实现向上调整 建成小堆 AdjustUp(php->a, php->size - 1); } //删除元素（这里可以实现排序 （从小到大） ） void HeapPop(HP* php) { //断言 assert(php); assert(php->size > 0); //第一个元素和最后一个元素交换 Swap(&php->a[0], &php->a[php->size - 1]); --php->size; //向下调整后 就可以剥离出最后一个元素实现排序（小到大） AdjustDown(php->a, php->size, 0); } //返回第一个元素 HPDataType HeapTop(HP* php) { //断言 assert(php); assert(php->size > 0); //返回第一个元素 return php->a[0]; } //判断不能没有元素 bool HeapEmpty(HP* php) { //断言 assert(php); // return php->size == 0; }
🌠Test.c源文件
//包含头文件 #include"Heap.h" //int main() //{ // //int a[] = { 65,100,70,32,50,60 }; // int a[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 }; // HP hp; // HeapInit(&hp); // for (int i = 0; i < sizeof(a)/sizeof(int); i++) // { // HeapPush(&hp, a[i]); // } // HeapPrint(&hp); // // int k = 5; // while (!HeapEmpty(&hp) && k--) // { // printf("%d ", HeapTop(&hp)); // HeapPop(&hp); // } // // HeapDestroy(&hp); // // return 0; //} // 这种写法的缺点： // 1、先有一个堆的数据结构 // 2、空间复杂度复杂度的消耗 //排序 //void HeapSort(int* a, int n) //{ // //创建指针 // HP hp; // //初始化 // HeapInit(&hp); // for (int i = 0; i < n; i++) // { // //添加元素 // HeapPush(&hp, a[i]); // } // int i = 0; // //不能没有元素 // while (!HeapEmpty(&hp)) // { // //返回第一个元素 // printf("%d ", HeapTop(&hp)); // a[i++] = HeapTop(&hp); // //删除元素（这里可以实现排序 （从小到大） ） // HeapPop(&hp); // } // //销毁 // HeapDestroy(&hp); //} //排序升序 //void HeapSort(int* a, int n) //{ // // 向上调整建堆 （大堆）or （小堆） // // 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); // } // // // O(N*logN) // int end = n - 1; // while (end > 0) // { // Swap(&a[0], &a[end]); // AdjustDown(a, end, 0); // --end; // } //} //int main() //{ // //int a[] = { 65,100,70,32,50,60 }; // //int a[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 }; // //int a[] = { 70, 65, 100, 32, 50, 60 }; // int a[] = { 2,3,5,7,4,6,8 }; // HeapSort(a, sizeof(a) / sizeof(int)); // // return 0; //}
💫拓展
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
💦1. 用数据集合中前K个元素来建堆
💧前k个最大的元素，则建小堆
💧前k个最小的元素，则建大堆
💦2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
方法实现：
//大量数据排序 void PrintTopK(const char* filename, int k) { // 1. 建堆--用a中前k个元素建堆 //打开文件 FILE* fout = fopen(filename, "r"); //判断是否打开文件 if (fout == NULL) { perror("fopen fail"); return; } //开辟空间 int* minheap = (int*)malloc(sizeof(int) * k); //判断 if (minheap == NULL) { perror("malloc fail"); return; } //存入数据 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); } // 前k个数建小堆 for (int i = (k - 2) / 2; i >= 0; --i) { AdjustDown(minheap, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 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"); //关闭文件 fclose(fout); } int main() { //创建数字 CreateNDate(); //实现寻找 PrintTopK("data.txt", 5); return 0; }
🌝二叉树的链表存储结构
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
💫初始化二叉树的链表存储结构
这里就简单的续写咯
//包含头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> // 不是增删查改，学习二叉树结构 typedef struct BinaryTreeNode { //左节点 struct BinaryTreeNode* left; //右节点 struct BinaryTreeNode* right; int val; }BTNode; //初始化 BTNode* BuyNode(int x) { //开辟空间 BTNode* node = (BTNode*)malloc(sizeof(BTNode)); //判断 if (node == NULL) { perror("malloc fail"); exit(-1); } //初始化 node->val = x; node->left = NULL; node->right = NULL; //返回值 return node; }
💫二叉树的遍历
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
💦1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
💦2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
💦3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
// 二叉树前序遍历 void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } // 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); } // 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); }
💫二叉树层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
不知道大家还记得队列不，这里可是需要用到哟。
// 层序遍历 void LevelOrder(BTNode* root) { Que q; //初始化 QueueInit(&q); if (root) //添加元素 QueuePush(&q, root); //判断 while (!QueueEmpty(&q)) { //找头 BTNode* front = QueueFront(&q); printf("%d ", front->val); if (front->left) //添加元素 QueuePush(&q, front->left); if (front->right) //添加元素 QueuePush(&q, front->right); //删除元素 QueuePop(&q); } printf("\n"); //销毁 QueueDestroy(&q); }
💫二叉树的节点个数以及高度等
// 二叉树节点个数(总节点个数) int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } // 叶子节点个数 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); } // 第k层的节点个数 int TreeKLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) { return 1; } return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } // 二叉树销毁 void TreeDestroy(BTNode* root) { if (root == NULL) { return; } TreeDestroy(root->left); TreeDestroy(root->right); free(root); //root = NULL; } // 二叉树查找值为x的结点 BTNode* TreeFind(BTNode* root, int x) { if (root == NULL) return NULL; if (root->val == x) return root; BTNode* ret = NULL; ret = TreeFind(root->left, x); if (ret) return ret; ret = TreeFind(root->right, x); if (ret) return ret; return NULL; }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
