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

算法通过村第六关-树青铜笔记|中序后序

文章目录

  • 前言
  • 1. 树的常见概念
  • 2. 树的性质
  • 3. 树的定义与存储方式
  • 4. 树的遍历方式
  • 5. 通过序列构建二叉树
    • 5.1 前中序列恢复二叉树
    • 5.2 中后序列恢复二叉树
  • 总结


前言


提示:瑞秋是个小甜心,她只喜欢被爱,不懂的去爱人。 --几米《你们 我们 他们》

树是一种非常重要的数据结构,在算法和工程中都有大量的应用,我们这里从概念一步一步学习,闯过这一关,掌握树的基本特征以及遍历方面的基础问题。

1. 树的常见概念

树是一个有n个有限节点组成一个具有层次关系的集合,每个节点有0个或者多个子节点,没有父节点的节点为称为根节点,也就是说除了根节点以为每个节点都有父节点,并且有且只有一个节点。树的种类有很多,最常见的就是二叉树了,基本结构如下:

在这里插入图片描述
参考上面图的结构,可以很方面的理解树的概念:

  1. 节点的度:一个节点含有的几点的个数称为该节点的度
  2. 树的度:一颗树中,最大的节点的度称为树的度,注意与节点度的区别
  3. 叶节点或者终端节点:度为0的节点称为叶节点
  4. 非终端节点或者分支节点:度不为0的节点
  5. 双亲节点或者父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点
  6. 孩子节点或者子节点:一个节点含有的子树的根节点称为该节点的子节点
  7. 兄弟节点:具有相同父节点的节点互称为兄弟节点
  8. 节点的祖先:从根节点到该节点所有分支上的所有节点
  9. 子孙:以某节点为根节的子树中任一节点都称为该节点的子孙
  10. 森林:有m(m >= 0 )课互不相交的树的集合称为森林
  11. 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树
  12. 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树
  13. 二叉树:每个节点最多含有两个子树的树称为二叉树

2. 树的性质

  • 性质1:在二叉树的第i层上至多有2^(i - 1)个节点(i > 0)
  • 性质2:深度为k的二叉树之多有2^k - 1 个节点(k > 0)
  • 性质3:对于任意一颗二叉树,如果其叶节点数为N0,而度数为2的节点总数为N2,则N0 = N2 + 1
  • 性质4:具有n个节点的完全二叉树的深度必为log2(n + 1)
  • 性质5:对完全二叉树,若从上至下,从左至右编号,则编号为i的节点,其左孩子的编号一定是2i,其右孩子必是2i+ 1;其双亲的编号是i/2(i == 1 时为根,除外哈🤣)

满二叉树和完全二叉树是经常晕的问题,我们有必要单独看一下,满二叉树就是如果一棵二叉树只有度为0的节点和度为2的节点,而且度为0的节点在同一层,则这棵二叉树为满二叉树。

在这里插入图片描述

这颗二叉树为满二叉树,也可以说深度为k=4,有2^k -1 = 15个 节点的二叉树。

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没有填满外,其余每层节点点数都达到最大值,并且最下面一层的节点都集中在该层的最左侧的若干位置。

这个定义,就有些恶心了,估计大部分看了之后还是不懂什么是完全二叉树,看看下面的图:

在这里插入图片描述
前面两棵树的前n-1层都是满的,最后一层所有子节点都集中在左侧区域,而且节点之间不能有间隙。最后一个为什么呢?他有一个节点缺少一个左子节点/

3. 树的定义与存储方式

注意:

这里我们主要看原理,不执行代码,采用伪代码的方式,理解方便一些

定义树的原理和前面讲的链表本质上差不多,只不过多了一个指针,如果是二叉树的化,只要在链表上的定义增加一个指针就可以了:

public class TreeNode{int val;TreeNode left;TreeNode right;
}

这里本质上就是两个引用,分别指向两个位置,为了方便理解,我们称为左孩子和右孩子。如果是N叉树要如何定义呢?其实就是每个节点最多可以有N个节点指向其他位置,这里就不用left和right,我们使用List存储就行了,也就是如下:

// 定义N叉树
public class TreeNode {int val;List<TreeNode> nodes;
}

那么是否可以采用数组的方式存储二叉树呢?其实就是用数组来存储二叉树的,顺序存储的方式如图:
在这里插入图片描述
用数组来存储二叉树如何遍历呢?如果父节点的数组下标i,那么它的做还是就是 i* 2 + 1,右孩子就是 i * 2 + 2.

但是用链式表示二叉树,更方便我们理解,所以一般也采用链式二叉树。所以大家要知道一点,数组也是可以便是二叉树的。

使用数组存储的最大问题就是可能存在大量的空间浪费。如图上面假设b没有分支,那么数组1 3 4就空着,但是整个数组的大小仍然是7,因此很少使用数组来存储树。

4. 树的遍历方式

我们常见的树的遍历方式,层次遍历和深度优先遍历两种:

  • 深度优先遍历:先往深走,遇到叶子节点再往回走
  • 广度优先遍历:一层一层的去遍历,一层遍历完再访问下一层

这两种遍历方式不仅仅是二叉树,N叉树也是,图结构也有,我们更常见的叫法:广度优先和深度优先,本质上是一回事。深度优先又有前中后三种,避免混淆,我们记住一点:前指的是中间的父节点再遍历中的顺序,只要明白了这一点,前中后序就是指中间节点的位置就可以了。

看如下中间节点的顺序,就可以发现问题,访问中间节点的顺序就是所谓的遍历方式

前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

大家试着画图写一写,看看自己是否真的理解前中后序了。

在这里插入图片描述

后面大量的算法都与这四种(层次,前中后)遍历方式有关,有的题目根据处理角度不同,可以用层次遍历,也可以用一种甚至两种深度优先的方式来实现。

5. 通过序列构建二叉树

前面我们已经介绍了怎么些前中后序的过程,这里我们看一看怎么通过序列来恢复原始二叉树:

前序遍历:中左右 [5 4 1 2 6 7 8]
中序遍历:左中右 [1 4 2 5 7 6 8]
后序遍历:左右中 [1 2 4 7 8 6 5]

5.1 前中序列恢复二叉树

我们先看看如何通过中前序列恢复二叉树:

前序遍历:中左右 [5 4 1 2 6 7 8]
中序遍历:左中右 [1 4 2 5 7 6 8]
  • 第一轮

我们先从前序第一个就是访问根节点,所以根节点是5

中序遍历的特点是根节点的左子树的元素在根节点左侧,右子树的元素都在根节点右侧,从中序遍历序列我们可以划分成如下结构:

前序序列划分:
5 [ 4 1 2 ] [ 6 7 8 ]
中序序列划分:
[ 1 4 2 ] 5 [ 7 6 8 ] 

当然前序序列第一个括号里面的都是左子树的元素,第二个括号一定都是右子树的元素。

那么这里怎么将这两个括号从哪里分开,我们彩照中序的两个数组划分。我们看前序2之前的元素都在第一个括号中,7之后的元素都在第二个数组中,所以这里从2和7之间划分。

由此我们画图表示一下,看下此时的树的结构:

在这里插入图片描述

  • 第二轮:

我们先看两个序列的第一个数组

根据上面的划分方法:

前序序列划分:
4 [ 1 ] [ 2 ] 
中序序列划分:
[ 1 ] 4 [ 2 ] 

此时树的结构为:
在这里插入图片描述

  • 第三轮

我们看两个序列的第二个数组

根据上面的划分方法:

前序序列划分:
6 [ 7 ] [ 8 ] 
中序序列划分:
[ 7 ] 6 [ 8 ] 

此时树的结构为:
在这里插入图片描述
如此就是最终效果了,可以和上面的图对比一下。

5.2 中后序列恢复二叉树

通过中序和后序也能恢复原始序列,唯一不同的是后续的最后一个是根节点,中序的处理上面是一样的过程。

中序遍历:左中右 [1 4 2 5 7 6 8]
后序遍历:左右中 [1 2 4 7 8 6 5]

这里读者可以自行尝试,我这里不做赘述了。


Q&A💡:

那么有疑问了,为什么前序和后序不能恢复二叉树?

前序遍历:中左右 [5 4 1 2 6 7 8]
后序遍历:左右中 [1 2 4 7 8 6 5]

我们看前序和后序,通过前序我们可以知道根节点,通过后序我们也只能知道根节点,那么中间的部分要怎么划分呢?那些元素属于左子树,那些元素属于右子树呢?很显然,我们不得而知,所以用前序和后序不能恢复二叉树。

推荐力扣的题目⭐⭐⭐:

前序和中序造树:105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

中序和后序造树:106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)


总结

提示:树的概念,二叉树、完全二叉树、满二叉树,树的恢复,前中后序序列

相关文章:

算法通过村第六关-树青铜笔记|中序后序

文章目录 前言1. 树的常见概念2. 树的性质3. 树的定义与存储方式4. 树的遍历方式5. 通过序列构建二叉树5.1 前中序列恢复二叉树5.2 中后序列恢复二叉树 总结 前言 提示&#xff1a;瑞秋是个小甜心&#xff0c;她只喜欢被爱&#xff0c;不懂的去爱人。 --几米《你们 我们 他们》…...

C++动态内存管理+模板

&#x1f493;博主个人主页:不是笨小孩&#x1f440; ⏩专栏分类:数据结构与算法&#x1f440; C&#x1f440; 刷题专栏&#x1f440; C语言&#x1f440; &#x1f69a;代码仓库:笨小孩的代码库&#x1f440; ⏩社区&#xff1a;不是笨小孩&#x1f440; &#x1f339;欢迎大…...

SQL 注入漏洞攻击

文章目录 1. 介绍2. 无密码登录3. 无用户名无密码登录4. 合并表获取用户名密码 1. 介绍 假设你用自己的用户名和密码登录了一个付费网站&#xff0c;网站服务器就会查询一下你是不是 VIP 用户&#xff0c;而用户数据都是放在数据库中的&#xff0c;服务器通常都会向数据库进行查…...

一篇五分生信临床模型预测文章代码复现——Figure 10.机制及肿瘤免疫浸润(四)

之前讲过临床模型预测的专栏,但那只是基础版本,下面我们以自噬相关基因为例子,模仿一篇五分文章,将图和代码复现出来,学会本专栏课程,可以具备发一篇五分左右文章的水平: 本专栏目录如下: Figure 1:差异表达基因及预后基因筛选(图片仅供参考) Figure 2. 生存分析,…...

Transformer 模型中常见的特殊符号

Transformer 模型中常见的特殊符号 通过代码一起理解一下 Transformer 模型中常见的特殊符号&#xff0c; 示例代码&#xff0c; special_tokens{unk_token: [UNK], sep_token: [SEP], pad_token: [PAD], cls_token: [CLS], mask_token: [MASK]}这段代码是定义了一个字典spec…...

C# halcon SubImage的使用

SubImage(HObject imageMinuend, HObject imageSubtrahend, out HObject imageSub, HTuple mult, HTuple add) 公式 x1imageMinuend此行此列的灰度 x2imageSubtrahend此行此列的灰度 则imageSub此行此列的灰度为;(x1-x2)*multadd 溢出裁剪 以byte图为例&#xff0c;小于0&a…...

每天几道Java面试题:异常机制(第三天)

目录 第三幕、第一场&#xff09;异常机制面试题 友情提醒 背面试题很枯燥&#xff0c;加入一些戏剧场景故事人物来加深记忆。PS:点击文章目录可直接跳转到文章指定位置。 第三幕、 第一场&#xff09;异常机制面试题 【面试官老吉&#xff0c;面试官潘安&#xff0c;面试者…...

Linux 中的 chattr 命令及示例

Linux 中的chattr命令是一个文件系统命令,用于更改目录中文件的属性。该命令的主要用途是使多个文件无法被超级用户以外的用户更改。管理员表示,众所周知,Linux 是一个多用户操作系统,一个用户有可能删除另一个用户非常关心的文件。为了避免这种情况,Linux 提供了“ chatt…...

LeetCode 2605. Form Smallest Number From Two Digit Arrays【数组,哈希表,枚举;位运算】1241

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

VoxWeekly|The Sandbox 生态周报|20230904

欢迎来到由 The Sandbox 发布的《VoxWeekly》。我们会在每周发布&#xff0c;对上一周 The Sandbox 生态系统所发生的事情进行总结。 如果你喜欢我们内容&#xff0c;欢迎与朋友和家人分享。请订阅我们的 Medium 、关注我们的 Twitter&#xff0c;并加入 Discord 社区&#xf…...

antd setFieldsValue 设置初始值无效AutoComplete 设置默认值失败

antd form setFieldsValue 设置初始值无效 解决方案 setTimeout(()>{setFieldsValue(values)},100)antd AutoComplete 设置默认值失败 defaultValue 设置无效 解决方案 设置value&#xff0c;搭配onChange来设置修改...

01-Redis核心数据结构与高性能原理

上一篇&#xff1a; 1.Redis安装 下载地址&#xff1a;http://redis.io/download 安装步骤&#xff1a; # 安装gcc yum install gcc# 把下载好的redis-5.0.3.tar.gz放在/usr/local文件夹下&#xff0c;并解压 wget http://download.redis.io/releases/redis-5.0.3.tar.gz…...

预防Dos攻击

Dos----拒绝服务攻击&#xff0c;一般是构造特殊的输入&#xff0c;使得后台的处理耗时远超正常水平&#xff0c;随着请求越来越多&#xff0c;后台服务越发疲于奔命&#xff0c;最后因资源耗尽&#xff0c;无法再接受新的请求&#xff0c;最终造成拒绝服务的效果。 特殊输入例…...

ant design的文档真的是一坨屎

很多基础设置 高傲的写都不写 要自己去index.d.ts里查 这就算了&#xff0c;为什么还有错的。。。。。 即使因为版本号而不同&#xff0c;起码把差异说明一下吧&#xff0c;直接丢个错的什么意思&#xff0c;。。。。。。。。 没点子功夫还真用不了 文档 进度条 Progress -…...

关于迁移学习的一点理解

举个栗子&#xff0c;老虎图片的数量非常少&#xff0c;可以让网络先学会识别猫的图片 1、预训练模型 内容&#xff1a;利用在 ImageNet1000 数据集训练好的模型&#xff0c;将所需的模型参数下载&#xff0c;嵌入到对应的网络架构中&#xff0c;使用对预训练模型的搭建。目前P…...

【力扣周赛】第 361 场周赛(⭐前缀和+哈希表 树上倍增、LCA⭐)

文章目录 竞赛链接Q1&#xff1a;7020. 统计对称整数的数目竞赛时代码——枚举预处理 Q2&#xff1a;8040. 生成特殊数字的最少操作&#xff08;倒序遍历、贪心&#xff09;竞赛时代码——检查0、00、25、50、75 Q3&#xff1a;2845. 统计趣味子数组的数目竞赛时代码——前缀和…...

解决 Android 依赖冲突

解决办法 问题原因就是&#xff0c;各个模块所有的依赖&#xff08;递归&#xff09;的 jar 包最后都会加载到安卓的项目中&#xff0c;你可以选择 project 形式查看 External Libraries&#xff0c;都在这了。所以解决问题关键就是干掉冲突&#xff0c;剩下一个就行了&#xf…...

前端设计模式基础笔记

前端设计模式是指在前端开发中经常使用的一些解决问题的模式或思想。它们是经过实践证明的最佳实践&#xff0c;可以帮助我们更好地组织和管理我们的代码。 一、单例模式&#xff08;Singleton Pattern&#xff09; 单例模式是一种创建型模式&#xff0c;它保证一个类只有一个…...

Python项目开发:Flask基于Python的天气数据可视化平台

目录 步骤一&#xff1a;数据获取 步骤二&#xff1a;设置Flask应用程序 步骤三&#xff1a;处理用户输入和数据可视化 步骤四&#xff1a;渲染HTML模板 总结 在这个数字化时代&#xff0c;数据可视化已经成为我们理解和解释信息的重要手段。在这个项目中&#xff0c;我们…...

Dell 服务器常见报错信息汇总

Dell 服务器常见报错汇总 如果有别的报错信息欢迎补充...

算法通关村-----贪心面试大热门之区间问题

判断区间是否重叠 问题描述 给定一个会议时间安排数组intervals&#xff0c;每个会议时间都包括开始时间和结束时间,intervals[i] [starti,endi]&#xff0c;请你判断一个人是否能够参加这里面的全部会议。详见leetcode252 问题分析 先将会议安排数组按照开始时间排序&…...

OAK相机:自动或手动设置相机参数

OAK相机&#xff1a;自动或手动设置相机参数 硬件软件 硬件 使用硬件如下&#xff1a; 4✖️ov9782相机OAK-FFC-4P驱动板 硬件接线参考博主的一篇博客&#xff1a;OAK相机&#xff1a;多相机硬件同步拍摄 软件 博主使用的是Ubuntu18.04系统&#xff0c;首先配置所需的pytho…...

百家宴焕新上市,持续深耕100-300元价位段

执笔 | 尼 奥 编辑 | 古利特 4月8日&#xff0c;长江酒道曾在《百家宴谋划“晋级”之路&#xff0c;多措并举切分宴席市场“蛋糕”》一文中提到&#xff1a;“百家宴主力新品即将登场&#xff0c;市场政策灵活焕新。” 如今&#xff0c;百家宴新品及市场新政&#xff0c;正…...

Linux Debian12使用git将本地项目上传到码云(gitee)远程仓库

一、注册码云gitee账号 这个可以参考其他教程&#xff0c;本文不做介绍。 gitee官网&#xff1a;https://gitee.com/ 二、Linux Debian12安装git 如果Linux系统没有安装git&#xff0c;可以使用下面命令安装git sudo apt install git 三、gitee新建仓库 我这只做测试&…...

电子烟行业常用的英文表达

1. 电子烟的各种表达 a) 电子烟 i. Electronic-cigarette, ii. Electronic smoke, iii. electronic cigarettes iv. Electric cigarette, v. E-Cigarettes vi. e-cigarette, vii. e-Cig viii. E cigar,e-cigar 电子烟雪茄 2. 电子烟特指词汇及衍生 a) VAPE i. Vapo…...

【SpringMvc 丨跨域】

Spring MVC 支持跨域处理&#xff08;CORS&#xff09;。 CORS 简介处理CORS 过滤器CrossOrigin注解java配置xml配置 主页传送门&#xff1a;&#x1f4c0; 传送 简介 跨域是指在浏览器的同源策略下&#xff0c;不能执行其他网站的脚本。它是由浏览器的安全限制造成的&#xf…...

【C语言】【strlen函数的使用与模拟实现】

1.strlen函数的使用和模拟实现 1.1使用&#xff1a; size_t strlen(const char* str)返回类型为无符号整型&#xff0c;参数是字符指针 计算的是字符串中到“\0"之前的字符个数 1.2模拟实现&#xff1a; 方法一&#xff1a;计数器式遍历 #include<stdio.h> #in…...

类和对象【基础概念】

全文目录 类的定义定义方式 类的访问限定符封装&#xff08;面向对象的三大特性之一&#xff09; 类对象模型类对象的存储方式类对象的大小计算 this指针this指针的特性**this指针可以为空吗&#xff1f;** 类的定义 在C中&#xff0c;C语言中的结构体struct中除了定义变量外还…...

如何测试生成式人工智能(AIGC)

简介&#xff1a;在人工智能日趋普及的今天&#xff0c;生成式人工智能&#xff08;AIGC&#xff09;已经成为不可忽视的一个分支。从自动化生成新闻、编写代码到图像和音频生成&#xff0c;AIGC几乎无处不在。但如何确保这些生成的内容达到预期标准、安全可靠&#xff0c;同时…...

机器学习算法详解3:逻辑回归

机器学习算法详解3&#xff1a;逻辑回归 前言 ​ 本系列主要对机器学习上算法的原理进行解读&#xff0c;给大家分享一下我的观点和总结。 本篇前言 ​ 本篇对逻辑回归的算法原理进行解读。 目录结构 文章目录 机器学习算法详解3&#xff1a;逻辑回归1. 引子2. sigmoid函数3. 原…...

深圳哪些公司做网站/潍坊今日头条新闻最新

表达式中的transition参数的参数值有24中&#xff0c;以代号0-23来表示&#xff0c;分别代表24中显示类型&#xff0c;具体的参数值列表如下所示&#xff1a; 同时还可以参考一下以下的页面转换特效&#xff1a;网页变换效果&#xff08;Trans&#xff09;共分四大类&#xff1…...

阿里云网站怎么备案域名解析/软文推广发布平台

题目 思路 先把A1到An按值从小到大排序假定货舱选在任意一个位置x处&#xff0c;则f(x)f(x)f(x)如上图 一前一后依次给他们分组 若要∣a−x∣∣b−x∣|a-x||b-x|∣a−x∣∣b−x∣取最小值&#xff0c;只有a≤x≤ba≤x≤ba≤x≤b时&#xff0c;最小值为b−ab-ab−a&#xff08;在…...

专做国际时事评论网站/网络营销具有哪些特点

比如像比较简单的关键词“交流”、“心得”并没有可供选择的选项&#xff0c;怎么办&#xff1f;而且输入后按确定也没有用。 解决方法 可以直接在输入后回车&#xff0c;然后确定。 更新20200330 本篇博客的关键词可见&#xff1a;...

房地产行业现状与未来/百度seo优化

物联网因其宏大主题&#xff0c;以及巨大的应用想象空间而备受政府和企业的关注。国际电信联盟 (ITU) 对物联网的定义&#xff1a;“物联网主要解决物品到物品 (Thing to Thing&#xff0c;T2T)&#xff0c;人到物品(Human to Thing&#xff0c;H2T)&#xff0c;人到人 (Human …...

videopro wordpress/百度如何发布作品

Q:我用outlook下载了邮箱里所有的邮件&#xff0c;现在想刻盘保存&#xff0c;我应该保存哪些文件呢&#xff0c;以保证我把光盘内的数据放到其他电脑上还可以用outlook查看我的这些邮件&#xff1f; A:找到你outlook的按装文件&#xff0c;你可以全部刻下来&#xff0c;到后期…...

网站开发制做/谷歌网址

今天讲解的知识点是Arrayadapter这个类&#xff0c;这个是一个适配器&#xff0c;它实现的是Adapter接口&#xff0c;和它类似的有simpleadapter和baseadapter&#xff0c;其中simpleadapter这个类&#xff0c;大家千万不要为它的名字忽悠了&#xff0c;其实这个类的功能非常强…...