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

数据结构-5.9.树的存储结构


一.树的逻辑结构:


二.双亲表示法(顺序存储):

1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点);

2.结点包括结点数据和指针;

3.上述图片中右边的顺序存储解析:比如A结点左边的0,就是在数组中的位置即第一个位置,A结点右边的-1代表没有双亲即没有父结点,结点C左边的2代表在数组中第3个位置,右边的0就是结点C的父结点即A结点在数组中的位置,其他同理;

4.上述图片中的代码解析:PTNode代表结点,结构体里的nodes数组是PTNode型,也就是结点的集合,构成了树,结构体PTNode里有结点的数据和指向双亲位置域的双亲指针,指针是int型(不是int *),因此指向的是双亲结点在数组中的位置下标;

5.基本操作:

a.增加结点:

上述图片增加一个结点M在结点H下,顺序存储在第12个位置即数组下标为11,结点M的父结点为H,结点H在数组中下标为7,因此结点M的结点指针parent为7:

此时数组中数据元素的排列顺序表面像是层序规则排列,但在插入新结点时并不需要遵守层序的规则即不需要同一层中必须先从最左边添加,然后依次添加到最右边,而是可以随意添加在某个结点下,比如再插入一个L结点在E结点下:

b.删除结点:

比如删除G结点,有两种方案:

方案一:把G结点的双亲指针改为-1(因为双亲指针的值就是对应结点的父结点在数组中的位置,此时G结点不存在了,即在该树中没有父结点,因此双亲指针可设为-1,是一个不存在的数组下标)

方案二:把尾部的数据即结点L里的数据移动到G结点的位置上,这样就保证数组里的每一个存储单元都是有效的(比方案一好)

注:删除结点后要把结点数减一,不是数组长度减一

刚才删除的G结点是叶子结点,如果删除的不是叶子结点,那么既然该结点被删除了,那么这个结点下面连着的所有结点即以该结点为根结点的树就都被删除了:如删除D结点,那么结点D,H,I,J,M就都被删除了,此时就涉及到查询除了根结点D外H,I,J,M在数组中的位置,然后更改双亲指针进行删除;

c.查询结点(查询到结点后也可以修改结点数据):

采用双亲表示法,找到父结点很容易,因为有双亲指针直接可以知道父结点在数组中的位置,

但如果找父结点的子结点,就只能从头到尾依次遍历,把每一个结点的双亲指针取出来,对比是否与父结点在数组中的下标相等,这也就暴露出删除结点中方案一是有些低效的,因为该方案中删除元素后会有双亲指针的无效数据,此时遍历数组时也会把这个无效数据一起遍历,降低了效率,因此删除结点中方案二较好,

6.回顾:二叉树的顺序存储(二叉树也是树,也可以用双亲表示法)


三.孩子表示法(顺序+链式存储结合):

1.核心:先利用顺序表开辟一个顺序存储空间即数组来存储各个结点里的数据,每个结点包含数据域和指向第一个子结点的指针

2.代码:

解析:结点CTBox结构体中存储数据和第一个孩子,链表struct CTNode中的各个结点其实只是保存了各个子结点的数组下标

对于上述代码呈现出的存储结构,可知找子结点很方便,但找双亲结点就较麻烦;


四.孩子兄弟表示法(链式存储):

1.代码:

解析:1.*firstchild指针可看作左指针,指向结点的第一个子结点(不一定叫左子结点,因为可能不是二叉树,但一定是第

一个结点),

*nextsibling指针可看作右指针,指向结点的第一个子结点的后面结点即右兄弟结点

(左孩子,不同层;右兄弟,同层)

(从物理上看,用孩子兄弟表示法保存的树形状上和二叉树一样,只不过左右指针的含义不同)

如根结点A(只有孩子没有同层的兄弟),结点A的*firstchild指针指向B结点,

由于B结点的右兄弟为C结点,所以结点B的 *nextsibling指针指向 C结点,

由于C结点的右兄弟为D结点,所以结点C的 *nextsibling指针指向D结点,

同理,结点B的第一个孩子为E结点,那么结点B的*firstchild指针指向E结点,

由于E结点的右兄弟为F结点,所以结点E的 *nextsibling指针指向 F结点,

结点E的第一个孩子为K结点,那么结点E的*firstchild指针指向K结点,

同理,结点C的第一个孩子为G结点,那么结点C的*firstchild指针指向G结点,

同理,结点D的第一个孩子为H结点,那么结点D的*firstchild指针指向H结点,

由于H结点的右兄弟为I结点,所以结点H的 *nextsibling指针指向 I结点,

由于I结点的右兄弟为J结点,所以结点I的 *nextsibling指针指向 J结点,

2.例如:二叉树转化为树

思路:要把二叉树看作是用二叉链表保存的树,左边的第一个结点是孩子,剩下的右边全是兄弟

首先A是根结点,A结点的左边第一个结点B为左孩子,可知在B的右边的结点C,F,L都是它的右兄弟,所以:

看以B为根结点的子树,D结点是B结点的左孩子,H结点连在D结点的右边,所以H结点是D结点的右兄弟,

同理,G结点是D结点的左孩子,后续同理,最终如下:


五.森林和二叉树的转换:

本质:用二叉树链表(孩子兄弟表示法)存储森林

核心:可以利用二叉链表的方式来存储森林,一个森林里有几个互不相交的树,首先把森林里的树都转换为二叉树,森林里的每一棵树在逻辑上看是平级的,因此可以把这些树的根结点看作兄弟结点,如果用二叉链表(孩子兄弟表示法)存储的话,右指针表示兄弟关系,因此可以把这些树的根结点用右指针连接起来:

例题:

把二叉树转换为森林:

思路:从根结点A出发,右边的结点C,F,L都是右兄弟,因此结点A,C,F,L是平级的兄弟关系,

因此结点A,C,F,L就是四棵互不相交的树的根结点,

对于A结点,第一个孩子为B结点,B结点没有右兄弟,C结点已经用了,这里无需处理C结点

对于B结点,第一个孩子为D结点,D结点没有右兄弟,

对于D结点,第一个孩子为G结点,D结点的右兄弟为H结点,因此B结点的右边连接H结点,

对于C结点,第一个孩子为E结点,F结点已经用了,这里无需处理F结点,

对于E结点,第一个孩子为I结点,E结点的右兄弟为J,因此C结点右边连接J结点,

对于F结点,第一个孩子为K结点,L结点已经用了,这里无需处理L结点,

对于L结点,左右没有连接任何东西,所以处理完毕:


六.总结:


相关文章:

数据结构-5.9.树的存储结构

一.树的逻辑结构: 二.双亲表示法(顺序存储): 1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点); 2.结点包括结点数据和指针; 3.上述图片中右边的顺序存储解析:比如A结点左边的0,就…...

【Linux】解锁线程基本概念和线程控制,步入多线程学习的大门

目录 1、线程初识 1.1线程的概念 1.2.关于线程和进程的进一步理解 1.3.线程的设计理念 1.4.进程vs线程(图解) 1.5地址空间的第四谈 2.线程的控制: 2.1.关于线程控制的前置知识 2.2创建线程的系统调用: 这个几号手册具体…...

uniapp学习(005-2 详解Part.2)

零基础入门uniapp Vue3组合式API版本到咸虾米壁纸项目实战,开发打包微信小程序、抖音小程序、H5、安卓APP客户端等 总时长 23:40:00 共116P 此文章包含第41p-第p47的内容 文章目录 mainifest.json文件配置获取微信小程序appid注册微信小程序微信小程序控制台图形界…...

深度学习的关键概念和术语

特征 特征是图像上可进行视觉辨识的区域。特征通常代表对应用相关的内容(缺陷、对象、对象的特定部分)。 特征尺寸 仅用于聚焦模式下的绿色分类、红色、蓝色定位和蓝色读取工具。 您认为对分析图像内容最重要的图像特征的主观大小。该特征尺寸确定用于…...

navicate可视化数据库操作-cnblog

1 连接数据库 点击链接,自定义名称,输入root密码 2 准备按照图例创建数据库demo 3 新建数据库...

kubernetes中的微服务

目录 一 什么是微服务 二 微服务的类型 三 ipvs模式 3.1 ipvs模式配置方式 四 微服务类型详解 4.1 clusterip 4.2 ClusterIP中的特殊模式headless 4.3 nodeport 4.4 loadbalancer 4.5 metalLB 4.6 externalname 五 Ingress-nginx 5.1 ingress-nginx功能 5.2 部署…...

Python 量子机器学习及其应用

Python 量子机器学习及其应用 目录 🌀 量子机器学习的基础概念💡 量子计算的原理与经典计算的区别🔑 量子算法在机器学习中的应用潜力⚛️ 量子计算与经典机器学习算法的结合🚀 案例展示:量子算法提升机器学习效率&a…...

echarts显示隐藏柱状图柱子的背景色

showBackground: true, //控制是否显示背景色backgroundStyle: {// color: rgba(180, 180, 180, 0.4) //背景色的颜色color: red} 关键代码是 showBackground: true, //控制是否显示背景色 设置为false或者直接而不写就是不显示背景色,默认是不显示背景色 true的时…...

QT文件操作【记事本】

mainwindow.h核心函数 QFileDialog::getOpenFileName()QFileDialog::getSaveFileName() #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include<QFileDialog> #include<QMessageBox> #include<QDebug> #include<QFile> #…...

Linux 定时备份系统日志

Linux 定时备份系统日志 SSH跨机免密登录复制备份到另一台虚机上开启定时任务 SSH跨机免密登录 定时备份首先要实现免登入 一、scp 一个文件从其他服务器到本机&#xff0c;怎么跳过ssh登录验证呢&#xff1f; 要在使用SCP时跳过密码登录&#xff0c;你可以设置SSH密钥认证。首…...

音视频入门基础:FLV专题(15)——Video Tag简介

一、引言 根据《video_file_format_spec_v10_1.pdf》第75页&#xff0c;如果某个Tag的Tag header中的TagType值为9&#xff0c;表示该Tag为Video Tag&#xff1a; 这时StreamID之后紧接着的就是VideoTagHeader&#xff0c;也就是说这时Tag header之后的就是VideoTagHeader&…...

尚硅谷rabbitmq2024 第15-18节 springboot整合与可靠性答疑

在spring boot项目中&#xff0c;只引入了一个amqp的starter&#xff0c;为什么在写listener的时候能看到rabbitmq相关的类&#xff0c;比如RabbitListener( public void processMessage(String dataString, Message message, channel channel){ 这里的Message就是rabbitmq下面…...

ctfshow-web 萌新题

给她 pyload: 1.dirsearch扫描&#xff0c;发现git 2. GitHack工具得到.git文件 <?php $passsprintf("and pass%s",addslashes($_GET[pass])); $sqlsprintf("select * from user where name%s $pass",addslashes($_GET[name])); ?>addslashes函…...

基于RPA+AI的网页自动填写机器人 | OPENAIGC开发者大赛高校组优秀作品

在第二届拯救者杯OPENAIGC开发者大赛中&#xff0c;涌现出一批技术突出、创意卓越的作品。为了让这些优秀项目被更多人看到&#xff0c;我们特意开设了优秀作品报道专栏&#xff0c;旨在展示其独特之处和开发者的精彩故事。 无论您是技术专家还是爱好者&#xff0c;希望能带给…...

Tmux常用操作--云GPU版

Tmux是什么&#xff0c;作用&#xff1f; Tmux是一个终端复用器&#xff08;terminal multiplexer&#xff09;&#xff0c;属于常用的开发工具。 作用 使用Tmux创建守护进程&#xff0c;可以使得关闭PyCharm或者其他终端的情况下&#xff0c;远程服务器&#xff08;云GPU&a…...

股市入门常见术语介绍

鉴于最近行情讨论火热&#xff0c;我也想借此平台&#xff0c;结合我大学时期身边同学老师的投资经历&#xff0c;写一篇交易入门术语简介。内容不多但是足以达到科普之用。 ​ 希望大家能谨慎对待投资&#xff0c;始终保持谦虚学习的态度。不要迷失在瞬息万变的金融市场&…...

专栏十九:单细胞大数据时代使用scvi和scanpy整合数据

慢更ing,主要是记录自己在分析中的一些困惑 一、基础知识和解惑 放在最前面,是因为scvi整合不像harmony,傻瓜式操作,很多地方还是要注意一下的。 1.如何正确的寻找HVGs 一般我们使用的函数就是scanpy.pp.highly_variable_genes,里面的参数较为复杂。 Q:输入数据的格…...

C语言编程必备知识

C语言是编程领域中基础且广泛使用的语言之一&#xff0c;掌握C语言编程需要一些核心知识&#xff0c;涵盖基本语法、内存管理、数据结构等方面。以下是C语言编程中的一些必备知识点&#xff1a; 1. **基础语法** - **变量声明**&#xff1a;所有变量都需要在使用前声明&…...

k8s 1.28 集群部署

文章目录 环境配置安装docker安装cri-dockerd(Docker与Kubernetes通信的中间程序)&#xff1a; 部署kubernetes 环境配置 关闭Selinux #永久 sed -i s/enforcing/disabled/ /etc/selinux/config #临时 setenforce 0 关闭Swap #临时 swapoff-a #永久 sed -ri s/.*swap.*/#&a…...

python入门教程

Python 是一种非常流行的编程语言&#xff0c;因其简单易学的语法和广泛的应用领域&#xff08;如数据分析、人工智能、Web 开发等&#xff09;而备受欢迎。以下是一个入门级 Python 教程&#xff0c;适合初学者快速掌握 Python 的基础知识。 1. 安装 Python 你可以从 Python…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

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…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...