05-5.4.1 树的存储结构

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com


喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏

树的逻辑结构回顾

[[5.1.1~2 树的定义和基本术语]]
[[5.2.2 二叉树的存储结构]]
如何实现树的顺序存储?
树:一个分支结点可以有多课子树
只依靠数组下标,无法反映结点之间的逻辑关系
思路:
用数组存顺序存储各个结点。每个结点中保存 数据元素、指向双亲结点(父结点)的“指针”

双亲表示法(顺序存储)

![[Pasted image 20240617204710.png]]

![[Pasted image 20240617204517.png]]

#define MAX_TREE_SIZE 100  // 树中最多结点数typedef struct{  // 树的结点定义ElemType data;  // 数据元素int parent;  // 双亲位置域
}PTNode;typedef struct{  // 树的类型定义PTNode nodes[MAX_TREE_SIZE];  // 双亲表示int n;  // 结点数
}PTree;

拓展:双亲表示法存储“森林”

森林是 m ( m ≥ 0 ) m(m \geq 0) m(m0) 棵互不相交的树的集合
![[Pasted image 20240617204640.png]]

双亲表示法的优缺点

  • 优点:找双亲(父结点)很方便
  • 缺点:找孩子不方便,只能从头到尾遍历整个数组
  • 适用场景:“找父亲”多,“找孩子”少。如:并查集

孩子表示法(顺序+链式存储)

![[Pasted image 20240617204926.png]]

孩子表示法:用数组顺序存储各个结点。每个结点中保存 数据元素、孩子链表头指针

// 链表结点中只需要保存孩子的编号以及指向下一个链表结点的指针
struct CTNode{int child; // 孩子结点在数组中的位置struct CTNode *next;  // 下一个孩子
};// 一个数组元素中包含数据元素data和一个链表的指针firstChild
typedef struct{ElemType data;struct CTNode *firstChild;  // 第一个孩子
} CTBox;// 用上面声明的结构体定义一个数组,在数组中存储结点的信息,同时还要记录这棵树中总共有多少个结点,以及根结点的下标是多少
typedef struct{CTBox nodes[MAX_TREE_SIZE];int n, r;  // 结点数和根的位置
} CTree;

用孩子表示法存储“森林”

在这里插入图片描述

用孩子表示法存储“森林”
需要记录多个根的位置

孩子表示法的优缺点

  • 优点:找孩子很方便
  • 缺点:找双亲结点很不方便
  • 适用场景:“找孩子”多,“找父亲”少。如:服务流程树

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

typedef struct CSNode{ElemType data;  // 数据域struct CSNode *firstChild. *nextsibling;  // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

与二叉树类似,采用 二叉链表 实现,每个结点中包含 数据元素两个指针,但这两个指针的含义与二叉树不同

孩子兄弟表示法存储“森林”

![[Pasted image 20240617210552.png]]

![[Pasted image 20240617210626.png]]

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

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

相关文章

经验分享,xps格式转成pdf格式

XPS 是一种电子文档格式、后台打印文件格式和页面描述语言。有时候微软默认打印机保存的是xps格式,我们如何转换为pdf格式呢,这里分享一个免费好用的网站,可以实现。 网站:https://xpstopdf.com/zh/ 截图:

JVM 三色标记算法

三色标记算法核心原理 三色标记算法是一种JVM的垃圾标记算法,CMS/G1垃圾回收器就是使用的这种算法,它可以让JVM在不发生或者尽可能短的发生STW(Stop The World)的情况下进行垃圾的标记和清除。 顾名思义,三色标记算法…

Linux(Centos7)OpenSSH漏洞修复,升级最新openssh-9.7p1

OpenSSH更新 一、OpenSSH漏洞二、安装zlib三、安装OpenSSL四、安装OpenSSH 一、OpenSSH漏洞 服务器被扫描出了漏洞需要修复,准备升级为最新openssh服务 1. 使用ssh -v查看本机ssh服务版本号 ssh -V虚拟机为OpenSSH7.4p1,现在准备升级为OpenSSH9.7p1…

springboot小型超市商品展销系统-计算机毕业设计源码01635

摘 要 科技进步的飞速发展引起人们日常生活的巨大变化,电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流,人类发展的历史正进入一个新时代。在现实运用中,应用软件的工作…

“暗蚊”黑产团伙通过国内下载站传播Mac远控木马攻击活动分析

黑客&网络安全如何 1 概述 近期,安天CERT发现一组利用非官方软件下载站进行投毒和攻击下游用户案例,并深入分析了攻击者在网管运维工具上捆绑植入macOS平台远控木马,利用国内非官方下载站发布,以此取得政企机构内部…

nvm 报错https://npm.taobao.org/mirrors/node/index.json 淘宝镜像更换

文章目录 一、问题背景二、解决问题1. 获取配置文件的位置2. 修改配置文件中的镜像源配置3. 修改 npm 镜像源 一、问题背景 使用nvm的时候报错: Could not retrieve https://npm.taobao.org/mirrors/node/index.json. 由于淘宝的镜像域名更换,npm.taobao.org 域名…

【PowerDesigner】创建和管理CDM之新建实体

目录 🌊1. PowerDesigner简介 🌍1.1 常用模型文件 🌍1.2 PowerDesigner使用环境 🌊2. 创建和管理CDM 🌍​​​​​​2.1 新建CDM 🌍2.2 新建实体 🌊3. 研究心得 🌊1. PowerDe…

qss实现登录界面美化

qss实现登录界面美化 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);// 去掉头部this->setWindowFlag(Qt::FramelessWindowHint);// 去掉空白部分th…

元数据:数据的罗塞塔石碑

在大数据时代,我们每天都在生成和处理海量数据。但数据本身,如果没有适当的上下文和描述,就像是一堆没有翻译的古老文字。这就是元数据发挥作用的地方——它是大数据世界的罗塞塔石碑,为我们提供了理解和利用数据的关键。 文章目录…

期末考试老师怎样发成绩

期末成绩的公布,总是让老师感到焦虑。成绩,这一张张的数字,承载着学生一学期的努力,也牵动着家长们的心。 传统的成绩公布方式,写成绩条让学生带回家,或是通过私发家长的方式,都存在一定的弊端。…

记录清除挖矿病毒 solrd 过程

1、发现solrd病毒 端午节期间,kafka 服务器被黑客攻击了,植入了挖矿病毒 solrd,这个病毒很聪明,内存,CPU并没有异常升高,以致于上班第一天完全没有察觉。 上班第一天 正常登录服务器查看 flink ,消费kafka…

云和运维(SRE)的半生缘-深读实证02

这个标题不算太夸张,云计算和很多IT岗位都有缘,但是和运维(SRE)岗位的缘分最深。 “深读实证”系列文章都会结合一些外部事件,点明分析《云计算行业进阶指南》书中的内容。本次分享介绍了下列内容: 我以运维…

ctfshow web 单身杯

web签到 <?phperror_reporting(0); highlight_file(__FILE__);$file $_POST[file];if(isset($file)){if(strrev($file)$file){ //翻转函数include $file;}}要进行反转并且包含文件用data协议 自己写不好写可以用函数帮你翻转 <?php $adata:text/plain,<?eval(…

Cisco Packet Tracer实验(五)不同vlan间的通信简单配置

1&#xff0e;单臂路由(图) 环境&#xff1a;一台路由器&#xff0c;一台二层交换机&#xff0c;两台pc机 单臂路由&#xff08;Single Arm Routing&#xff09;是指在网络架构中&#xff0c;只有一个物理接口&#xff08;单臂&#xff09;连接到路由器三层交换机&#xff0c;而…

大数据分析-二手车用户数据可视化分析

项目背景 在当今的大数据时代&#xff0c;数据可视化扮演着至关重要的角色。随着信息的爆炸式增长&#xff0c;我们面临着前所未有的数据挑战。这些数据可能来自社交媒体、商业交易、科学研究、医疗记录等各个领域&#xff0c;它们庞大而复杂&#xff0c;难以通过传统的数据处…

【漏洞复现】飞企互联-FE企业运营管理平台 treeXml.jsp SQL注入漏洞

0x01 产品简介 飞企互联-FE企业运营管理平台是一个基于云计算、智能化、大数据、物联网、移动互联网等技术支撑的云工作台。这个平台可以连接人、链接端、联通内外&#xff0c;支持企业B2B、C2B与020等核心需求&#xff0c;为不同行业客户的互联网转型提供支持。其特色在于提供…

eclipse如何导入springboot项目

打开eclipse 找到你的springboot项目 点击finish即可 test02就已经导入进去了 配置一下maven 在将那个springboot项目刷新一下即可 运行成功

怎么把网页上的接口信息导入postman

第一步 打开f12&#xff0c;右键选中需要的接口。选择copy-copy as cURL 第二步 打开postman&#xff0c;选择"Raw Text"&#xff0c; 把刚才复制的curl粘贴到空白位置&#xff0c;点击Continue - 最后的效果。导入的接口自带cookie&#xff0c;不用再输入cookie&a…

服务器----阿里云服务器重启或关机,远程连接进不去,个人博客无法打开

问题描述 在使用阿里云免费的新加坡服务器时&#xff0c;发现重启或者是关机在开服务器后&#xff0c;就会出现远程连接不上、个人博客访问不了等问题 解决方法 进入救援模式连接主机&#xff0c;用户名是root&#xff0c;密码是自己设置的 点击访问博客查看更多内容

【Linux】进程_7

文章目录 五、进程8. 进程地址空间9. 进程终止10. 进程等待 未完待续 五、进程 8. 进程地址空间 我们上节知道了进程地址空间是根据页表来使虚拟地址转换成内存中的物理地址&#xff0c;那这种 地址空间 页表 的机制有什么好处呢&#xff1f;①这种机制可以将物理内存从无序…