如何给网站做seo,云南新闻最新消息今天,企业运营管理案例分析,高端菜单设计制作要讲二叉树的概念#xff0c;就要先讲树的概念。 树是什么呢#xff1f; 树其实是一种储存数据的结构#xff0c;因为他的结构倒过来和生活中的树很相似所以才被称之为树。
这是一颗多叉树#xff0c;从最顶端的节点可以找到下边的几个节点#xff0c;下边的节点又可以找…要讲二叉树的概念就要先讲树的概念。 树是什么呢 树其实是一种储存数据的结构因为他的结构倒过来和生活中的树很相似所以才被称之为树。
这是一颗多叉树从最顶端的节点可以找到下边的几个节点下边的节点又可以找到他的下一级节点注意观察如下边的g h i节点他们返回上一级只有一条路径从最上边找到他也只有唯一的路径。 树的结构之间不可以交叉一个节点只能有一个爸爸节点但是一个爸爸可以有多个孩子。 联想一下这个结构是不是和我们windows下的文件夹很相似一个文件夹打开后可以找到很多文件夹从某个文件夹内找到另一个文件夹只有一条路径。 讲几个比较重要的概念。 节点的度一个节点含有的子树的个数即一个爸爸有几个孩子。 A的度为4B的度为2。
树的度一棵树里面所有节点中最大的节点的度为树的度 A的节点为2B的节点为3该树的度为3。 树的高度就是树的深度 父节点有孩子结点的节点上图ABC都为父节点 子节点上图除了A别的都可以称作子节点他们都有父节点 节点的祖先所有节点的祖宗即A 兄弟节点有相同的父节点的节点。F和G就不是相同的父节点就不是兄弟节点。但是他们的爸爸在同一层所以称为堂兄弟节点。、 多叉树的实现比较难搞每个节点要保存父节点还要保存他的兄弟节点 所以我们先来实现一些简单的树形结构二叉树。 二叉树 概念这棵树的每个节点的子节点最多只能有两个左孩子或者右孩子。 任意二叉树都由以下几种情况复合而成 特殊的二叉树
满二叉树一个二叉树如果他的每一层的节点数都达到最大值这棵树就是满二叉树如果该二叉树的层数为K总结点个数为2k -1。 例如 每个父亲节点都有两个孩子。
现实中的二叉树如图 是不是超级标准。 2完全二叉树 完全二叉树由满二叉树发展而来满二叉树是完全二叉树的一种如果一棵树有K个节点这些节点从左往右依次数都是连着的,假设这里有一棵完全二叉树节点个数为9。 只能4有左孩子后才能有右孩子同一层节点如果左边的节点没有两个儿子后边的节点都不能有孩子。 下边两棵树都不是完全二叉树。 二叉树的存储结构 1顺序结构 顺序结构用数组来存储但一般只适用于完全二叉树完全二叉树使用数组存储的话不会因为有些地方是空的会造成空间的浪费所以现实中只有用堆才会使用数组存储。 二叉树顺序存储在物理上是一个数组在逻辑上是一棵完全二叉树。 第二种是链式储存用链表表示一棵二叉树这种结构在数据结构高阶中才会用到我们不做仔细讲解。
普通二叉树是不适合用数组建堆的会造成大量的空间浪费但是完全二叉树不一样他的节点是挨个建立的我们接下来建堆就是用这种结构。 堆的概念 有一堆元素以顺序表按照完全二叉树的顺序将其储存起来堆有两种大堆和小堆。 大堆 all父节点大于子节点根节点的值最大这样的堆叫做大堆 如果根节点最小所有父节点的值小于子节点那这个堆被称为小堆。 堆的创建 给一个数组
a[5,6,2,8,9,4,7]这个数组在逻辑上是一棵完全二叉树但还不是一个堆。 想要将它变成一个大堆就要调整他的顺序。 首先我们会想到让根节点小于其子节点然而其子节点也必须小于自己的子节点所以想要让一棵树变为一个大堆就要让自己的子树也变成一个大堆。
建堆过程如图 用数组的方式存储但其逻辑上可以看作是一棵二叉树完全二叉树 这里的1234567是数组的下标 可以发现若知道一个子节点的下标为child其父节点的下标为child-1)/2。 知道一个父节点parent其左孩子节点的下标为parent21。右孩子的下标为parent22。 建堆的时间复杂度 向下调整法 向下调整法通过父节点的下标找左右孩子不断判断值的大小交换建堆。 代码如下
//向下调整
void AdjustDown(HeapStyle* a, int n, int parent)
{int child parent * 2 1;while (childn){//找出小的孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}为了容易计算且满二叉树是完全二叉树的一种为了化简过程就利用满二叉树来证明。 假设树的高度为n 第一层一个节点最多需要向下调整n-1层 第二层21个节点最多每个节点要调整h-2层 第三层有22个节点最多每个节点要调整h-3层 … 第h-1层2h-2个节点最多向下调整一层 建堆的时间复杂度为O(N)。 向上调整法建堆 第一层不需要调整 第二层21个节点每个节点最多需要向上调整1次。 第三层22个节点每个节点最多向上调整2次 … 第h-1层2h-2个节点最多每个节点向上调整h-2次。 第h层2h-1个节点每个节点最多向上调整h-1次。 不用算就可以得出向上调整的时间复杂度为O(N2)。 向上调整法通过孩子找父亲判断交换建堆 代码如下
//向上调整
void AdjustUp(HeapStyle* a, int child)//向上调整
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}建堆过程 通过上边的分析我们已经知道向下调整法相对于向上调整优势巨大所以在建堆的过程中使用向下调整法遍历数组的每个节点使用向下调整法建大堆上边的流程图可知如果从根节点开始建堆不能确保左子树和右子树是否为堆最后一层不需要调整从倒数第二层开始调整使其变为一个堆。
//找出小的孩子if (child 1 n a[child] a[child 1]){child;}找出该节点左右孩子中大的那个。
if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}如果小于就互换越小越往上所以建的是小堆将判断条件更改为大于号即建大堆。这里的大于号和小于号是建大堆还是建小堆的关键。 利用循环交换后将parent改为childchild也更新一次是因为更换过来的父节点有可能比该子树的子节点更小。 如图所示 给定一个数组a[k] for (int i (k - 2) / 2; i 0; --i)//这里要思考一下{AdjustDown(minheap, k, i);}从倒数第二层开始建堆即可k-1是数组最后一个函数要想知道其父节点下标要减一再除以2所以就变成了(k-2)/2。 堆排序 假设我们要排升序 建立一个大堆堆顶元素一定是最大的那个如果直接取出根节点那么我们建的堆将被破坏左子树和右子树可能就不再是大堆。 就像上图数组建堆后下标为01234的数字为4 6 5 7 7如果取出4剩余的6,5,7,7明显不再是一个堆我们又要重新建堆这样堆排序有什么优势可言时间复杂度就变为O(N2)。如何取出根节点又不破坏左子树和右子树的大堆状态呢 将堆顶元素与最后一个交换最大的数就到了数组最后边然后只需要对换过去的根节点向下调整即可。 代码如下
//向下调整
void AdjustDown(HeapStyle* a, int n, int parent)
{int child parent * 2 1;while (childn){//找出小的孩子if (child 1 n a[child] a[child 1])//找出左右子树大的那个{child;}if (a[child] a[parent])//建大堆大于就交换{swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void Heapsort(int* a, int n)//建大堆
{for (int i (n-2)/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 endn-1。a[end]为最后一个节点交换后传参为n-1向下调整就不再带最后一个节点玩了直到调整至第一个节点这样这个数组就有序了。 TOPK问题 TOPK问题在生活中常常出现就比如年级前几名饭店味道排名等等等等如何在一大地数据中找到前几名呢 如果我们建一个小堆那么堆顶节点即为整棵树最小的那个假设有10000个数据我们要找出其中的前10个我们就可以使用前十个元素建一个小堆然后再让剩下的元素与堆顶元素进行比较如果大于对顶元素就与对顶元素进行交换然后向下调整重新建出一个小堆这时堆顶元素会发生变化会变成一个新的堆中最小的数遍历完成之后队中剩下的元素即为这10000个数里面最小的那个。 创建一个数组向里面写入10000个随机数进行测试。 随机数的范围是32767如果我们创建100000个数据只会出现很多重复的数据所以我们就使用一万个数据测试一下数据。 代码如下
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include time.h
//int main()
//{
// printf(%d , RAND_MAX);
//
// return 0;
//}void swap(int* a, int* b)
{int swp 0;swp *a;*a *b;*b swp;
}
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){//找出小的孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * (n));srand(time(0));for (int i 0; i n; i){a[i] rand() % 10000;}a[5] 100000 1;a[6100] 100002;a[1007] 100003;a[8678] 888888;a[3459] 777777;int k 10;for (int i (k - 2) / 2; i 0; i--)//倒数第二层最后一个节点{AdjustDown(a, k, i);//传入下标}//以前k个数建堆完毕for (int i k 1; i n; i){if (a[i] a[0]){swap(a[i], a[0]);}AdjustDown(a, k, 0);}for (int i 0; i k; i){printf(%d , a[i]);}
}int main()
{TestTopk();return 0;
}为了测试方便我们修改了数组中的几个数值。 运行后如下 是不是小堆呢 答案是他就是个小堆这样一万个数据里的前10个最大的数据就找出来了。 然而10000个数据是不是有点太少了。 我们普通创建的数组存储在栈上malloc出的数组存放在堆里如果有很多很多数据就会占据很多时间我们可以考虑将这些数字存放在一个文件里然后利用相关的文件操作找出这些数字里最大得前几个。 向文件里写入数据
//创造数据
void CreatNData()
{int n 1000000;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() % 100000;//然而最大不过32767有很多重复数据得了fprintf(fin, %d\n, x);}int k 10;//PrintTopk(file, k);fclose(fin);
}创建完成之后可以打开修改修改数据然后在main函数里将创建数据的函数注释防止数据覆盖。 打开后直接就是一顿修改 那几个后边数字相同且贼大的就是修改的数据。
void PrintTopk(const char*file, int k)
{//1,建堆--用a中的前k个元素建堆FILE* fout fopen(file, 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]);}fclose(fout);
}逻辑和上边malloc出的数组找最大得前十个一样。建小堆找到小于根节点的数据就进行交换交换后再次进行向下调整。 要注意rand出的数据最大32767因为我们创建了一百万个数据所以如果不修改数据的话查找出来的都会是32767。 运行结果如图 是一个小堆 对顶元素在预料之中。这样Topk问题就解决啦。 这篇文章就讲解到这里如果有什么问题欢迎大家提出指正。
