当前位置：首页 > news >正文

非线性表之堆的实际应用和二叉树的遍历

news 来源：原创 2024/9/21 8:31:50

前言：前一篇我已经介绍过了二叉树和堆的介绍和相关代码的实现

一、堆的实现

1.1堆向上调整算法

1.2堆向下调整算法

二、堆的应用

2.1堆的排序

2.2TOP-K问题

三、二叉树的遍历

3.1 二叉树的创建

3.2遍历介绍

3.3前序遍历

3.4中序遍历

3.5后序遍历

四、二叉树的其他求法

4.1求二叉树的结点个数

4.2求二叉树的深度/高度

4.3求二叉树的第k层节点个数

五、结尾

前言：前一篇我已经介绍过了二叉树和堆的介绍和相关代码的实现

非线性链表之树结构和堆的代码实现-CSDN博客

一、堆的实现

1.1堆向上调整算法

使用堆的向上调整算法的前提是：在插入新元素之前，前面的元素就已经满足了堆的性质！！

堆的向上调整(heapify up)算法的思想是:

1.将新元素插入到叶子节点。

2.与父节点进行比较。

3.如果新元素的值大于父节点的值,则需要进行交换。将新元素看作父节点,重复上述过程。使

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void HPAdjustPush(int* a, int child)
{assert(a);int father = (child - 1) / 2;while (child > 0){if (a[father] < a[child]){swap(&a[father], &a[child]);child = father;father = (child - 1) / 2;}else{return;}}
}

1.2堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以

把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void HPAdjustdown(int* a, int father,int sz)
{assert(a);int child = father * 2 + 1;while (child < sz){if (child + 1 < sz && a[child] < a[child + 1]){child++;}if (a[father] < a[child]){swap(&a[father], &a[child]);father = child;child = father * 2 + 1;}else{return;}}
}

二、堆的应用

2.1堆的排序

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

1. 建堆升序：建大堆降序：建小堆

2. 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以

完成堆排序。

代码实现

#define _CRT_SECURE_NO_WARNINGS 1#include<assert.h>
#include<stdio.h>void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void HPAdjustPush(int* a, int child)
{assert(a);int father = (child - 1) / 2;while (child > 0){if (a[father] < a[child]){swap(&a[father], &a[child]);child = father;father = (child - 1) / 2;}else{return;}}
}void HPAdjustdown(int* a, int father,int sz)
{assert(a);int child = father * 2 + 1;while (child < sz){if (child + 1 < sz && a[child] < a[child + 1]){child++;}if (a[father] < a[child]){swap(&a[father], &a[child]);father = child;child = father * 2 + 1;}else{return;}}
}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);}
}

2.2TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

代码实现


typedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//从从后往前的第一个非叶子节点开始向下调整
void AdjustDown(int* arr, int N, int parent)
{int child = parent * 2 + 1;//这里假设左孩子为小的/大的一个while (child < N){//假设这里建小堆//假设有右孩子并且如果右孩子比左孩子小的if (child + 1 < N && arr[child + 1] < arr[child]){child++;}//如果孩子比双亲小，则将双亲和孩子交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else //当孩子比双亲大时，则不需要调整了{break;}}
}void TopK(int* arr, int n, int k)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}//定义一个变量end记录堆最后一个元素int end = n - 1;//取前k个最值for (int i = end; i < k; i--){//将堆顶与比它大的数交换，必依次比较到n-kif (*(arr+end) < *arr){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);}}for (int i = 0; i < k; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{int n = 10000;srand((unsigned int)time(0));int* arr = (int*)malloc(sizeof(int) * n);if (arr == NULL){perror("malloc fail");return;}for (int i = 0; i < n; i++){arr[i] = rand() % 1000000 + 5;}//最大/*arr[100] = 1000001;arr[500] = 1000002;arr[1000] = 1000003;arr[5555] = 1000004;arr[9999] = 1000005;*///最小arr[100] = 1;arr[500] = 2;arr[1000] = 3;arr[5555] = 4;arr[9999] = 5;TopK(arr, n, 5);return 0;
}

三、二叉树的遍历

要想遍历二叉树，首先我手动创建一个二叉树

3.1 二叉树的创建

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

3.2遍历介绍

学习二叉树结构，最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

上述二叉图遍历结果

前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 2 5 6 4 1