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

数据结构:树的概念和结构

文章目录

  • 1. 树的概念
  • 2. 树的结构
  • 3. 树的相关概念
  • 4. 树的表示
    • 孩子表示法
    • 双亲表示法
    • 孩子兄弟表示法
  • 5. 树在实际中的应用
  • 5. 树在实际中的应用

1. 树的概念

在这里插入图片描述

树是一种非线性的数据结构,它是由 n (n >= 0)个有限结点组成一个具有层次关系的.

把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.

2. 树的结构

  • 有一个特殊的结点,称为根节点,根节点没有前驱节点.
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1,T2,…Tm,其中每一个集合本身又是一棵树,并且称为根的子树
  • 树是递归定义的.

注意:树形结构中,子树之间不能有交集,否则就不是树形结构,是图结构了.


下面就是一个平平无奇的树
在这里插入图片描述

子树 T1 和子树 T2 是根节点 A 的子树,同时 D,G,H,J 组成的树也是以 B 为根节点的子树,所以说树是递归定义的.
在这里插入图片描述


对于树的定义还需要强调两点:

  • n > 0 时根节点是唯一的,不可能存在多个根节点
  • m > 0 时,子树的个数没有限制,但是它们一定是不相交的.

3. 树的相关概念

在这里插入图片描述

结点的度:一个结点含有子树的个数称为该结点的度; 如上图,A的为 2 ,D的为 3
叶结点或终端结点:度为 0 的结点称为叶结点; 如上图, G, H, I, J, F为叶节点
非终端结点或分支结点:度不为 0 的结点; 如上图, A, B, C, D, E为分支结点
双亲结点或父节点:若一个结点含有子节点,则这个结点称为其子节点的父节点; 如上图,A 为 B 的父节点
孩子结点或子节点:一个结点含有的子树的根节点称为该结点的子节点; 如上图,E 是 C 的孩子结点
兄弟结点:具有相同父节点的结点互称为兄弟结点;如上图,G, H, I互称为兄弟结点
树的度:一棵树中,最大的结点的度称为树的度如上图,树的度为 3
结点的层次:从根开始定义起, 根为第1层,根的子节点为第2层,以此类推
树的高度或深度:树中结点的最大层次如上图,该树的高度为4
堂兄弟结点:双亲在同一层的结点互为堂兄弟如上图, I, J互为堂兄弟结点
结点的祖先:从根到该结点所经分支上的所有节点如上图,A 是所有结点的祖先
子孙:以某结点为根的子树中任一节点都称为该节点的子孙如上图:所有结点都是 A 的子孙
森林:由 m (m > 0) 棵互不相交的树的集合称为森林

4. 树的表示

以前学单链表的时候就有一个指针,双链表有两个指针,但是树有几个指针就不确定了,因为树没有规定每个结点有多少孩子.
有三种方式来表示

孩子表示法

说明了树的度为N,使用顺序表表示

每个结点有多个指针域,其中每个指针指向一棵子树的根节点

#define N 3     //假设树的度为Nstruct TreeNode
{int val;struct TreeNode* child[N];  //指针数组
};  

但是这样的表示也有缺陷,就是需要知道树的度,而且很有可能造成空间的浪费

双亲表示法

每个结点中,附设一个指示器指示其双亲结点在数组中的位置

struct TreeNode
{int val;int parent;
}

在这里插入图片描述

在这里插入图片描述

虽然找到该结点的双亲结点时间复杂度为 O ( 1 ) O(1) O(1), 但是要找到该结点的子节点却仍然需要遍历整个树才可以找到,显然这个结构也有缺陷

孩子兄弟表示法

任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的.因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟.

struct TreeNode
{int val;struct TreeNode* firstchild;struct TreeNode* nextbrother;
}

在这里插入图片描述

这样可以说是最优的表示法了
如果我们想要得到某个结点的所有孩子,下面的代码就可以了.

struct TreeNode* Anode;
struct TreeNode* child = Anode->firstchild;while (child)
{printf("%d ", child->val);child = child->nextbrother;
}

这样确实做到了最大节省空间,同时,这也是一个二叉树,它的逻辑结构适合很多操作,是一个很优秀的逻辑结构.

5. 树在实际中的应用

文件系统的目录树结构、网络拓扑,最短路径问题,搜索引擎、思维导图等
了最大节省空间,同时,这也是一个二叉树,它的逻辑结构适合很多操作,是一个很优秀的逻辑结构.

5. 树在实际中的应用

文件系统的目录树结构、网络拓扑,最短路径问题,搜索引擎、思维导图等
在这里插入图片描述

相关文章:

数据结构:树的概念和结构

文章目录 1. 树的概念2. 树的结构3. 树的相关概念4. 树的表示孩子表示法双亲表示法孩子兄弟表示法 5. 树在实际中的应用5. 树在实际中的应用 1. 树的概念 树是一种非线性的数据结构,它是由 n (n > 0)个有限结点组成一个具有层次关系的. 把它叫做树是因为它看起来像一棵倒挂的…...

【GIS】栅格转面报错:ERROR 000864输入栅格: 输入不在定义的属性域内。 ERROR 000863: 无效的 GP 数据类型

问题: 栅格转面(矢量)时,ArcGIS窗口显示:ERROR 000864输入栅格: 输入不在定义的属性域内。 ERROR 000863: 无效的 GP 数据类型. 原因: 栅格转面时输入的栅格数据集的字段必须是整型. 解决办法: 使用Spatial Analyst中的转为整型工具,将栅格数据转为整型后再进行栅格转面的操作…...

32 WEB漏洞-文件操作之文件下载读取全解

目录 介绍利用获取数据库配置文件文件名,参数值,目录符号 涉及案例:Pikachu-文件下载测试-参数Zdns-文件下载真实测试-功能点小米路由器-文件读取真实测试-漏洞RoarCTF2019-文件读取真题复现-比赛百度杯2017二月-Zone真题复现-比赛拓展 下载和读取都差不…...

Linux之history、tab、alias、命令执行顺序、管道符以及exit

目录 Linux之history、tab、alias、命令执行顺序、管道符以及exit history历史命令 格式 参数 修改默认记录历史命令条数 案例 案例1 --- 显示history历史记录中出现次数最高的top10 案例2 --- 增加history显示的时间信息 命令与文件名补全 --- tab 命令别名 格式 案…...

vcomp100.dll丢失怎样修复?5个靠谱的修复方法分享

VCOMP100.DLL 是由微软打造的动态链接库,它对于一些图形密集型应用,例如Photoshop,以及多款知名游戏如巫师3的运行至关重要。 如果操作系统在启动应用程序时无法找到此vcomp100.dll,则会出现vcomp100.dll丢失或未找到错误。 如果D…...

Vue3自定义指令(directive)

文章目录 前言一、Vue3指令钩子函数二、自定义指令的两种方式1.局部使用例子1:鉴权例子2:拖拽 2.全局使用例子1:监听宽高指令例子2:监听是否出现在视口 总结 前言 此文章主要讲了vue3中自定义指令的使用,以及一些WebA…...

大数据课程L9——网站流量项目的实时业务处理代码

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握网站流量项目的SparkStreaming代码; ⚪ 掌握网站流量项目的HBaseUtil代码; ⚪ 掌握网站流量项目的MysqlUtil代码; ⚪ 掌握网站流量项目的LogBean代码; ⚪ 掌握网站流量项目的To…...

【2023最新B站评论爬虫】用python爬取上千条哔哩哔哩评论

文章目录 一、爬取目标二、展示爬取结果三、爬虫代码四、同步视频五、附完整源码 您好,我是 马哥python说,一枚10年程序猿。 一、爬取目标 之前,我分享过一些B站的爬虫: 【Python爬虫案例】用Python爬取李子柒B站视频数据 【Pyt…...

mysql设置max_sp_recursion_depth,sql_mode

mysql 中设置 @@max_sp_recursion_depth select @@max_sp_recursion_depth; 今天在mysql 写存储过程递归调用时,发现老是报错(recovery limit 0(as set by the max_sp_recursion_depth));后来百度下发现 max_sp_recursion_depth设置不对; 这个修改涉及到全局和session级修…...

论文阅读:SERE: Exploring Feature Self-relation for Self-supervised Transformer

Related Work Self-supervised 学习目的是在无人工标注的情况下通过自定制的任务(hand-crafted pretext tasks)学习丰富的表示。 Abstract 使用自监督学习为卷积网络(CNN)学习表示已经被验证对视觉任务有效。作为CNN的一种替代…...

遥感数据与作物模型同化应用:PROSAIL模型、DSSAT模型、参数敏感性分析、数据同化算法、模型耦合、精度验证等主要环节

查看原文>>>遥感数据与作物模型同化实践技术应用 基于过程的作物生长模拟模型DSSAT是现代农业系统研究的有力工具,可以定量描述作物生长发育和产量形成过程及其与气候因子、土壤环境、品种类型和技术措施之间的关系,为不同条件下作物生长发育及…...

Navicat15工具连接PostgreSQL15失败

1.错误现象及原因 错误现象: 错误原因: postgresql 15版本中 pg_database 系统表把 datlastsysoid 列删除了,所以造成了此错误。 2.解决方法 (1)将Navicat工具更新到官网最新版本。 (2)更换…...

开源AI家庭自动化助手-手机控制家庭智能家居服务

产品简介 将本地控制和隐私放在首位的开源家庭自动化。由全球开发者和 DIY 爱好者社区提供支持。非常适合在 Raspberry Pi 或本地服务器上运行。 功能介绍 1. 控制面板在控制面板,你可以查看家庭的灯光,温度,门铃,音响&#xf…...

解决CSS定位错乱/疑难杂症的终极绝招==》从样式污染开始排查

我们接手他人或者第三方项目的时候,有时候会遇到一些莫名其妙的问题: 明明自己的样式写的没有问题,但是网页上却显示的乱七八糟的,或者效果完全出不来。 案例如下: 这里只用了很典型的flex弹性布局,并没有…...

【笔记】《C++性能优化指南》Ch3 测量性能

【笔记】《C性能优化指南》Ch3 测量性能 1. 优化思想1.1 专业的性能测试流程1.2 优化准则1.2.1 90/10规则1.2.2 Amdahl定律 2. 进行实验2.1 记实验笔记2.2 测量基准性能并设定目标2.3 你只能改善你能够测量的 3. 分析程序执行3.1 实现分析器的方式3.2 分析器的优缺点 4. 测量长…...

2023大数据面试总结

文章目录 Flink(SQL相关后面专题补充)1. 把状态后端从FileSystem改为RocksDB后,Flink任务状态存储会发生哪些变化?2. Flink SQL API State TTL 的过期机制是 onCreateAndUpdate 还是 onReadAndWrite?3. watermark 到底…...

udev自动创建设备节点的机制

流程框图如下 自动创建 1 内核检测到设备插入后,会发送一个uevent事件到内核中,并提供有关硬件设备的信息。 2 udevd守护程序收到uevent事件后,创建一个设备类,(向上提交目录信息),会在内核中…...

访问局域网内共享文件时报错0x80070043,找不到网络名

我是菜鸡 此篇只为分享一个我遇到的很简单的但是排查了好久的小问题。 我的网络环境是在校园网内, 自己的办公电脑设置了固定IP:10.11.128.236,同事电脑IP为:10.11.128.255 本人需要访问同事在局域网内分享的文件,…...

Java定时器

对于定时器的设定,想必大家在不少网站或者文章中见到吧,但是所谓的定时器如何去用Java代码来bianx呢??感兴趣的老铁,可以看一下笔者这篇文章哟~~ 所谓的定时器就是闹钟!! 设定一个时间&#x…...

科普js加密时出现的错误

当你在使用Babel解析JavaScript代码时,可能会遇到一个错误信息:“Deleting local variable in strict mode”(在严格模式下删除本地变量)。这个错误信息通常表示你正在尝试删除一个使用let或const关键字声明的变量。在JavaScript的…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

Go语言多线程问题

打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...

数据挖掘是什么?数据挖掘技术有哪些?

目录 一、数据挖掘是什么 二、常见的数据挖掘技术 1. 关联规则挖掘 2. 分类算法 3. 聚类分析 4. 回归分析 三、数据挖掘的应用领域 1. 商业领域 2. 医疗领域 3. 金融领域 4. 其他领域 四、数据挖掘面临的挑战和未来趋势 1. 面临的挑战 2. 未来趋势 五、总结 数据…...