广告联盟怎么做,优化建议,wordpress 当前页码,失效网站建设费支出目录
前言#xff1a;前一篇我已经介绍过了二叉树和堆的介绍和相关代码的实现
一、堆的实现
1.1堆向上调整算法
1.2堆向下调整算法
二、堆的应用 2.1堆的排序 2.2TOP-K问题
三、二叉树的遍历
3.1 二叉树的创建 3.2遍历介绍
3.3前序遍历
3.4中序遍历
3.5后序遍历
…目录
前言前一篇我已经介绍过了二叉树和堆的介绍和相关代码的实现
一、堆的实现
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#includeassert.h
#includestdio.hvoid 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 (*(arrend) *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 二叉树的创建
#includestdio.h
#includeassert.h
#includestdlib.htypedef 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
3.3前序遍历
void PreOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}//前序遍历 根 左子树 右子树printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
3.4中序遍历
void InOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}//中序遍历 左子树 根 右子树InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
3.5后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}//后序遍历 左子树 右子树 根PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
四、二叉树的其他求法 以下解法所用的是递归法 4.1求二叉树的结点个数
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
4.2求二叉树的深度/高度
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}
4.3求二叉树的第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);
}
五、结尾
如果有什么建议和疑问或是有什么错误希望大家可以在评论区提一下。 希望大家以后也能和我一起进步 如果这篇文章对你有用的话希望能给我一个小小的赞
