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

算法与数据结构(五)--树【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&#xff0c;将JSON字符串&#xff0c;解析为复杂类型。 比如&#xff0c;解析成如下类型&#xff1a; Map<String, List<Bean>> 依赖&#xff08;Gson&#xff09; <dependency><groupId>com.google.code.gson</groupId><art…...

伪彩色处理及算法

伪色彩(false color)是指将真实世界的中无法被肉眼观察到的色彩通过计算机或其他技术转换为可见光,从而使人们能够看到这些原本无法看到的色彩。这种技术被广泛应用于军事、医学、科研等领域。 在医学领域,伪色彩技术被用于医学影像诊断。例如,通过将不同灰度的图像映射到…...

Gradle-02:问题Plugin with id ‘maven‘ not found

1. 背景 在一次使用 Gradle 构建自己项目&#xff0c;完事&#xff0c;需要上传到本地 Maven 仓库&#xff0c;因为事先并不清楚 apply plugin: maven 插件已经被 Gradle 移除&#xff0c;找了一圈&#xff0c;才找到解决方案。 2. 原因 apply plugin: maven def localRepo f…...

jupyter lab环境配置

1.jupyterlab 使用虚拟环境 conda install ipykernelpython -m ipykernel install --user --name tf --display-name "tf" #例&#xff1a;环境名称tf2. jupyter lab kernel管理 show kernel list jupyter kernelspec listremove kernel jupyter kernelspec re…...

Unity Sort Group(排序组)

** Unity 中的Sort Group组组件允许让Sprite Renderer(精灵渲染器)重新决定渲染顺序. ** 作为组件存在 组件内容&#xff1a; Unity 使用Sort Group 组件的Sort layer 和Order in layer的值来确定排序组在渲染队列内相对与场景内其他排序组和游戏对象的优先级。 属性功能So…...

基于总线加锁和缓存锁(CPU实现原子操作的两种方式)

总线锁 总线锁就是使用处理器提供的一个LOCK#信号&#xff0c;当一个处理器在总线上输出此信号时&#xff0c;其他处理器的请求将被阻塞住&#xff0c;那么该处理器可以独占共享内存。 CPU和内存之间的通信被锁&#xff01;&#xff01; 如果多个处理器同时对共享变量进行读写…...

MybatisPlus存在 sql 注入漏洞(CVE-2023-25330)解决办法

首先我们了解下这个漏洞是什么&#xff1f; MyBatis-Plus TenantPlugin 是 MyBatis-Plus 的一个为多租户场景而设计的插件&#xff0c;可以在 SQL 中自动添加租户 ID 来实现数据隔离功能。 MyBatis-Plus TenantPlugin 3.5.3.1及之前版本由于 TenantHandler#getTenantId 方法在…...

【java】使用maven完成一个servlet项目

一、创建项目 创建一个maven项目 maven是一个管理java项目的工具&#xff0c;根据maven的pom.xml可以引入各种依赖&#xff0c;插件。 步骤 打开idea&#xff0c;点击新建项目 点击创建项目&#xff0c;项目创建就完成了 进入时会自动打开pom.xml文件。 pom是项目的配置文件…...

前端Vue入门-day07-Vuex入门

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 自定义创建项目 vuex概述 构建 vuex [多组件数据共享] 环境 创建一个空仓库 state 状态 1. 提供数据&…...

2023再谈前端状态管理

目录 什么是状态管理&#xff1f; 状态 常见模式 要解决的问题 心智模型 React Context Context 的问题 优点 缺点 React 外部状态管理库 概览 Class 时代 Redux 单向数据流 三大原则 如何处理异步 如何处理数据间联动 优点 缺点 Dva icestore Mobx 设…...

ffmpeg SDL播放器--播放udp组播流

c调用ffmpeg api及SDL库播放播放udp组播流。 代码及工程见https://download.csdn.net/download/daqinzl/88168574 参考文档&#xff1a;https://blog.csdn.net/a53818742/article/details/109312740 开发工具&#xff1a;visual studio 2019 记得推送udp流&#xff0c;可采…...

__attribute__((noreturn))

GNU C 的一大特色就是__attribute__ 机制&#xff0c;__attribute__ 可以设置函数属性&#xff08;Function Attribute&#xff09;、变量属性&#xff08;Variable Attribute&#xff09;和类型属性&#xff08;Type Attribute&#xff09;。 语法格式为: __attribute__((att…...

遮挡边界处的深度补全和双曲面外推

论文地址&#xff1a;Depth Completion with Twin Surface Extrapolation at Occlusion Boundaries 论文代码&#xff1a;https://github.com/imransai/TWISE 深度补全是从稀疏的已知深度值开始&#xff0c;为其余图像像素估计未知深度。 大多数方法将其建模为深度插值&#x…...

LK-99室温超导激发万万亿市场,将对我们的生活产生哪些影响?

7月下旬&#xff0c;韩国量子能源研究中心公司相关研究团队在预印本网站上陆续公布两篇类似的论文&#xff0c;宣称一种命名为LK-99的铜掺杂铅磷灰石材料拥有“室温常压”超导能力&#xff0c;系全世界首款室温常压超导材料。 它们的实验方法比较简单&#xff0c;就是把铅、铜、…...

子集——力扣78

文章目录 题目描述法一 迭代法实现子集枚举题目描述 法一 迭代法实现子集枚举 class Solution {public:vector<int> t;vector<vector<...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...