【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 的父结点都在第二层,所以之间为堂兄弟的关系。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【webrtc】Chrome和Firefox在SDP协商过程中,针对localhost的不同处理

内网下chrome端webrtc协商失败 现象 我有一个webrtc服务器在局域网内,使用chrome浏览器访问时,发现webrtc在做媒体协商时失败。 具体表现是,在交换sdp后,ice的状态是oniceconnectionstatechange: failed 但是换成Firefox浏览器…

html接入腾讯地图

1.申请key key申请地址&#xff1a;https://lbs.qq.com/dev/console/application/mine 官方文档 https://lbs.qq.com/webApi/javascriptGL/glGuide/glBasic 2.html接入示例 <!DOCTYPE html> <html lang"en"> <head><meta charset"U…

全国青少年劳动技能与智能设计大赛安徽省赛——庐江县师资培训活动圆满举行

为贯彻落实科教兴国的国家战略目标&#xff0c;根据《教育部办公厅关于公布 2022—2025 学年面向中小学生的全国性竞赛活动》的相关通知。为了提升教师在劳动技能与智能设计领域的教学与指导能力&#xff0c;为即将到来的省级大赛做好充分准备。4月18日&#xff0c;一场由庐江县…

维基百科、百度百科和搜狗百科词条的创建流程

随着网络的发展&#xff0c;百度百科、搜狗百科、维基百科等百科网站已经成为大众获取知识的重要途径。因为百科具有得天独厚的平台优势&#xff0c;百科上的信息可信度高&#xff0c;权威性强。所以百科平台也成为商家的必争之地。这里小马识途聊聊如何创建百度百科、搜狗百科…

GPT与GAN结合生成图像——VQGAN原理解析

1、前言 这篇文章&#xff0c;我们讲VQ_GAN&#xff0c;这是一个将特征向量离散化的模型&#xff0c;其效果相当不错&#xff0c;搭配Transformer&#xff08;GPT&#xff09;或者CLIP使用&#xff0c;达到的效果在当时可谓是令人拍案叫绝&#xff01; 原论文&#xff1a;Tam…

LTD271次升级 | 网站/小程序可设访问IP的黑白名单 • 官微中心支持PDF等办公文件预览与并分享 • 订单退款显示更详尽明细

1、新增IP访问限制功能&#xff1b; 2、订单新增交易号显示与退款明细显示&#xff1b; 3、自定义地址增加四级地区&#xff1b; 4、Android版App优化文件功能&#xff1b; 5、已知问题修复与优化&#xff1b; 01 官微中心 1) 新增IP限制访问功能 允许或者禁止某些 IP 或…

uniapp项目中禁止横屏 ,app不要自动旋转 -,保持竖屏,uniapp取消重力感应

uniapp项目中禁止横屏 &#xff0c;app不要自动旋转 -&#xff0c;保持竖屏&#xff0c;uniapp取消重力感应 1.适用于移动端&#xff0c;安卓和IOS&#xff0c;当即使手机打开了自动旋转的按钮&#xff0c;设置如下的代码后&#xff0c;页面依旧保持竖屏。 步骤一&#xff1a…

【深度学习】yolo-World,数据标注,zeroshot,目标检测

仓库&#xff1a;https://github.com/AILab-CVC/YOLO-World 下载权重&#xff1a; 仓库下载和环境设置 下载仓库&#xff1a;使用以下命令从 GitHub 上克隆仓库&#xff1a; git clone --recursive https://github.com/AILab-CVC/YOLO-World.git创建并激活环境&#xff1a…

程序猿成长之路之数据挖掘篇——朴素贝叶斯

朴素贝叶斯是数据挖掘分类的基础&#xff0c;本篇文章将介绍一下朴素贝叶斯算法 情景再现 以挑选西瓜为例&#xff0c;西瓜的色泽、瓜蒂、敲响声音、触感、脐部等特征都会影响到西瓜的好坏。那么我们怎么样可以挑选出一个好的西瓜呢&#xff1f; 分析过程 既然挑选西瓜有多个…

DaPy:实现数据分析与处理

DaPy&#xff1a;实现数据分析与处理 DaPy是一个用于数据分析和处理的Python库&#xff0c;它提供了一系列强大的工具和功能&#xff0c;使开发者能够高效地进行数据清洗、转换和分析。本文将深入解析DaPy库的特点、功能以及使用示例&#xff0c;帮助读者了解如何利用DaPy库处理…

贪心算法在单位时间任务调度问题中的应用

贪心算法在单位时间任务调度问题中的应用 一、引言二、问题描述与算法设计三、算法证明四、算法实现与效率分析五、C语言实现示例六、结论 一、引言 单位时间任务调度问题是一类经典的优化问题&#xff0c;旨在分配任务到不同的时间槽中&#xff0c;使得某种性能指标达到最优。…

【QT进阶】Qt http编程之实现websocket server服务器端

往期回顾 【QT进阶】Qt http编程之json解析的简单介绍-CSDN博客 【QT进阶】Qt http编程之nlohmann json库使用的简单介绍-CSDN博客 【QT进阶】Qt http编程之websocket的简单介绍-CSDN博客 【QT进阶】Qt http编程之实现websocket server服务器端 一、最终效果 通过ip地址和端口…

万界星空科技电机行业MES+商业电机行业开源MES+项目合作

要得出mes系统解决方案在机电行业的应用范围&#xff0c;我们先来看一下传统机电行业的管理难题&#xff1a; 1、 产品标准化程度较低&#xff0c;制造工艺复杂&#xff0c;生产周期较长&#xff0c;产品质量不稳定&#xff1b; 2、 自动化程度低&#xff0c;大多数工序以手工…

【视频异常检测】Open-Vocabulary Video Anomaly Detection 论文阅读

Open-Vocabulary Video Anomaly Detection 论文阅读 AbstractMethod3.1. Overall Framework3.2. Temporal Adapter Module3.3. Semantic Knowledge Injection Module3.4. Novel Anomaly Synthesis Module3.5. Objective Functions3.5.1 Training stage without pseudo anomaly …

电子信息制造工厂5G智能制造数字孪生可视化平台,推进数字化转型

电子信息制造工厂5G智能制造数字孪生可视化平台&#xff0c;推进数字化转型。5G智能制造数字孪生可视化平台利用5G网络的高速、低延迟特性&#xff0c;结合数字孪生技术和可视化界面&#xff0c;为电子信息制造工厂提供了一种全新的生产管理模式。不仅提升生产效率&#xff0c;…

设计模式(三):抽象工厂模式

设计模式&#xff08;三&#xff09;&#xff1a;抽象工厂模式 1. 抽象工厂模式的介绍2. 抽象工厂模式的类图3. 抽象工厂模式的实现3.1 创建摩托车的接口3.2 创建摩托车的具体实现3.3 创建汽车的接口3.4 创建汽车的具体产品3.5 创建抽象工厂3.6 创建具体工厂3.7 创建工厂生成器…

Fisher判别示例:鸢尾花(iris)数据(R)

先读取iris数据&#xff0c;再用程序包MASS&#xff08;记得要在使用MASS前下载好该程序包&#xff09;中的线性函数lda()作判别分析&#xff1a; data(iris) #读入数据 iris #展示数据 attach(iris) #用变量名绑定对应数据 library(MASS) #加载MASS程序包 ldlda(Species~…

《ElementPlus 与 ElementUI 差异集合》el-select 显示下拉列表在 Cesium 场景中无法监听关闭

前言 仅在 Element UI 时有此问题&#xff0c;Element Plus 由于内部结构差异较大&#xff0c;不存在此问题。详见《el-select 差异点&#xff0c;如&#xff1a;高、宽、body插入等》&#xff1b; 问题 点击空白处&#xff0c;下拉列表可监听并关闭&#xff1b;但在 Cesium…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之五 简单进行车牌检测和识别 一、简单介绍 二、简单进行车牌检测和识别实现原理 …

鸿蒙(HarmonyOS)性能优化实战-Swiper高性能开发

背景 在应用开发中&#xff0c;Swiper 组件常用于翻页场景&#xff0c;比如&#xff1a;桌面、图库等应用。Swiper 组件滑动切换页面时&#xff0c;基于按需加载原则通常会在下一个页面将要显示时才对该页面进行加载和布局绘制&#xff0c;这个过程包括&#xff1a; 如果该页面…