【C 数据结构】树

文章目录

  • 【 1. 基本原理 】
    • 1.1 子树、空树
    • 1.2 有序数、无序树
    • 1.3 森林
  • 【 2. 结点 】
  • 【 3. 度、层次、深度 】

【 1. 基本原理 】

  • 树结构是一种 非线性存储结构,存储的是具有 一对多 关系的数据元素的集合。
  • 一对多
    如下图中的左图所示,对于数据 A 来说,和数据 B、C、D 有关系;对于数据 B 来说,和 E、F 有关系。这就是“一对多”的关系。
    在这里插入图片描述
  • 将具有“一对多”关系的集合中的数据元素按照上面右图的形式进行存储,整个存储形状在逻辑结构上看,类似于实际生活中倒着的树(左图倒过来),所以称这种存储结构为 树型存储结构
  • 树的广义表 表示法
    上图用广义表可以表示为:
    (A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )

1.1 子树、空树

  • 子树:上图中,整棵树的根结点为结点 A,而如果单看结点 B、E、F、K、L 组成的部分来说,也是棵树,而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树;同样,结点 E、K、L 构成的也是一棵子树,根结点为 E。
    单个结点也是一棵树,根结点就是它本身。上图中的结点 K、L、F 等都是树,且都是整棵树的子树。
    知道了子树的概念后,树可以这样定义:树是由根结点和若干棵子树构成的
  • 在树结构中, 对于具有同一个根结点的各个子树,相互之间不能有交集
    例如上图中,除了根结点 A,其余元素又各自构成了三个子树,根结点分别为 B、C、D,这三个子树相互之间没有相同的结点。如果有,就破坏了树的结构,不能算做是一棵树。
  • 空树:如果集合本身为空,那么构成的树就被称为空树。 空树中没有结点

1.2 有序数、无序树

  • 如果树中结点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为 有序树;反之称为 无序树
    在有序树中,一个结点最左边的子树称为 第一个孩子 ,最右边的称为 最后一个孩子
    例如上图中,如果其本身是一棵有序树,则以结点 B 为根结点的子树为整棵树的第一个孩子,以结点 D 为根结点的子树为整棵树的最后一个孩子。

1.3 森林

  • 由 m(m >= 0)个互不相交的树组成的集合被称为 森林 。例如上图中,分别以 B、C、D 为根结点的三棵子树就可以称为森林。
  • 前面讲到,树可以理解为是由根结点和若干子树构成的,而这若干子树本身是一个森林,所以,树还可以理解为是由根结点和森林组成的。用一个式子表示为:Tree =(root,F),其中,root 表示树的根结点,F 表示由 m(m >= 0)棵树组成的森林。
    除了上图表示树的方法外,还有其他表示方法:

【 2. 结点 】

  • 结点:使用树结构存储的每一个数据元素都被称为结点。例如,上图中的数据元素 A 就是一个结点;
  • 父结点(双亲结点)子结点兄弟结点
    对于上图中的结点 A、B、C、D 来说,A 是 B、C、D 结点的父结点(也称为“双亲结点”);B、C、D 都是 A 结点的子结点(也称“孩子结点”);
    对于 B、C、D 来说,它们都有相同的父结点,所以它们互为兄弟结点。
  • 树根结点(根结点):每一个非空树都有且只有一个被称为根的结点。上图中的结点 A 就是整棵树的根结点。
    树根的判断依据为: 如果一个结点没有父结点,那么这个结点就是整棵树的根结点
  • 叶子结点:如果结点没有任何子结点,那么此结点称为叶子结点(叶结点)。例如上图中,结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。

【 3. 度、层次、深度 】

  • 对于一个结点, 拥有的子树的数量(结点有多少分支)称为结点的 度(Degree)。例如上图中,根结点 A 下分出了 3 个子树,所以,结点 A 的度为 3。
    一棵树的度 是树内各结点的度的最大值。例如上图中,各个结点的度的最大值为 3,所以,整棵树的度的值是 3。
  • 结点的层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。例如上图中,A 结点在第一层,B、C、D 为第二层,E、F、G、H、I、J 在第三层,K、L、M 在第四层。
  • 一棵树的 深度(高度)是树中结点所在的最大的层次。例如上图中树的深度为 4。
  • 如果两个结点的父结点虽不相同,但是它们的父结点处在同一层次上,那么这两个结点互为 堂兄弟。例如上图中,结点 G 和 E、F、H、I、J 的父结点都在第二层,所以之间为堂兄弟的关系。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【电子通识】什么是8D分析法?8D步骤及用法?

在问题分析时往往会听到8D报告这样的词汇。如在电源专题【电源专题】案例:电源芯片厂家怎么判断电源芯片端口是否损坏中我们使用的图片就来源于电源芯片厂家的8D报告。 什么是8D分析法? 8D问题分析由美国国防部于1974年创立,当时用于军用物资采购保障。目前在汽车产业、组装…

谷歌收录工具有什么好用的?

如果是想促进谷歌的收录,其实能用的手段无非就两个,谷歌GSC以及爬虫池 谷歌gsc就不用说了,作为谷歌官方提供的工具,他能提供最准确的数据,并且可以提交每天更新的链接,进而促进收录,只要你的页面…

ApiHug 的初心-ApiHug101

视频 秒懂 ApiHug -019 HOPE 🔥 H.O.P.E.: Help other people excellent 💝 是这个项目最初的初心 🤗 ApiHug {Postman|Swagger|Api...} 快↑ 准√ 省↓ 🏠 gitee github search ApiHug ApiHug 🤗 ApiHug {Post…

机器人模型匹配控制(MPC)MATLAB实现

模型匹配控制(Model matching control)是指设计一个控制器使闭环系统的传递函数tf(s)与td(s)相一致! mpcDesigner 可以分为: 2时域精确模型匹配控制3频域精确模型匹配控制 机械臂控制中应用模型匹配控制(Model Matc…

平衡二叉树(AVLTree)

AVLTree 1、树的分类2、平衡二叉树2.1、构建一个平衡二叉树2.2、删除节点2.3、搜索方式2.3.1、广度优先搜索(BFS)2.3.2、深度优先搜索(DFS) 1、树的分类 树形结构是编程当中特别常见的一种数据结构。比如电脑中的文件管理系统就大…

信息打点--公众号服务

微信公众号 获取微信公众号的途径https://weixin.sogou.com/ 微信公众号没有第三方服务 Github监控 人员&域名&邮箱 eg:xxx.cn password in:file https://gitee.com/ https://github.com/ https://www.huzhan.com/ 资源搜索 in:name test 仓库标题搜索含有…

C语言中字符串函数以及内存函数的使用和注意事项

目录 0. 前言 1、求字符串长度函数 1.1、strlen 模拟实现 2.长度不受限制的字符串函数 2.1 strcpy 模拟实现 2.2strcat 模拟实现 2.3strcmp 模拟实现 3.长度受限制的字符串函数 3.1strncpy 3.2strncat 3.3strncmp 4、字符串查找函数 4.1strstr 模拟实现 3.2strt…

修复版最新精仿熊猫办公PPT模板图片素材整站源码+WAP手机端+会员系统+火车头采集

修复版最新精仿熊猫办公PPT模板图片素材整站源码WAP手机端会员系统火车头,采用Empirecms7.5版UTF-8开发,是一款非常高端的ppt模板,图片素材下载站模板非常适合大型图库下载站,配有手机端模板,支持自定义设置会员组&…

面试官:在原生input上面使用v-model和组件上面使用有什么区别?

前言 还是上一篇面试官:来说说vue3是怎么处理内置的v-for、v-model等指令? 文章的那个粉丝,面试官接着问了他另外一个v-model的问题。 面试官:vue3的v-model都用过吧,来讲讲。 粉丝:v-model其实就是一个语…

python使用redis存储时序数据

import redisdef ts_demo():"""时序数据存储RedisTimeSeries测试"""# 连接到Redisr redis.Redis(hostlocalhost, password"xxxx", port63790, db0)r1 r.ts()# print(r1.get("ts_key"))# print(r.exists(ts_key))# # 清空键…

【技巧】Git 版本控制工具没有图标提示怎么办?

Git 版本控制工具在日常开发中使用率是非常高的,多数情况下会安装 TortoiseGit 之类的插件,让文件夹显示图标,方便观察文件的状态。但是有时装完插件之后发现,文件夹/文件并没有图标显示,可以按照以下思路进行排查&…

Ts支持哪些类型和类型运算(上)

目录 1、元组 2、接口(interface) 3、枚举(Enum) 4、字面量类型 5、keyof 6、in keyof 7、类型的装饰 静态类型系统 就是把 类型检查从运行时提前到了编译时,所以ts类型系统中的许多类型与js并无区别 例如&am…

2024-4-22 群讨论:微服务启动预热相关

以下来自本人拉的一个关于 Java 技术的讨论群。关注公众号:hashcon,私信进群拉你 Hotspot JVM 进程启动后,流量到来的时候 JIT 吃掉很多 CPU,如何观察到? 很多途径都能观察到: top -Hp:这个需…

MTK6775/MT6775/曦力P70联发科处理器性能参数资料

联发科MT6775(曦力P70)芯片搭载强大的Arm Cortex-A73/A53八核CPU,并采用台积电12纳米FinFET制程工艺,相较于其他14纳米级别产品,功耗节省达到了15%。此外,曦力P70还配备了高效能的Arm Mali-G72 GPU,相比上一代产品曦力…

Java——继承与组合

和继承类似, 组合也是一种表达类之间关系的方式, 也是能够达到代码重用的效果。组合并没有涉及到特殊的语法 (诸如 extends 这样的关键字), 仅仅是将一个类的实例作为另外一个类的字段。 继承表示对象之间是is-a的关系,比如:狗是动物,猫是动…

YOLOv9训练结果分析->mAP、Precision、Recall、FPS、Confienc、混淆矩阵分析

简介 这篇博客,主要给大家讲解我们在训练yolov9时生成的结果文件中各个图片及其中指标的含义,帮助大家更深入的理解,以及我们在评估模型时和发表论文时主要关注的参数有那些。本文通过举例训练过程中的某一时间的结果来帮助大家理解&#xf…

动态规划——切割钢条问题

一、动态规划 动态规划算法通常用于解决最优化问题(寻求最优解)。其思想与分治法类似,将待求解的问题分成若干个子问题,先求出子问题,再根据子问题的解求出原来问题中的解,与分支法不同的是,在动…

【勒索病毒恢复】.svh勒索病毒介绍及恢复方案

一、.[[backupwaifu.club]].svh勒索病毒介绍 svh勒索病毒是一种恶意软件,它通过加密受害者的文件并要求支付赎金来解锁,从而达到勒索的目的。这种病毒已经存在了数年,并且不断演变,形成了多种不同的家族和变种。如果您的数据承载着…

Bentley二次开发教程02-开发环境搭建

1 Bentley 平台介绍 图 1 Bentley 平台介绍 Bentley 软件大致可分为四大平台,分别为用于设计的 Microstation 平台,用于协同的 ProjectWise 平台,用于对资产进行全生命周期管理的 AssetWise 平台和数据互联互通的 数字孪生平台 iTwin。 1.1 …

CyclicBarrier(循环屏障)源码解读与使用

🏷️个人主页:牵着猫散步的鼠鼠 🏷️系列专栏:Java全栈-专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 目录 1. 前言 2. 什么是CyclicBarrier? 3. CyclicBarrier与CountDownL…