| 【数据结构】树以及堆的讲解 | 您所在的位置：网站首页 › 矩阵树图和树图的区别是什么 › 【数据结构】树以及堆的讲解 |
【数据结构】树以及堆的讲解
|
(这里写自定义目录标题) 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言一、树的概念？二、树的表示方法三、树的实际应用四、二叉树概念以及结构1.概念2.特殊的二叉树3.二叉树的性质4.二叉树的存储结构5.引入堆的概念以及结构6.堆的实现以及堆排序7.时间复杂度问题8.TPopk问题 总结 前言树形结构是一种非线性的数据结构，其应用非常广泛，由树形结构可以引申出二叉树、堆等等的特殊树。 学习树对我们今后的工作帮助非常大。 一、树的概念？树是一种非线性的数据结构，它是n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它根朝上，而叶朝下。简单来讲就是–>树+人类亲缘关系描述 **- 根结点：没有父结点，且为所有结点的祖先的结点，如上图的A 节点的度：一个节点含有的子树个数称为该节点的度，如上图：A-6、D-1、E-2叶子节点：度为0的结点，如上图的B、C分支节点：度不为0的结点，如上图的D、E、F父节点：一个节点含有子节点的节点，称为父节点，如：A为B、C、D、E的父节点子节点：一个节点有父节点的节点称为子节点，如：B、C、D、E为A的子节点兄弟节点：具有相同父节点的节点，如：I、J的父节点都为E，则I和J为兄弟节点树的度：一棵树中，最大的节点度，如上图：树的度为6节点的层次：从根节点开始算，根为1，依次往下计算树的高度或深度：树的节点最大层，如上图：4堂兄弟：处于同一层，但又不是兄弟节点的节点节点的祖先：从根节点到所经分支上的所有节点子孙：以某节点为根的子树中任一节点都称为该节点的子孙，如：所有节点都是A的子孙森林：由多棵不相交的数组成** 二、树的表示方法树的存储表示既要保存值域，也要保存节点和节点之间的关系，实际中树的表示方法有很多种，如：双亲表示法、孩子表示法等等，但我们最常用的还是孩子兄弟表示法。
一棵二叉树是结点的一个有限集合，构成二叉树有规定： 1.一定是由一个根节点加上两棵左子树和右子树组成 2.二叉树不存在大于2的节点 3.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 2.特殊的二叉树 满二叉树 每一层的节点数都达到最大值，则称这个二叉树为满二叉树，就是说，如果一个二叉树层数为h，且节点总数为2^h-1，则为满二叉树  2.完全二叉树  完全二叉树为(最后一层-1）层必须为满节点，最后一层可以没有分支节点，若有，则需要有序。 注意：满二叉树是一种特殊的完全二叉树 
3.二叉树的性质
3.1 如何计算高度为h的节点个数？  父子间下标关系： 
5.引入堆的概念以及结构
1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的，因为会浪费大量的空间，而往往在现实中，我们会把堆（一种二叉树）使用顺序结构的数组进行存储。 2.堆 2.1、是一种完全二叉树。 2.2、大堆：树中任何一个父亲都大于或等于孩子 核心算法： 6.1 向上调整算法 前提：是一个堆 6.2 向下调整算法 前提：左右子树是一个堆 向上调整建堆： 什么是TPopk问题？ TPopk问题是堆的应用之一，其是要实现N个数中找出最大/最小数的前K个. 实现方法： 1.用于简单场景，如N的值不大的情况 2.用于复杂场景，如N的值太大的情况 #include #include #include void Swap(int* child,int* father) { int tmp = *child; *child = *father; *father = tmp; } void AdjustDown(int* a,int k,int father) { int child = (father * 2) + 1; while (child child++; } if (a[child] break; } } } void AdjustDownC(int* a,int k) { for (int i = (k-1-1)/2; i >=0; i--) { AdjustDown(a,k,i); } } void PrintTopK(int* a,int n,int k) { //1.将前K个数建堆 AdjustDownC(a,k); //2.将N-K的数，依次与堆顶元素比较 for (int i = k; i Swap(&a[0],&a[i]); AdjustDown(a,k,0); } } } void Topk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); if (a == NULL) { perror("malloc fail:"); return; } srand((unsigned int)time(0)); for (int i = 0; i printf("%d ", a[i]); } } int main() { Topk(); return 0; } 总结这就是我对堆的应用与理解，谢谢观看！ |
在实际应用中，树结构常常用于制作文件目录
3.2 如何计算二叉树的高度（h） 已知节点个数，求高度（h） N为节点个数 公式：(2^h)-1 = N ⇒ F(h) = log N+1;
小堆：树中任何一个父亲都小于或等于孩子 
向下调整建堆 
堆排序 
【本文地址】