当前位置: 首页 > 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…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...