【数据结构】穿梭在二叉树的时间隧道:顺序存储的实现

专栏引入

哈喽大家好,我是野生的编程萌新,首先感谢大家的观看。数据结构的学习者大多有这样的想法:数据结构很重要,一定要学好,但数据结构比较抽象,有些算法理解起来很困难,学的很累。我想让大家知道的是:数据结构非常有趣,很多算法是智慧的结晶,我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏,在这里我将把数据结构内容以有趣易懂的方式展现给大家。

1.二叉树的顺序存储结构 

之前我们谈过了树的存储结构,并且谈到了顺序存储结构对树这种一对多的关系结构实现起来还是比较困难的。但二叉树是一种特殊的树,由于二叉树的特殊性,使得它可以使用顺序存储结构来实现,二叉树的顺序存储结构就是使用一维数组存储二叉树中的节点,并且节点的存储位置,也就是数组的下标要能体现出来节点之间的逻辑关系,比如:双亲和孩子的关系、左孩子右兄弟的关系等。先来看看完全二叉树的顺序存储,就用下面这棵二叉树为例:

将这棵二叉树存入数组中,相应的下标对应其同样的位置,很多数据结构相关书籍上下标都是将0空置,从1开始存储,其实下标0的位置是否存放数据对堆的实现的难度没有影响,为了节省空间我对下标为0的位置进行了存储,如下图:

这下我们可以看出来完全二叉树的优越性了吧,由于它严格的定义,所以用顺序结构也可以表现出二叉树的结构来,当然对于一般的二叉树,尽管层序编号不能反映出来逻辑关系,但是可以将其按完全二叉树来编号,只不过,把不存在的节点设置为"NULL"而已,就像下面的图中,虚线部分表示不存在:

 

 

我们再考虑一种极端的情况:一颗深度为h的右斜树。它只有h个节点,却要分配2^{h}-1个存储单元空间,这显然是对存储空间的浪费,如下图所示:

 所以,二叉树的顺序存储结构一般只适用于完全二叉树。上一篇中我们提到了堆是一个特殊的完全二叉树,所以这篇我们就以堆为例子来实现二叉树的顺序存储。

2.堆

2.1堆的概念

堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子节点的值,称为大顶堆;或者每个结点的值都小于等于其左右孩子结点的值,称为小顶堆。如下图所示:

从堆的定义可以知道:根节点一定是堆中所有结点的最大(小)值 。在上一篇堆二叉树的性质介绍时,有一个性质还没和大家介绍,因为这个性质就仿佛是为堆量身定制的,所以我计划在介绍堆时再介绍它:

如果一棵有n个节点的完全二叉树(其深度为\left \lfloor \log_{2}n \right \rfloor+1)的节点按层序编号(从第一层到第\left \lfloor \log_{2}n \right \rfloor+1层,每层从左到右),对任一节点i(1≤i≤n)有:

  • 如果i=1,则节点i是二叉树的根,无双亲;如果i>1,则双亲是节点\left \lfloor i/2 \right \rfloor
  • 如果2i>n,则节点i没有左孩子(节点i为叶子节点),否则其左孩子是节点2i。
  • 如果2i+1>n,则节点i没有右孩子;否则其右孩子是节点2i+1。

在这个性质第二、三条,也就是说明下标i与2i和2i+1的双亲子女的关系:双亲结点=(子节点-1)/2。

2.2堆的实现

我们先来定义一下堆的结构:

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2.2.1堆的创建和销毁

堆的创建我们使用顺序存储来实现,所以它的创建和销毁的实现代码和顺序表的实现的相同。首先是堆的创建函数:

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

接着是堆的销毁函数:

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

2.2.2堆的向上调整

一说到调整我们肯定会对两个数据进行交换,我们先来写一个交换函数:

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

堆的向上调整是将一个元素插入到小堆时,调整堆的结构,使其满足小堆的性质过程。实现堆的向上调整的要先将元素插入到数组的最后一个位置(这一步我们在堆的插入操作中实现)。这时候我们就要比较插入元素和其双亲结点的大小关系,然后做出调整。这里我们可以用循环实现,用循环来实现比用递归实现的好处有:

  1. 空间开销:循环实现通常比递归实现需要更少的内存空间。递归函数会在每次调用时创建一个新的函数栈帧,而循环则只使用一个循环体内的局部变量。
  2. 性能:循环实现通常比递归实现具有更高的执行效率。递归函数在每次调用时都需要进行函数调用、参数传递和返回值处理等操作,而循环通过使用迭代变量和循环条件判断来控制流程,避免了递归带来的额外开销。

首先我们先将这个函数里面的判断条件先写好:

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

既然我们要用循环来实现,那么使用while()语句的循环条件是什么呢?最坏的情况就是将新插入的节点经过调整变成根节点,那条件是parent≥0吗?parent是不会小于0的,当parent=0时,插入的数据还要接着向上调整交换,此时child变为0,parent=(0-1)/2,我们计算出来的parent时-0.5,但是要取整,所以parent还是0,此时循环还是没结束,会再次进入循环,此时child==parent,经过判断语句会侥幸跳出循环,这样是不严谨的。我们将循环条件设为child大于0就可以完美解决这个问题。此时,这个向上调整的操作完整代码为:

void AdjustUp(HPDataType* 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;}}
}

2.3堆的插入 

 堆的插入操作和顺序表的插入操作相似,其具体步骤为:

  1. 首先,函数开始时先进行一些边界判断,确保堆的指针有效。
  2. 如果堆的当前元素数量等于堆的容量,即堆已满,需要进行动态扩容。这里使用realloc函数对堆的数组进行扩容,新的容量为原来容量的两倍。
  3. 将待插入的元素x放到堆数组的最后一个位置,并将堆的元素数量递增。
  4. 调用AdjustUp函数对刚插入的元素进行向上调整,保持堆的性质。

我们来实现一下这个操作:

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4堆的向下调整

堆的向上调整是为了让堆在插入数据时能够保持堆的性质,而堆的向下调整操作是在删除根节点后,为了维护堆的性质而进行的操作。该操作的目的是将新的根节点下沉到合适的位置,使得根节点的值不大于它的左右子节点的值。堆的向下调整具体步骤为:

  1. 初始化子节点的索引child,设为父节点的左孩子节点的索引,即parent*2+1。
  2. 进入一个循环,判断当前节点是否有左孩子节点,如果有则执行循环体。
  3. 在循环体内,先假设左孩子节点的值最小,将child设为左孩子节点的索引。
  4. 检查右孩子节点是否存在,即child+1<size,如果存在且右孩子节点的值小于左孩子节点的值,则将child更新为右孩子节点的索引。
  5. 检查当前节点的值是否大于最小的子节点的值,如果是,则交换当前节点和最小子节点的值,将当前节点的索引设为子节点的索引child,并更新子节点的索引为新的左孩子节点的索引child=parent*2+1。
  6. 如果当前节点的值不大于最小子节点的值,即a[child]>=a[parent],则跳出循环。
  7. 重复之前的步骤,直到当前节点没有左孩子节点为止。

我们来具体实现一下这个操作:

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小,如果解设错了,更新一下if (child+1 < size && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

 2.5堆的删除

堆的删除具体操作步骤为:

  1. 调用Swap函数来交换小堆根节点(php->a[0])和最后一个节点(php->a[php->size - 1])的值。这样就将要删除的根节点移到了最后一个位置。
  2. 将小堆的大小减1,即php->size--,表示删除了一个节点。
  3. 最后,调用AdjustDown函数来对小堆进行向下调整,以维护小堆的性质。这样就完成了小堆的删除操作。

我们来实现一下这个操作:

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/340862.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AI程序员来了,大批码农要失业

根据GitHub发布的《Octoverse 2021年度报告》&#xff0c;2021年中国有755万程序员&#xff0c;排名全球第二。 ChatGPT的出现&#xff0c;堪比在全球互联网行业点燃了一枚“核弹”&#xff0c;很多人都会担心“自己的工作会不会被AI取代”。 而2024年的AI进展速度如火箭般&am…

getway整合sentinel流控降级

3. 启动sentinel控制台增加流控规则&#xff1a; 根据API分组进行流控&#xff1a; 1.设置API分组&#xff1a; 2.根据API分组进行流控&#xff1a; 自定义统一异常处理&#xff1a; nginx负载配置&#xff1a;

vue-router 源码分析——2. router-link 组件是如何实现导航的

这是对vue-router 3 版本的源码分析。 本次分析会按以下方法进行&#xff1a; 按官网的使用文档顺序&#xff0c;围绕着某一功能点进行分析。这样不仅能学习优秀的项目源码&#xff0c;更能加深对项目的某个功能是如何实现的理解。这个对自己的技能提升&#xff0c;甚至面试时…

德人合科技——@天锐绿盾 | -文档透明加密系统

天锐绿盾文档透明加密系统是一种先进的数据安全解决方案&#xff0c;旨在保护企业和组织的敏感信息&#xff0c;防止未经授权的访问和泄漏。 PC地址&#xff1a; https://isite.baidu.com/site/wjz012xr/2eae091d-1b97-4276-90bc-6757c5dfedee 以下是该系统的一些关键特点和功…

【读书笔记】曼陀罗思考法

目录 1 起源2 路径示例——人生规划设计 3 分类3.1 扩展型“扩展型”曼陀罗——使用方法 3.2 围绕型 4 注意事项 1 起源 曼陀罗在梵文中意味着“圣地”&#xff0c;象征着宇宙的秩序和内心的神圣结构。 “曼陀罗思考法”&#xff0c;是由日本学者今泉浩晃发明的方法&#xff…

【计算机毕设】基于SpringBoot的中小企业设备管理系统设计与实现 - 源码免费(私信领取)

免费领取源码 &#xff5c; 项目完整可运行 &#xff5c; v&#xff1a;chengn7890 诚招源码校园代理&#xff01; 1. 研究目的 在中小企业中&#xff0c;设备管理是确保生产和运营效率的重要环节。传统的设备管理通常依赖于手工记录和人工管理&#xff0c;容易导致数据不准确、…

LLM的基础模型4:初识Embeddings

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调或者LLM背后的基础模型新阅读。而最新科技&#xff08;Mamba,xLSTM,KAN&#xff09;则提…

12-学生们参加各科测试的次数(高频 SQL 50 题基础版)

12-学生们参加各科测试的次数 -- 学生表中&#xff0c;id是唯一的&#xff0c;将他作为主表 -- CROSS JOIN产生了一个结果集&#xff0c;该结果集是两个关联表的行的乘积 -- 2行表,与3行表使用cross join,得到2*36行数据 select st.student_id, st.student_name,su.subject_na…

【软件测试】自动化测试如何管理测试数据

前言 在之前的自动化测试框架相关文章中&#xff0c;无论是接口自动化还是UI自动化&#xff0c;都谈及data模块和config模块&#xff0c;也就是测试数据和配置文件。 随着自动化用例的不断增加&#xff0c;需要维护的测试数据也会越来越多&#xff0c;维护成本越来越高&#…

【Transformer(7)】Transformer架构解析

一、Transformer结构图 从上图可以看到&#xff1a; Transformer结构主要由编码和解码两大部分组成&#xff1a; &#xff08;1&#xff09;输入- position embedding - patch embedding &#xff08;2&#xff09;编码器 多头注意力机制 Add & NormMLP Add & Norm &…

爪哇,我初窥门径

2017年3月&#xff0c;我大二下学期了。 虽说一直在学习&#xff0c;持续在解决学习中遇到的问题&#xff0c;但迷茫依旧。 对着黑框编程&#xff0c;还是不知道Java在现实工作中是用来干什么的。 说实话&#xff0c;真的挺枯燥无趣的。 逐渐&#xff0c;我开始意识到&#…

linux部署运维2——centos7.9离线安装部署涛思taos2.6时序数据库TDengine

在实际项目开发过程中&#xff0c;并非一直都使用关系型数据库&#xff0c;对于工业互联网类型的项目来说&#xff0c;时序型数据库也是很重要的一种&#xff0c;因此掌握时序数据库的安装配置也是必要的技能&#xff0c;不过对于有关系型数据库使用的开发工作者来说&#xff0…

基础数学内容重构(后缀0个数)

今天也是参加了一下宁波大学的校赛&#xff0c;其中有一道题是求后缀0的个数&#xff0c;题意是让我们求一下式子的后缀0个数&#xff1a; 看上去比较复杂&#xff0c;但是通过化简我们可以知道以上式子就是求&#xff08;n 1&#xff09;&#xff01;&#xff0c;这里化简的过…

windows上进行git初始化时报错:fatal: unknown write failure on standard output

一、报错描述 1、git init命令一般是在命令行&#xff0c;切换到项目的根目录后执行 2、如果是windows的系统&#xff0c;我们粘贴路径时&#xff0c;需要进行转义命令行才能识别&#xff0c; 也就是像我下面写的 D:\\Users\\...3、报错信息进行解读 一般情况下&#xff0c;…

2024年手机能做的赚钱软件有哪些?整理了八个手机能做的正规赚钱软件分享

在这个指尖滑动的时代&#xff0c;手机不仅仅是通讯工具&#xff0c;更是我们探索财富的钥匙。你是否曾幻想过&#xff0c;躺在沙发上&#xff0c;轻轻一滑&#xff0c;就能让钱包鼓起来&#xff1f; 今天&#xff0c;就让我们一起来探索那些隐藏在手机里的赚钱秘笈&#xff0c…

Apache OFBiz 路径遍历导致RCE漏洞复现(CVE-2024-36104)

0x01 产品简介 Apache OFBiz是一个电子商务平台,用于构建大中型企业级、跨平台、跨数据库、跨应用服务器的多层、分布式电子商务类应用系统。是美国阿帕奇(Apache)基金会的一套企业资源计划(ERP)系统。该系统提供了一整套基于Java的Web应用程序组件和工具。 0x02 漏洞概…

缓存方法返回值

1. 业务需求 前端用户查询数据时,数据查询缓慢耗费时间; 基于缓存中间件实现缓存方法返回值:实现流程用户第一次查询时在数据库查询,并将查询的返回值存储在缓存中间件中,在缓存有效期内前端用户再次查询时,从缓存中间件缓存获取 2. 基于Redis实现 参考1 2.1 简单实现 引入…

STM32 HAL库开发——入门篇(3):OLED、LCD

源自正点原子视频教程&#xff1a; 【正点原子】手把手教你学STM32 HAL库开发全集【真人出镜】STM32入门教学视频教程 单片机 嵌入式_哔哩哔哩_bilibili 一、OLED 二、内存保护&#xff08;MPU&#xff09;实验 2.1 内存保护单元 三、LCD 3.1 显示屏分类 3.2 LCD简介 3.3 LCD…

jpeg编码学习

正点原子stm32教程提到过jpeg解码库libjpeg&#xff0c;但是没有提到jpeg编码&#xff0c;我也好奇jpeg编码怎么实现&#xff0c;用代码怎么生成jpeg文件的。所以最近学习了jpeg编码&#xff0c;在这里做记录。 参考文章 jpeg图片格式详解 https://blog.csdn.net/yun_hen/art…

算法004:盛水最多的容器

这道题比较简单&#xff0c;使用双指针。 要求的是最大面积&#xff0c;对于一个水桶&#xff08;水杯来说&#xff09;&#xff0c;面积的算法是固定的&#xff0c;就是底乘以高。 在这个题中&#xff0c;我们把左边的位置设为left&#xff0c;右边的位置设为right&#xff…