算法与数据结构(五)--树【1】树与二叉树是什么
一.树的定义
树是一个具有层次结构的集合,是由一个有限集和集合上定义的一种层次结构关系构成的。不同于线性表,树并不是线性的,而是有分支的。
树(Tree)是n(n>=0)个结点的有限集。
若n=0,称为空树;
若n>0,则它满足如下两个条件:
(1)有且仅有一个特定的称为根(Root)的结点
(2)其余结点可分为m(m>=0)个互不相交的有限集T1,T2,T3,...,Tm,其实每一个集合本身又是一颗树,并称为根的子树(Sub Tree)。
显然,树的定义是一个递归的定义。
二.树的基本术语
结点:数据元素以及指向子树的分支
根结点:非空树中无前驱结点的结点
结点的度:结点拥有的子数树
树的度:树内各节点的度的最大值
叶子结点/终端节点:度=0的结点
非终端结点:根结点以外的分支结点称为内部结点
结点的子树的根称为该结点的孩子,该结点称为孩子的双亲
兄弟:同一个双亲的结点 堂兄弟:双亲在同一层的结点
结点的祖先:从根到该结点所经分支上的所有结点。
结点的子孙:以某结点为根的子树中的任一结点。
树的深度:树中的结点的最大层次,就是说有几层。
有序树:树中结点的各子树从左至右有次序
无序树:树种结点的各子树无次序
就像这棵树,如果规定了T1,T2,T3有次序,也就是说规定T1一定要在左边,T2一定要在中间,T3一定要在右边,如果更换次序,那么就成了另一颗树。那么这种树就叫作有序树。
如果规定更换次序仍是同一棵树,那么这种树是无序树。
森林:是m(m>=0)棵互不相交的树的集合。把根结点删除树就变成了森林。
一颗树可以看成是一个特殊的森林。
给森林中的各子树加上一个双亲结点,森林就变成了树。
树一定是森林,但森林不一定是树。
三.二叉树的定义
为什么要重点研究每结点最多只有两个“叉”的树?
二叉树的结构简单,规律性强;可以证明,所有的树都能转为唯一对应的二叉树,不失一般性。
普通树(多叉树)若不转化为二叉树,则运算很难实现。
二叉树是n(n>=0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两科互不相交的分别称为这个根的左子树和右子树的二叉树组成。
特点:(1)每个结点最多有俩孩子【二叉树中不存在度大于2的结点】
(2)子树有左右之分,其次序不能颠倒。
(3)二叉树可以是空集合,根可以有空的左子树或空的右子树。
注:二叉树不是树的特殊情况,它们是两个概念。
二叉树结点的子树要区分左子树和右子树,即使只有一颗子树也要进行区分,说明它是左子树,还是右子树。
树当结点只有一个孩子时,就无须区分它是左还是右的次序。因此,二者是不同的。这是二叉树与树的最主要差别。



注:虽然二叉树与树的概念不同,但是关于树的基本术语对二叉树都适用。
四.二叉树案例引入--利用二叉树求解表达式的值
若表达式为“第一操作数 运算符 第二操作数”的形式,则对应的二叉树中以左子树表示第一操作数,右子树表示第二操作数,根结点的数据域存放运算符(若为一元运算符,则左子树为空),其中,操作数本身又为表达式。
相关文章:
算法与数据结构(五)--树【1】树与二叉树是什么
一.树的定义 树是一个具有层次结构的集合,是由一个有限集和集合上定义的一种层次结构关系构成的。不同于线性表,树并不是线性的,而是有分支的。 树(Tree)是n(n>0)个结点的有限集。 若n0&…...
打开的idea项目maven不生效
方法一:CtrlshiftA(或者help---->find action), 输入maven, 点击add maven projects,选择本项目中的pom.xml配置文件,等待加载........ 方法二:view->tools windows->mave…...
kvm+qemu+libvirt管理虚机
virt-manager 图形化创建虚拟机 #virt-manager纳管远程kvm虚拟机 # 可以指定kvm虚机的ssh端口和virt-manager所在主机的私钥 virt-manager -c qemussh://root10.197.115.17:5555/system?keyfileid_rsa --no-fork # 如果你生成的ssh-key 的名称是 test-key,在/home/ssh-key/ 目…...
电气防火限流式保护器在汽车充电桩使用上的作用
【摘要】 随着电动汽车行业的不断发展,电动汽车充电设施的使用会变得越来越频繁和广泛。根据中汽协数据显示,2022年上半年,我国新能源汽车产销分别完成266.1万辆和260万辆,同比均增长1.2倍,市场渗透率达21.6%。因此,电动汽车的安全…...
VBA技术资料MF38:VBA_在Excel中隐藏公式
【分享成果,随喜正能量】佛祖也无能为力的四件事:第一,因果不可改,自因自果,别人是代替不了的;第二,智慧不可赐,任何人要开智慧,离不开自身的磨练;第三&#…...
Gson:解析JSON为复杂对象:TypeToken
需求 通过Gson,将JSON字符串,解析为复杂类型。 比如,解析成如下类型: Map<String, List<Bean>> 依赖(Gson) <dependency><groupId>com.google.code.gson</groupId><art…...
伪彩色处理及算法
伪色彩(false color)是指将真实世界的中无法被肉眼观察到的色彩通过计算机或其他技术转换为可见光,从而使人们能够看到这些原本无法看到的色彩。这种技术被广泛应用于军事、医学、科研等领域。 在医学领域,伪色彩技术被用于医学影像诊断。例如,通过将不同灰度的图像映射到…...
Gradle-02:问题Plugin with id ‘maven‘ not found
1. 背景 在一次使用 Gradle 构建自己项目,完事,需要上传到本地 Maven 仓库,因为事先并不清楚 apply plugin: maven 插件已经被 Gradle 移除,找了一圈,才找到解决方案。 2. 原因 apply plugin: maven def localRepo f…...
jupyter lab环境配置
1.jupyterlab 使用虚拟环境 conda install ipykernelpython -m ipykernel install --user --name tf --display-name "tf" #例:环境名称tf2. jupyter lab kernel管理 show kernel list jupyter kernelspec listremove kernel jupyter kernelspec re…...
Unity Sort Group(排序组)
** Unity 中的Sort Group组组件允许让Sprite Renderer(精灵渲染器)重新决定渲染顺序. ** 作为组件存在 组件内容: Unity 使用Sort Group 组件的Sort layer 和Order in layer的值来确定排序组在渲染队列内相对与场景内其他排序组和游戏对象的优先级。 属性功能So…...
基于总线加锁和缓存锁(CPU实现原子操作的两种方式)
总线锁 总线锁就是使用处理器提供的一个LOCK#信号,当一个处理器在总线上输出此信号时,其他处理器的请求将被阻塞住,那么该处理器可以独占共享内存。 CPU和内存之间的通信被锁!! 如果多个处理器同时对共享变量进行读写…...
MybatisPlus存在 sql 注入漏洞(CVE-2023-25330)解决办法
首先我们了解下这个漏洞是什么? MyBatis-Plus TenantPlugin 是 MyBatis-Plus 的一个为多租户场景而设计的插件,可以在 SQL 中自动添加租户 ID 来实现数据隔离功能。 MyBatis-Plus TenantPlugin 3.5.3.1及之前版本由于 TenantHandler#getTenantId 方法在…...
【java】使用maven完成一个servlet项目
一、创建项目 创建一个maven项目 maven是一个管理java项目的工具,根据maven的pom.xml可以引入各种依赖,插件。 步骤 打开idea,点击新建项目 点击创建项目,项目创建就完成了 进入时会自动打开pom.xml文件。 pom是项目的配置文件…...
前端Vue入门-day07-Vuex入门
(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹) 目录 自定义创建项目 vuex概述 构建 vuex [多组件数据共享] 环境 创建一个空仓库 state 状态 1. 提供数据&…...
2023再谈前端状态管理
目录 什么是状态管理? 状态 常见模式 要解决的问题 心智模型 React Context Context 的问题 优点 缺点 React 外部状态管理库 概览 Class 时代 Redux 单向数据流 三大原则 如何处理异步 如何处理数据间联动 优点 缺点 Dva icestore Mobx 设…...
ffmpeg SDL播放器--播放udp组播流
c调用ffmpeg api及SDL库播放播放udp组播流。 代码及工程见https://download.csdn.net/download/daqinzl/88168574 参考文档:https://blog.csdn.net/a53818742/article/details/109312740 开发工具:visual studio 2019 记得推送udp流,可采…...
__attribute__((noreturn))
GNU C 的一大特色就是__attribute__ 机制,__attribute__ 可以设置函数属性(Function Attribute)、变量属性(Variable Attribute)和类型属性(Type Attribute)。 语法格式为: __attribute__((att…...
遮挡边界处的深度补全和双曲面外推
论文地址:Depth Completion with Twin Surface Extrapolation at Occlusion Boundaries 论文代码:https://github.com/imransai/TWISE 深度补全是从稀疏的已知深度值开始,为其余图像像素估计未知深度。 大多数方法将其建模为深度插值&#x…...
LK-99室温超导激发万万亿市场,将对我们的生活产生哪些影响?
7月下旬,韩国量子能源研究中心公司相关研究团队在预印本网站上陆续公布两篇类似的论文,宣称一种命名为LK-99的铜掺杂铅磷灰石材料拥有“室温常压”超导能力,系全世界首款室温常压超导材料。 它们的实验方法比较简单,就是把铅、铜、…...
子集——力扣78
文章目录 题目描述法一 迭代法实现子集枚举题目描述 法一 迭代法实现子集枚举 class Solution {public:vector<int> t;vector<vector<...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
