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

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]]

相关文章:

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 --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…...

Spring事务管理与Spring AOP详解

Spring事务管理与Spring AOP详解 一、引言 在企业级应用开发中,事务管理和面向切面编程(AOP)是两个至关重要的概念。Spring框架作为Java企业级应用的首选框架之一,为事务管理和AOP提供了强大的支持。本文将详细解析Spring的事务…...

LaTeX 的使用

文章目录 TeX 编辑器文档类型中文编译文档结构preamble 导言区(不能放正文内容)document body 正文区 正文内容目录段落列表无序列表有序列表 图片表格交叉引用段落图片表格 转义符 数学公式数学符号行内公式行间公式有公式计数器无公式计数器 公式包含文…...

Text2SQL之Vanna优化

文章目录 前言一、优化方向二、干就完了一次性生成多个Question-SQL对先生成一个问题,再根据DDL和业务数据生成SQL总结前言 前阵子写了篇Text2SQL的简单介绍,发现其也是RAG只会,写下了Text2SQL之不装了,我也是RAG 最近也一直在做Text2SQL的优化,于是把自己的一些心得,总…...

船舶行业信息安全解决方案介绍

船舶行业信息安全背景: 近年来随着经济复苏、疫情与国际形势影响国内外船舶海运业务蓬勃发展,在业务量激增的背景下出现多类信息安全事件。其中2017年,马士基集团遭到勒索软件攻击,内部业务系统和码头操作系统均受到严重影响&…...

Typora—适用于 Mac 和 Win 系统的优秀 Markdown 文本编辑器

Typora 是一款适用于 Mac 和 Win 系统的优秀 Markdown 文本编辑器,它以其简洁易用的界面和强大的功能受到了众多用户的喜爱。 首先,Typora 的界面设计非常简洁直观,没有过多繁杂的菜单和按钮,让用户能够专注于写作本身。它采用实时…...

产品经理的未来在哪里?

【同学聚会】 医生说:你生病的话可以找我。 老师说:你孩子成绩不好时找你辅导。 律师说:你遇上官司时我帮你。 程序员说:你电脑坏了时我帮你修理。 产品经理说:我……好像无一技之长。(瞬间开始怀疑人…...

火车头采集怎么使用GPT等AI原创文章

火车头采集官方并没有GPT、百度文心一言AI、阿里通义千问AI、Kimi大模型等AI功能,但支持接入插件,可以编写相应人工智能AI原创文章插件(火车头采集支持PHP和c#这2种语言的插件编写),或者导入第三方封装好的GPT等AI原创…...

多元多项式的特征列与零点的关系定理

下面这个定理来自《计算机代数》6.1三角列与特征列(王东明、夏壁灿著) 【定理】 设 C [ C 1 , … , C r ] \mathbb{C }\left\lbrack C_{1},\ldots,C_{r} \right\rbrack C[C1​,…,Cr​]为多项式组 P ⊂ K [ x ] \mathbb{P \subset}\mathcal{K\lbrack}\…...

git - LFS 使用方法

安装Git LFS 访问 Git LFS官网 下载适用于您操作系统的版本。 Linux用户,解压缩下载的.tar.gz文件,并通过终端运行安装脚本。 tar -xvf git-lfs-linux-amd64-vX.Y.Z.tar.gz cd git-lfs-X.Y.Z sudo ./install.sh 初始化Git LFS # 全局启用 git lfs i…...

提高磁盘可靠性的技术:保障数据安全的四大方法

目录 1. 第一级容错技术 磁盘镜像(Mirroring) 工作原理 RAID 1 工作原理 优点 缺点 适用场景 示例 2. 第二级容错技术 概述 RAID 5 RAID 6 优点 缺点 适用场景 3. 基于集群系统的容错技术 概述 Hadoop HDFS Ceph 优点 缺点 适用场…...

CesiumJS【Basic】- #006 浏览器控制台查看位置角度

文章目录 浏览器控制台查看位置角度1 目标 浏览器控制台查看位置角度 1 目标 浏览器控制台查看位置角度...

Mac 终端报错 zsh: command not found: brew 解决方案

Homebrew安装 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"安装成功后,在终端输入下面命令 brew -v如果成功输出brew版本,则安装成功 关闭终端重新打开终端,报错zsh: comm…...

详解 HBase 的常用 API

一、环境准备 创建一个 Maven 工程并引入依赖 <dependency><groupId>org.apache.hbase</groupId><artifactId>hbase-server</artifactId><version>1.3.1</version> </dependency> <dependency><groupId>org.apach…...

JSR303校验

校验的需求 前端请求后端接口传输参数&#xff0c;需要校验参数。 在controller中需要校验参数的合法性&#xff0c;包括&#xff1a;必填项校验、数据格式校验等在service中需要校验业务规则&#xff0c;比如&#xff1a;课程已经审核过了&#xff0c;所以提交失败。 servi…...

04 远程访问及控制

1、SSH远程管理 SSH是一种安全通道协议&#xff0c;主要用来实现字符界面的远程登录、远程复制等功能。 SSH协议对通信双方的数据传输进行了加密处理&#xff08;包括用户登陆时输入得用户口令&#xff09;。 终端&#xff1a;接收用户的指令 TTY终端不能远程&#xff0c;它…...

[晕事]今天做了件晕事38 shell里的source 点号

今天碰到一个问题脚本里使用点号引入某个文件形式如下&#xff1a; . /tmp/abc但是脚本运行出现错误&#xff0c;一开始还以为是/tmp没有可执行权限&#xff08;https://mzhan017.blog.csdn.net/article/details/112178736#t16&#xff09;&#xff0c;导致abc运行不了。 后来…...

java如何分割字符串

java要实现对字符串的分割&#xff0c;需要用到split语句 语法格式是 str.split(分隔符) 其中 str是字符串 示例代码如下 public class Stringsplit {public static void main(String[] args) {String a"蒸羊羔&#xff0c;蒸熊掌&#xff0c;蒸鹿尾&#xff0c;烧花…...

胡说八道(24.6.12)——数字电子技术以及Modelsim

上回书说到数电中的最常用的表达式——逻辑表达式(由布尔代数组成)以及常用的两种图表——真值表(真值表表示的是所有的输入可能的线性组合以及输出)和卡诺图(卡诺图则是一种化简工具&#xff0c;排除冗余项&#xff0c;合并可合并项)。 今天&#xff0c;先来看看昨天说的基本逻…...

【Android面试八股文】AsyncTask中的任务是串行的还是并行的

文章目录 串行执行并行执行示例代码串行执行(默认)并行执行总结AsyncTask 的任务执行方式可以是串行的,也可以是并行的,这取决于使用的执行器 ( Executor)。 串行执行 默认情况下,AsyncTask 使用的是 SERIAL_EXECUTOR,即任务按顺序一个接一个地执行。这意味着下一个任务…...

无人机RTMP推流EasyDSS直播平台推流成功,不显示直播按钮是什么原因?

互联网视频云平台/视频点播直播/视频推拉流EasyDSS支持HTTP、HLS、RTMP等播出协议&#xff0c;并且兼容多终端&#xff0c;如Windows、Android、iOS、Mac等。为了便于用户集成与二次开发&#xff0c;我们也提供了API接口供用户调用和集成。在无人机场景上&#xff0c;可以通过E…...

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

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

基于51单片机的音乐彩灯设计

基于51单片机的音乐彩灯设计 &#xff08;程序&#xff0b;原理图&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 由STC单片机ADC0809模块LM386功放模块喇叭音频接口发光二极管电源构成 1.通过音频线输入可以播放电脑、手机、MP3里面的音乐。 2.AD对音频…...

API接口设计的艺术:如何提升用户体验和系统性能

在数字时代&#xff0c;API接口的设计对于用户体验和系统性能有着至关重要的影响。良好的设计可以显著提升应用程序的响应速度、可靠性和易用性。以下是几个关键点&#xff0c;帮助改善API接口的设计&#xff1a; 1. 理解并定义清晰的要求 用户研究&#xff1a;与最终用户进行…...

韩兴国/姜勇团队在《Trends in Plant Science》发表植物根系氮素再分配的观点文章!

氮素是陆地生态系统中的关键限制性营养元素&#xff0c;通过生物固氮和土壤氮供应通常远低高等植物的氮需求。当土壤氮素供应无法充分满足植物茎叶生长需求时&#xff0c;植物会通过自身营养器官&#xff08;如根或根茎&#xff09;再分配来实现氮的内部循环和再利用。尽管植物…...

52.Python-web框架-Django - 多语言编译-fuzzy错误

目录 1.起因 2.原因 3.解决方法 3.1手动移除fuzzy标记 3.2重新生成po文件&#xff0c;并检查是否还存在fuzzy标记 3.3重新编译生成mo文件 1.起因 在Django的国际化和本地化过程中&#xff0c;当你发现某些字段仅显示msgid&#xff0c;而不显示msgstr时&#xff0c;可能是…...

Linux自旋锁

面对没有获取锁的现场&#xff0c;通常有两种处理方式。 互斥锁&#xff1a;堵塞自己&#xff0c;等待重新调度请求自旋锁&#xff1a;循环等待该锁是否已经释放 本文主要讲述自旋锁 自旋锁其实是一种很乐观的锁&#xff0c;他认为只要再等一下下锁便能释放&#xff0c;避免…...

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

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

go 定时任务

在 Go 语言中&#xff0c;可以使用内置的 time 包来实现定时任务。以下是一个简单的示例&#xff1a; go package main import ( "fmt" "time" ) func main() { timer : time.NewTimer(2 * time.Second) <-timer.C fmt.Println(…...

Java Character 类

Java Character 类 Character 类用于对单个字符进行操作。 Character 类在对象中包装一个基本类型 char 的值 char ch a;// Unicode 字符表示形式char uniChar \u039A; // 字符数组char[] charArray { a, b, c, d, e };然而&#xff0c;在实际开发过程中&#xff0c;我们经…...

网络推广培训课程4万/专业放心关键词优化参考价格

状态 element和pad都可以处于不同的状态。pad的状态与element的状态相关联&#xff0c;因此状态的设计主要围绕element的状态进行。 一个element可以有 4 种状态。NULL、READY、PAUSED和PLAYING。当一个element最初被实例化时&#xff0c;它处于 NULL 状态。 状态定义 NULL&…...

大连网站优化方案/广州网页制作

此时只需要在配置文件my.cnf中加入以下语句&#xff1a; default-storage-engineINNODB character-set-serverutf8 collation-serverutf8_general_ci 然后重启数据库 再次查看&#xff1a; 问题即可解决&#xff01;...

网站的转盘游戏怎么做/个人网站设计

知乎的水印是如何批量添加的&#xff1f;您想拥有这个本领吗&#xff1f;我在opencv论坛发现了这个趣图添加logo的方法&#xff0c;也许您正需要这个代码&#xff0c;那我就诚心分享下吧。如何删除结果图像中mainlogo.png周围的黑色边框?import cv2 import numpy as np import…...

北京市住房和建设委员会网站/东莞营销网站建设

http://pengranxiang.iteye.com/blog/848862 首先我们先介绍一下为什么要让 Apache 与 Tomcat 之间进行连接。事实上 Tomcat 本身已经提供了 HTTP 服务&#xff0c;该服务默认的端口是 8080&#xff0c;装好 tomcat 后通过 8080 端口可以直接使用 Tomcat 所运行的应用程序&…...

seo网站营销推广全程实例pdf/市场营销案例100例

总体来说vue引入第三方字体库不算什么难度&#xff0c;如果出错&#xff0c;很多情况下是我们没有注意到一些情况&#xff0c;比如类名冲突等等&#xff0c;导致达不到所需的效果。我们这里以阿里的IconFont图标库来一步步引入。1、添加所需的图标入库1.png2、图标库里的图标库…...

外贸wordpress主题/app推广平台排行榜

燕山大学计算机组成原理硕士研究生入学考试大纲 燕山大学计算机组成原理硕士研究生入学考试大纲 考研加油站收集整理 http://doc.xuehai.net《计算机组成原理 》考研复习教学大纲【指定教学参考书】&#xff1a;计算机组成原理&#xff1b;哈尔滨工业大学&#xff1a;唐朔飞编著…...