【数据结构】唯一确定一个二叉树的方法

2023-11-13

唯一确定一棵二叉树的方法

​ 在了解以何种方式能唯一确定一棵二叉树之前,需要先认识树的遍历方式有哪几种。

树的遍历方式

  1. 先序遍历
  2. 后序遍历
  3. 层序遍历

二叉树的遍历方式

  1. 先序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层序遍历

确定的方式

那么如何唯一确定一棵二叉树呢?这就需要结合二叉树的遍历方式来进行,主要有以下两种方式:

  1. 二叉树的先序遍历+中序遍历
  2. 二叉树的后序遍历+中序遍历

在记忆这两种方式时,为了避免混淆,可以这样记忆:由于中序遍历是二叉树特有的遍历方式,所有唯一确定一棵二叉树的每一种方式中必有一个是中序遍历,而剩下的那一种就要么是先序遍历,要么是后序遍历。

现假设存在一棵二叉树,其先序、中序和后序遍历的结果如下:

  1. 先序遍历:ABDEGCFH
  2. 中序遍历:DBGEACFH
  3. 后序遍历:DGEBHFCA

在介绍如何利用遍历方式唯一确定一棵二叉树之前,需要重点强调:

无论利用什么方式来唯一确定一棵二叉树,其本质都是通过两种遍历结果来不断递归地确定根结点和划分左右子树的过程!

先序遍历+中序遍历

先序遍历+中序遍历的要义是:利用先序遍历确定根结点,再利用中序遍历划分左右子树

步骤一:分析整棵二叉树

对于先序遍历,其遍历方式是一个结点需要先访问自己,再访问其左子树,接着才是其右子树,故先序遍历结果中的第一个元素一定是根结点,根据上述先序遍历可以知道是A。

​ 接着利用得到的A,在中序遍历结果中找到A所在的位置,然后便可以将A左侧的所有元素归属到根结点的左子树,A右侧的所有元素归属到根结点的右子树,而之所以这样做,是因为对于中序遍历,其遍历方式是一个结点先访问其左子树,再访问自己,接着才是其右子树,所以A前面的元素一定来自A的左子树,A后面的一定来自A的右子树。

​ 根据上述分析,可以先画出如下图片:

在这里插入图片描述

步骤二:分析A的左子树,即包含DBGE的这棵二叉树。

这时可以把包含DBGE这四个元素的先序遍历部分和中序遍历部分单独提取出来:

  1. 部分先序遍历:BDEG
  2. 部分中序遍历:DBGE

现在单独观察包含DBGE的这棵树和它对应的部分先序遍历、部分中序遍历,可以看到接下来的分析方式又与步骤一是一模一样的了,即先确定这个树(仅包含DBGE的这棵树)的根结点,再确定它的两棵子树,现在根结点是部分先序遍历的第一个元素,即B,根据B,在部分中序遍历中划分左右子树,即左子树包含D,右子树包含GE,得到的图片如下:

在这里插入图片描述

可以看到这时B的左子树只有一个结点,所以可以认为已经确定好了,那么就只需要按照步骤一的方式对B的右子树进行同样的分析即可。

步骤三:分析A的右子树,即包含CFH的这颗二叉树。

这时可以把包含CFH这三个元素的先序遍历部分和中序遍历部分单独提取出来:

  1. 部分先序遍历:CFH
  2. 部分中序遍历:CFH

现在单独观察包含CFH的这棵树和它对应的部分先序遍历、部分中序遍历,可以看到接下来的分析方式又与步骤一是一模一样的了,即先确定这个树(仅包含CFH的这棵树)的根结点,再确定它的两棵子树,现在根结点是部分先序遍历的第一个元素,即C,根据C,在部分中序遍历中划分左右子树,即左子树为空,右子树包含FH,得到的图片如下:

在这里插入图片描述

可以看到这时B的左子树没有一个结点,所以可以认为已经确定好了,那么就只需要按照步骤一的方式对C的右子树进行同样的分析即可。

步骤四:得到一颗完整的二叉树。

根据上述步骤,完整地走一遍流程,便可以得到如下的一棵二叉树:

在这里插入图片描述

后序遍历+中序遍历

后序遍历+中序遍历的要义是:利用后序遍历确定根结点,再利用中序遍历划分左右子树

其实后序遍历+中序遍历唯一确定一棵二叉树的方法与先序遍历+中序遍历唯一确定一棵二叉树的方法本质上是一样的,唯一不同在于,利用后序遍历+中序遍历唯一确定一棵二叉树的方法在每次确定根结点时,需要对后序遍历的结果从后往前看,比如对于上述例子中的后序遍历:DGEBHFCA,第一步确定根结点时,需要取最后一个元素,因为后序遍历是最后才访问根结点,所以此时根结点的位置就是最后一个,而其他步骤就与先序遍历+中序遍历唯一确定一棵二叉树的方法是一样的了。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

【数据结构】唯一确定一个二叉树的方法 的相关文章

  • javaweb之MVC购物车(加入购物车,订单,订单详情)

    MVC Model View Controller 是软件工程中的一种软件架构模式 它把软件系统分为模型 视图和控制器三个基本部分 用一种业务逻辑 数据 界面显示分离的方法组织代码 将业务逻辑聚集到一个部件里面 在改进和个性化定制界面及用户

随机推荐

  • Scala学习路线

    本文是类比Java基础知识的 Scala学习笔记 1 Scala基础 1 Scala一些基础知识 https blog csdn net hzp666 article details 114842022 2 控制结构 if判断 https
  • 自然人税收管理系统服务器,【轻松学个税申报】自然人税收管理系统客户端操作...

    2018年8月1日个人所得税代扣代缴申报软件 自然人税收管理系统客户端正式上线 新的软件在界面 操作方法 实现功能等较多变化 为了大家能够熟练操作与应用 从今天起开始为大家带来自然人税收管理系统客户端操作应用 今天我们先来说一说新建帐户 一
  • 小学生Python编程 —— 欢乐钢琴

    孩子的又一作品 欢乐钢琴 from pgzrun import WIDTH 960 HEIGHT 720 o 0 name s song Actor name str o png 480 180 a press False 动效函数 def
  • sublime text3下搭建Python IDE--Anaconda插件(自动补全)

    今天自己想在sublime text3下装个python自动补全插件 当安装一个包管理器时 Package Contral 时 ctrl shift p输入Install Package时 总是报错说没有这个包 在网上也找了很多解决办法 有
  • Android Apache安装及局域网手机无法访问解决办法

    Android Apache安装及局域网手机无法访问解决办法 Apache是一款常用的开源Web服务器软件 可以在Android设备上安装并提供Web服务 本文将介绍如何在Android设备上安装Apache 并提供解决方案以解决在同一局域
  • 代码静态分析工具——splint的学习与使用

    引言 最近在项目中使用了静态程序分析工具PC Lint 体会到它在项目实施中带给开发人员的方便 PC Lint是一款针对C C 语言 windows平台的静态分析工具 FlexeLint是针对其他平台的PC Lint版本 由于PC Lint
  • ResNet简介

    ResNet Residual Network 此网络于2015年 国人何先生提出 用于解决随着深度学习的层数加深造成的网络退化现象和梯度消失 梯度爆炸 问题1 退化现象 当深度学习的各项指标能够随着训练轮数收敛的情况下 网络的层数增强未能
  • 深度学习车辆检测实现自动驾驶

    在本文中 我将通过一个车辆检测示例演示如何使用深度学习创建目标检测器 相同的步骤可用于创建任何目标探测器 我经常有朋友和同事问我自动驾驶系统如何感知周围的环境并做出 人类 的决定 目标检测是指对图像和视频中的目标进行定位和分类 下图显示了一
  • MySQL体系结构及数据库在Linux的部署

    数据库 存储数据的仓库 是长期存放在计算机内 有组织 可共享的大量数据的集合 数据库中的数 据按照一定数据模型组织 描述和存储 具有较小的冗余度 较高的独立性和易扩展性 并为各种用户共享 先来看看MySQL的体系架构图 可以看出MySQL的
  • 关于串口通信协议的解析,该怎么解决

    关于串口通信协议的解析 该怎么解决 串口通信协议 由于本系统采用非规范式输入 导致一帧数据可能分成几次接收 为了能够判断一帧数据是否接收完整 本系统制定了一套特殊的串口通信协议 如附图所示 附图 通信协议定义 在本系统的串口通信协议中 一帧
  • sql sever2008 R2 检测到索引可能已损坏。请运行 DBCC CHECKDB。

    1 设置成单用户状态 USE MASTER ALTER DATABASE DBNAME SET SINGLE USER GO DBNAME为修复的数据库名 2 执行修复语句 检查和修复数据库及索引 dbcc checkdb DBNAME R
  • 【pip】彻底解决 module ‘tensorflow‘ has no attribute ‘random_normal‘

    翻译 tensorflow显示没有random normal模块 解决 将代码中的 tf random normal 用tf random normal代替 区分 与
  • [leetcode]python3 算法攻略-回文链表

    请判断一个链表是否为回文链表 方案一 指针法 class Solution def isPalindrome self head 判断一个链表是否是回文的 很自然的想法就是两个指针 一个指针从前往后走 一个指针从后往前走 判断元素值是否相同
  • mysql读写分离与监控的使用(proxysql)

    os rhel 7 3 mysql 5 7 proxysql 1 4 15 1 ip 规划如下 172 25 11 1 node1 proxysql 172 25 11 2 node2 mysql master 172 25 11 3 no
  • 对于解决Visual Studio中scanf函数报错的原因及解决方法

    对于C语言初学者 可能会用到devC 或者是visual studio软件 我本人是比较推荐visual studio软件的 毕竟这个软件使用起来功能比devc 软件功能更多 而初学者在使用visual studio软件时会发现在使用初始的
  • Unity-委托2种常用使用场景总结

    委托使用场景1 调用委托 可以分发多个方法出去 举例 定义多个通知不同人的信息 例如经理 员工 客户 可以针对性的制定不同的通知 调用委托 可以一次性的群发给他们 委托使用场景2 方法的参数是个方法 例如按钮方法 参数是一个点击事件的方法
  • 麦克灵敏度调整

    1 先看MIC电路连接 这是个差分输入的例子 MICP2和MICN2是一对差分信号 经过C156的滤波 输入到MIC两端 MIC两引脚分别是到地和供电 上图的R177参数就关系到MIC输入的灵敏度 2 电阻R177影响灵敏度分析 MICBI
  • C++中函数返回引用

    1 返回引用和不返回引用的区别 下面两个代码是在类中的成员函数 而m data 变量为类的私有成员变量 int at return m data int at return m data 上面两个函数 第一个返回值是int的引用int 第二
  • Log Structured Merge Trees(LSM) 原理

    Log Structured Merge Trees LSM 原理 十年前 谷歌发表了 BigTable 的论文 论文中很多很酷的方面之一就是它所使用的文件组织方式 这个方法更一般的名字叫 Log Structured Merge Tree
  • 【数据结构】唯一确定一个二叉树的方法

    唯一确定一棵二叉树的方法 在了解以何种方式能唯一确定一棵二叉树之前 需要先认识树的遍历方式有哪几种 树的遍历方式 先序遍历 后序遍历 层序遍历 二叉树的遍历方式 先序遍历 中序遍历 后序遍历 层序遍历 确定的方式 那么如何唯一确定一棵二叉树