【数据结构】——树(Tree)的介绍和堆的实现

树 堆一、什么是树二、树的相关术语三、树的分类四、树的表示五、二叉树的介绍1.概念结构2.特殊二叉树2.1 满二叉树2.2 完全二叉树3.遍历方法4.二叉树的存储结构4.1 顺序存储4.2 链式存储5. 二叉树存储方式总结六、堆6.1 堆的定义6.2 堆的实现6.2.1 堆的结构6.2.2 堆的初始化——void HPInit(HP* php)6.2.3 堆的插入数据入堆——void HPPush(HP* php)6.2.4 堆的删除数据出堆——void HPPop(HP* php)6.2.5 取堆顶——HPDataType HPTop(HP* php)6.2.6 堆的销毁——void HPInit(HP* php)一、什么是树树是非线性数据结构由一组具有层次关系的节点组成不像链表、数组是一维线性结构。类比现实中的大树根在上、枝叶向下计算机树根节点在最上层子节点往下延伸。核心特点1.且仅有一个根节点最顶层无父节点2.除根外每个节点有且只有一个父节点3.任意节点向下延伸可以分出若干子节点4.不存在环不能绕一圈回到自身。5.子树是不相交的6.一棵由N个结点的树有N-1条边二、树的相关术语⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点。⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点。eg:A是B C D E的父节点/双亲结点。B C D E是A的孩子结点/子节点结点的度⼀个结点有⼏个孩⼦他的度就是多少eg:A结点的度为4B结点的度为2C结点的度为1…叶⼦结点/终端结点度为0的结点称为叶结点eg:这棵树的叶子结点有F G H I J K兄弟结点具有相同⽗结点的结点互称为兄弟结点(亲兄弟)eg: B C D E四个结点互为兄弟结点F G互为兄弟结点…树的度⼀棵树中最⼤的结点的度称为树的度。eg:这棵树的度为4结点的层次从根开始定义起根为第1 层根的⼦结点为第2层以此类推树的⾼度或深度树中结点的最⼤层次eg:这棵树的高度/深度为3结点的祖先从根到该结点所经分⽀上的所有结点eg:A是所有结点的祖先路径从一个节点走到另一个节点的节点序列eg:A-G的路径A-B-G…森林由mm0 棵互不相交的树的集合称为森林三、树的分类3.1 普通树多叉树每个节点可以有任意多个子节点。上面举的例子就是普通树3.2 二叉树每个节点最多只能有 2 个子节点分左孩子、右孩子顺序不能互换左子树左边子节点右子树右边子节点四、树的表示常用孩子兄弟表示法每个节点固定 2 个指针1.firstchild第一个左孩子即长子结点2.rightsib指向右侧的的兄弟结点structCSNode{intdata;structCSNode*firstchild;// 长子structCSNode*rightsib;// 右兄弟};五、二叉树的介绍1.概念结构1.1二叉树是每个节点最多拥有 2 个子节点的树形结构严格区分左子树、右子树左右不能互换。五种基本形态空树、只有根、只有左孩子、只有右孩子、左右孩子都有。1.2二叉树的特点1二叉树不存在度大于2的结点2二叉树的有左右之分次序不能颠倒二叉树是有序树空树空的二叉树没有根结点只有根结点的也是二叉树1.3二叉树的性质一 棵二叉树的深度为 h节点总数 为n则可知第 i 层最多有2^(i-1)个节点。深度 h 的二叉树最多有 2^k - 1 个节点n0n21叶子节点数 度为 2 节点数 1完全二叉树编号为 i的节点其父节点编号为i/2向下取整其左孩子编号为2i其右孩子编号为2i12.特殊二叉树2.1 满二叉树⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀个⼆叉树的层数为k且结点总数是2^k-1则它就是满⼆叉树。第k层有2^(k-1个结点2.2 完全二叉树完全⼆叉树是效率很⾼的数据结构完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的有n个结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。特点1.除了最后一层每层节点的个数达到最大2.最后一层个数不一定达到最大最后一层结点个数达到最大那么这个二叉树即使完全二叉树也是满二叉树3.结点从左到右依次排序性质若规定根结点的层数为1具有n个结点的满⼆叉树的深度(h log2(n1)以2为底n1 为对数)3.遍历方法以根节点访问顺序区分3.1 前序遍历先根遍历根左右访问当前根节点遍历左子树遍历右子树步骤演示根 A访问 A遍历 A 左子树 B根 B访问 BB 左 D访问 DD 无孩子返回B 右 E访问 EE 无孩子返回遍历 A 右子树 C根 C访问 CC 左 F访问 F无孩子C 右 G访问 G上述图前序遍历的结果为A B D E C F G3.2 中序遍历左 根 右执行逻辑递归遍历左子树访问当前根节点递归遍历右子树中序遍历结果D B E A F C G3.3 后序遍历左 右 根执行逻辑递归遍历左子树递归遍历右子树访问当前根节点后序遍历结果D E B F G C A3.4 层序遍历从上到下、从左到右借助队列实现层序遍历结果A B C D E F G4.二叉树的存储结构二叉树一般有两种存储结构顺序存储和链式存储4.1 顺序存储顺序存储底层结构是数组适用场景仅适合完全二叉树 / 满二叉树普通二叉树会大量浪费数组空间。存储规则数组下标从 1 开始方便计算父子关系设当前节点下标为 i父节点下标i/2向下取整左孩子2i右孩子2i1空位表示无节点示例4.2 链式存储链式结构底层结构为链表⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。5. 二叉树存储方式总结为了更清晰地展示二叉树的不同存储方式及其适用场景我们可以用以下思维导图进行归纳二叉树存储方式链式存储:任意二叉树通用二叉链表data, left, right三叉链表data, left, right, parent顺序存储数组普通完全二叉树:无大小规则:仅层序存放堆:完全二叉树 父子数值大小约束大根堆大顶堆:任意父节点 ≥ 子节点小根堆小顶堆:任意父节点 ≤ 子节点要点解析链式存储通过指针引用连接节点是最通用、最灵活的存储方式可以表示任意形态的二叉树。根据指针数量可分为二叉链表左、右孩子指针和三叉链表增加指向父节点的指针。顺序存储使用数组按层序存放节点。这种方式仅适用于完全二叉树包括满二叉树否则会浪费大量数组空间。它又可分为两类普通完全二叉树仅满足完全二叉树的结构特性层序、从左到右节点间没有数值大小约束。堆在完全二叉树的基础上增加了父子节点间的数值大小约束大根堆或小根堆是一种特殊的、高效的顺序存储应用。通过此图可以直观看出选择存储方式时首先要判断二叉树是否为完全二叉树。如果是则可以考虑高效的顺序存储尤其是堆如果不是则应使用链式存储。六、堆6.1 堆的定义堆是特殊的完全二叉树只能用数组顺序存储所以堆必须是完全二叉树分类大根堆大顶堆任意父节点 ≥ 左右孩子堆顶数组第一个元素是整个序列最大值小根堆小顶堆任意父节点 ≤ 左右孩子堆顶是整个序列最小值堆的节点编号为了在堆的实现中节省空间贴合编程语言数组特性方便代码实现堆的编号一般不像前面从1 开始而是从0开始所以堆的编号有以下特点对于具有n个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号则对于序号为i的结点有若i0i位置结点的双亲序号i-1/2若i0i为根结点编号若2i1n 左孩⼦序号2i1 2i1n 否则⽆左孩⼦若2i2n 右孩⼦序号2i2 2i2n 否则⽆右孩⼦6.2 堆的实现以小堆为例6.2.1 堆的结构堆是完全二叉树采用顺序存储结构所以堆的底层结构为数组所以堆的结构定义为数组表示数组的有效个数大小的size,数组的空间容量//堆的结构——顺序存储底层结构为数组typedefintHPDataType;typedefstructHeap{HPDataType*arr;//底层结构intsize;//有效数据的个数intcapacity;//空间容量}HP;和栈的结构定义相似。6.2.2 堆的初始化——void HPInit(HP* php)有了堆的结构定义之后就可以创建堆了同时不要忘记对堆结构成员进行初始化操作。调用堆的初始化函数时实参传过去的是堆的地址所以形参在接受时应当用一级指针//堆的初始化voidHPInit(HP*php){php-arrNULL;php-capacityphp-size0;}6.2.3 堆的插入数据入堆——void HPPush(HP* php)由于堆是一个完全二叉树完全二叉树的插入数据就是根结点往根节点的左子树插根节点的右子树插左子树的左子树插左子树的右子树插右子树的左子树插右子树的右子树插…放在堆的底层结构——数组中看就是向数组的最后一个元素后面插入数据。插入数据之前要判断是否有足够的空间可以插入数据有的话直接插入更新size。没有的话扩容更新capacity 和arr的地址再插入更新size。当sizecapacity时就需要扩容扩容用realloc来实现堆是由大堆和小堆的分类的所以在插入完数据之后要进行判断插入之后的逻辑结构是否满足大堆或者是小堆的定义不满足需要调整这个调整方法就是向上调整法以小堆为例向上调整法void AdjustUp(HPDataType* arr, int child)参数说明需要得到要调整的堆的地址即底层数组的地址还需要得到插入数据的编号也是数组下标child用来计算双亲结点的编号也是数组下标进行调整什么时候需要向上调整当孩子结点的值小于双亲结点的值时需要进行调整因为以小堆为例【大堆的话调整条件与小堆 相反其他不变】调整是将孩子结点的值与双亲结点的值互换但这只是向上调整了一次当堆有多层时需要将上述步骤重复所以需要while循环循环条件是child0向上调整的代码voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向上调整法voidAdjustUp(HPDataType*arr,intchild){//求双亲结点intparent(child-1)/2;while(child0){//大堆// if (arr[child] arr[parent])//小堆if(arr[child]arr[parent]){//调整,即交换孩子结点和双亲结点Swap(arr[child],arr[parent]);//更新child和parentchildparent;parent(child-1)/2;}else{//满足小堆的结构不用调整break;}}}堆的插入数据的完整代码voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向上调整法voidAdjustUp(HPDataType*arr,intchild){//求双亲结点intparent(child-1)/2;while(child0){//大堆// if (arr[child] arr[parent])//小堆if(arr[child]arr[parent]){//调整,即交换孩子结点和双亲结点Swap(arr[child],arr[parent]);//更新child和parentchildparent;parent(child-1)/2;}else{//满足小堆的结构不用调整break;}}}//堆的插入数据voidHPPush(HP*php,HPDataType x){assert(php);//判断空间是否足够if(php-sizephp-capacity){//扩容intnewcapacityphp-capacity0?4:2*php-capacity;HPDataType*tmp(HPDataType*)realloc(php-arr,newcapacity*sizeof(HPDataType));//判断扩容是否成功if(tmpNULL){perror(realloc fail!);exit(1);}//扩容成功更新capacity,和arr空间的地址php-arrtmp;php-capacitynewcapacity;}//空间足够php-arr[php-size]x;//向上调整AdjustUp(php-arr,php-size);php-size;}6.2.4 堆的删除数据出堆——void HPPop(HP* php)出堆在堆的结构里面删除数据只能操作堆顶为了保持其他结点的关系不变最小程度的修改原来堆的关系我们一般直接将最后一个元素与第一个元素交换之后进行向下调整以小堆为例的向下调整法voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向下调整voidAdjustDown(HPDataType*arr,intparent,intn){intchildparent*21;while(childn){//判断左右孩子的大小// 大堆if (child1narr[child] arr[child 1]);//小堆child1不能越界if(child1narr[child]arr[child1]){childchild1;}//孩子结点与双亲结点的比较//大堆arr[child] arr[parent]//小堆if(arr[child]arr[parent]){//调整Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}//堆的删除数据voidHPPop(HP*php){assert(!HPEmpty(php));//交换Swap(php-arr[0],php-arr[php-size-1]);--php-size;//向下调整AdjustDown(php-arr,0,php-size);}堆的删除操作的完整代码//判断堆是否为空boolHPEmpty(HP*php){assert(php);returnphp-size0;}//向下调整voidAdjustDown(HPDataType*arr,intparent,intn){intchildparent*21;while(childn){//判断左右孩子的大小// 大堆if (child1narr[child] arr[child 1]);//小堆child1不能越界if(child1narr[child]arr[child1]){childchild1;}//孩子结点与双亲结点的比较//大堆arr[child] arr[parent]//小堆if(arr[child]arr[parent]){//调整Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}//堆的删除数据voidHPPop(HP*php){assert(!HPEmpty(php));//交换Swap(php-arr[0],php-arr[php-size-1]);--php-size;//向下调整AdjustDown(php-arr,0,php-size);}6.2.5 取堆顶——HPDataType HPTop(HP* php)堆顶元素就是数组下标为0的元素取堆顶取出的值是最值//取堆顶数据HPDataTypeHPTop(HP*php){assert(!HPEmpty(php));returnphp-arr[0];}6.2.6 堆的销毁——void HPInit(HP* php)//堆的销毁voidHPDestory(HP*php){//判断arr是否为空为空就不需要free了if(php-arr)free(php-arr);//销毁之后还原结构体成员的值php-arrNULL;php-sizephp-capacity0;}