当前位置: 首页 > 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的…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

生成 Git SSH 证书

🔑 1. ​​生成 SSH 密钥对​​ 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​: -t rsa&#x…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

SpringTask-03.入门案例

一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)​现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...