当前位置: 首页 > news >正文

数据结构—基础知识(13):树的存储结构

数据结构—基础知识(13):树的存储结构

  1. 双亲表示法

    这种表示方法中,以一组连续的存储单元存储树的结点,每个结点除了数据域data外,还附设一个parent域用以指示其双亲结点的位置。
    在这里插入图片描述

    这种存储结构利用了每个结点(除根结点外)只有唯一的双亲性质。这种存储结构下,求结点的双亲十分方便,也很容易求树的根,但求结点的孩子时需要遍历整个结构

  2. 孩子表示法

    由于树中每个结点可能有多棵子树,则可用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有如下图的两种结点格式。
    在这里插入图片描述

    若采用第一种结点格式,则多重链表中的结点是同构的,其中d为树的度。由于树中很多结点的度小于 d,所以链表中有很多空链域,空间较浪费,不难推出,在一棵有n个结点度为k的树中必有n(k-1)+1 个空链域

    若采用第二种结点格式,则多重链表中的结点是不同构的,其中d为结点的度,degree 域的值同d。此时,虽能节约存储空间,但操作不方便

    另一种办法是,把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表做存储结构,则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构。

    下图(a)所示为下图中的树的孩子表示法。与双亲表示法相反,孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来,即将双亲表示和孩子链表合在一起。图(b)所示的就是这种存储结构的一例,它和图(a)表示的是同一棵树。
    在这里插入图片描述

  3. 孩子兄弟法

    孩子兄弟法又称二叉树表示法,或者二叉链表表示法,即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点(firstchild)和下一个兄弟结点(nextsibling)

    //------树的二叉链表(孩子—兄弟)存储表示------
    typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;
    }CSNode,*CSTree;
    

在这里插入图片描述

相关文章:

数据结构—基础知识(13):树的存储结构

数据结构—基础知识(13):树的存储结构 双亲表示法 这种表示方法中,以一组连续的存储单元存储树的结点,每个结点除了数据域data外,还附设一个parent域用以指示其双亲结点的位置。 这种存储结构利用了每个结…...

【Python爬虫入门到精通】小白也能看懂的知识要点与学习路线

文章目录 1. 写在前面2. 爬虫行业情况3. 学习路线 【作者主页】:吴秋霖 【作者介绍】:Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力于Python与爬虫领域研究与开发工作! 【作者推荐】:对JS逆向感兴趣的朋友可以关…...

服务器数据恢复—EVA存储raid5硬盘离线的数据恢复案例

服务器数据恢复环境: 某品牌EVA某型号存储,底层是RAID5阵列,划分了若干lun。 服务器故障&分析: 该存储设备中raid5阵列有两块硬盘掉线,存储中的lun丢失。 将故障服务器存储中的所有磁盘编号后取出,硬件…...

MAMBA论文疑被拒收,计算机科学顶会评审遭质疑

2023 年底,卡内基梅隆和普林斯顿大学计算机系的两位年轻科学家(Albert Gu, Tri Dao)联合推出一种叫做“Mamba”的大语言模型(LLM)新构架。与Transformers等传统模型相比,Mamba能够更有效地处理长序列。它利…...

EHS管理系统为何需要物联网的加持?

EHS是Environment、Health、Safety的缩写,是从欧美企业引进的管理体系,在国外也被称为HSE。EHS是指健康、安全与环境一体化的管理。 而在国内,整个EHS市场一共被分成三类; 一类是EHS管培体系,由专门的EHS机构去为公司…...

记事本(父页面与iframe子页面的联通,vue3+ts展示fbx模型,与tga贴图)

vue3ts 展示fbx与tga贴图 npm i three --save <template><div ref"modelContainer"></div> </template><script setup lang"ts"> import { ref, onMounted } from vue; import * as THREE from three; import { FBXLoader…...

【好书推荐-第五期】《互联网大厂推荐算法实战》(异步图书出品)

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号&#xff1a;程序员洲洲。 &#x1f388; 本文专栏&#xff1a;本文…...

C++ Qt day2

自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c; 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() #include <io…...

Mac上如何设置映射某个网站站点域名的IP

最近某常用的站点换 IP 了&#xff0c;但是 DNS 服务器还没有修改&#xff0c;这就导致无法访问&#xff08;换 DNS 服务器也不行&#xff09;。在用了一段时间的 IP 访问之后&#xff0c;还是没好&#xff0c;不知道是 DNS 污染还是咋了&#xff0c;所以最后还是手动改一下吧。…...

智能分析网关V4智慧冶金工厂视频智能监管方案

一、背景与需求 随着工业4.0的推进&#xff0c;冶金行业正面临着转型升级的压力。为了提高生产效率、降低能耗、保障安全&#xff0c;冶金智能工厂视频监管方案应运而生。该方案通过高清摄像头、智能分析技术、大数据处理等手段&#xff0c;对工厂进行全方位、实时监控&#xf…...

WebSocket实现HTML+SpringBoot聊天功能,小程序+SpringBoot聊天功能

目录 一、认识WebSocket 二、HTML实现聊天 三、微信小程序实现聊天 一、认识WebSocket 1.首先博主在初学Java时自我感觉走了很多弯路&#xff0c;因为以前见识短&#xff0c;在接触聊天功能时根本就没能想到有WebSocket这个聊天框架&#xff0c;就只能用底层的UDP或TCP实现聊…...

SpringMVC-RESTFul

文章目录 RESTFul一、基础概念二、增删改查1.查询全部用户信息 &#xff08;GET&#xff09;2.根据id查询用户信息3.添加用户&#xff08;POST&#xff09;4.修改用户 &#xff08;PUT&#xff09;5.删除用户 &#xff08;DELETE&#xff09; RESTFul 一、基础概念 二、增删改…...

Spring Boot3整合knife4j(swagger3)

目录 1.前置条件 2.导依赖 3.配置 1.前置条件 已经初始化好一个spring boot项目且版本为3X&#xff0c;项目可正常启动。 作者版本为3.2.2 初始化教程&#xff1a; 新版idea创建spring boot项目-CSDN博客https://blog.csdn.net/qq_62262918/article/details/135785412?…...

解决Windows系统本地端口被占用

目录 一、被程序占用端口 1.通过终端杀掉占用端口的进程 2.任务管理器 二、被系统列为保留端口 前言&#xff1a; 首先了解为什么会出现端口被占用的情况 端口被占用的情况可能出现的原因有很多&#xff0c;主要有以下几点&#xff1a; 1.多个应用程序同时启动&…...

GPS位置虚拟软件 AnyGo mac激活版

AnyGo for Mac是一款一键将iPhone的GPS位置更改为任何位置的强大软件&#xff01;使用AnyGo在其iOS或Android设备上改变其GPS位置&#xff0c;并在任何想要的地方显示自己的位置。这对那些需要测试应用程序、游戏或其他依赖于地理位置信息的应用程序的开发人员来说非常有用&…...

视频号视频怎么使用视频号下载助手提取视频呢?

微信视频号怎么使用视频下载助手提取视频&#xff0c;今天就和大家一起来看看我是如何操作的。 关于视频下载助手&#xff0c;给大家准备好了。获取方式在文末。注意看下关键词&#xff0c;家人们。 微信视频号是微信平台上的一个短视频分享功能&#xff0c;类似于抖音、快手这…...

第一篇【传奇开心果短博文系列】鸿蒙开发技术点案例示例:从helloworld开始理解鸿蒙开发ArkTS编程思路

传奇开心果短博文系列 系列短博文目录鸿蒙开发技术点案例示例系列 短博文目录一、前言二、初步解读鸿蒙的helloworld三、进一步深入解读理解 系列短博文目录 鸿蒙开发技术点案例示例系列 短博文目录 一、前言 从掰碎了揉烂了详细注释解读helloworld开始&#xff0c;理解Ark…...

四、MySQL之DML DQL

有关数据表的DML操作 INSERT 针对于数据的插入DELETE 针对于数据的删除UPDATE 针对于数据的修改 4.1 INSERT语句 INSERT INTO 表名 [(列名1,列名2,....)] VALUES (值1&#xff0c;值2&#xff0c;...); 默认情况下&#xff0c;一条插入命令只针对一行进行影响INSERT INTO 表…...

YOLOv8优化策略:注意力涨点系列篇 | 多尺度双视觉Dualattention | Dual-ViT,顶刊TPAMI 2023

🚀🚀🚀本文改进:多尺度双视觉Dualattention注意yolo,提升小目标检测能力 🚀🚀🚀YOLOv8改进专栏:http://t.csdnimg.cn/hGhVK 学姐带你学习YOLOv8,从入门到创新,轻轻松松搞定科研; 1.原理介绍 论文:Dual Vision Transformer | IEEE Journals & Magazine …...

视频渲染靠cpu还是显卡 会声会影视频渲染的作用是什么

视频渲染最占用的资源就是CPU&#xff0c;多核心多线程&#xff0c;这样才能渲染快。渲染可以在时间线上实时平滑预览&#xff0c;便于编辑&#xff0c;最终导出成片的时候速度也会快一些&#xff0c;渲染就是对每桢的图像进行重新优化的过程。 渲染的作用主要是能够保证使用者…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...