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

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

MVC 数据库

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

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...