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

数据结构中树、森林 与 二叉树的转换

1 树转换为 二叉树

将树转换成二叉树的步骤是:

  1. 加线。在所有的兄弟结点之间加一条线。
  2. 去线。对于树中的每个结点,只保留它与第一个孩子结点的连线,删除该结点其他孩子结点之间的连线。
  3. 调整。以树的根结点为轴心,将整个树顺时针旋转一定的角度(该结点的第一个孩子是该结点的左孩子,左孩子的兄弟是该结点的右孩子 )

在这里插入图片描述

2 森林转换为二叉树

森林是由若干棵树组成,可以将森林中的每棵树的根结点看作是兄弟,由于每棵树都可以转换为二叉树,所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是:

  1. 先把每棵树转换为二叉树;
  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点,用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换来的二叉树。

在这里插入图片描述

3 二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程,其步骤是:

  1. 加线。若某结点的左孩子结点存在,将该左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点,将该结点与这些右孩子结点用线连接起来;
  2. 去线。删除原二叉树中所有结点与其右孩子结点的连线;
  3. 整理(1)和(2)两步得到的树,使之结构层次分明。

在这里插入图片描述

4 二叉树转换为森林

二叉树转换为森林步骤如下:

  1. 先把每个结点与右孩子结点的连线删除,得到分离的二叉树;
  2. 把分离后的每棵二叉树转换为树;
  3. 整理第(2)步得到的树,使之规范,这样得到森林。

在这里插入图片描述

5 实战演练

5.1 例题1

(2009年408第6题)题目:将森林转换为对应的二又树,若在二又树中,结点 是结点 的父结点的父结点,则在原来的森林中,u和可能具有的关系是

I.父子关系
II.兄弟关系
III.u的父结点与的父结点是兄弟关系

A.只有II
B.I和II
C.I和III
D.I、II和III

解析:
在这里插入图片描述

5.2 例题2

(2014年408第5题)题目:将森林 F 转换为对应的二叉树 T,F 中叶结点的个数等于

A.T中叶结点的个数
C.T中左孩子指针为空的结点个数
B.T中度为 1的结点个数
D.T中右孩子指针为空的结点个数

解析:

在这里插入图片描述

相关文章:

数据结构中树、森林 与 二叉树的转换

1 树转换为 二叉树 将树转换成二叉树的步骤是: 加线。在所有的兄弟结点之间加一条线。去线。对于树中的每个结点,只保留它与第一个孩子结点的连线,删除该结点其他孩子结点之间的连线。调整。以树的根结点为轴心,将整个树顺时针旋…...

力扣labuladong——一刷day43

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣257. 二叉树的所有路径二、力扣129. 求根节点到叶节点数字之和三、力扣199. 二叉树的右视图四、力扣662. 二叉树最大宽度 前言 一般来说,如…...

MapApp 地图应用

1. 简述 1.1 重点 1)更好地理解 MVVM 架构 2)更轻松地使用 SwiftUI 框架、对齐、动画和转换 1.2 资源下载地址: Swiftful-Thinking:https://www.swiftful-thinking.com/downloads 1.3 项目结构图: 1.4 图片、颜色资源文件图: 1.5 启动图片配置图: 2. Mo…...

Java之反射获取和赋值字段

在Java中,反射能够使得代码更加通用,往往用于工具类中。 但常常我们在获取或者赋值反射的属性时,会出现没有赋值成功的结果,往往是由于这个属性在父级中而导致的,这个时候我们就不能用getDeclaredField方法单独获取字段…...

ckplayer自己定义风格播放器的开发记录

CKplayer是一款基于Flash和HTML5技术的开源视频播放器,支持多种格式的音视频播放,并且具有优秀的兼容性和扩展性。 它不仅可以在网页上播放本地或者网络上的视频,还可以通过代码嵌入到网页中,实现更加个性化的播放效果。CKplayer…...

全网最全Django面试题整理(一)

Django 中的 MTV 是什么意思? 在Django中,MTV指的是“Model-Template-View”,而不是常见的MVC(Model-View-Controller)架构。Django的设计理念是基于MTV的 Model(模型) 模型代表数据存取层&am…...

vue统一登录

说明: 统一登录其实就是前端去判断Url地址的token 之后如果有token未过期就直接跳转到首页。 说到浏览器输入url地址,那从浏览器输入地址一共发生了几件事大致如下: DNS解析域名,获取IP地址 --》 建立TCP连接(三次握…...

MVSNet论文笔记

MVSNet论文笔记 摘要1 引言2 相关基础2.1 多视图立体视觉重建(MVS Reconstruction)2.2 基于学习的立体视觉(Learned Stereo)2.3 基于学习的多视图的立体视觉(Learned MVS) 3 MVSNet3.1 网络架构3.2 提取图片…...

大型 APP 的性能优化思路

做客户端开发都基本都做过性能优化,比如提升自己所负责的业务的速度或流畅性,优化内存占用等等。但是大部分开发者所做的性能优化可能都是针对中小型 APP 的,大型 APP 的性能优化经验并不会太多,毕竟大型 APP 就只有那么几个&…...

K8S配置资源管理

这里写目录标题 K8S配置资源管理一.Secret1.介绍2.Secret 有四种类型3.创建 Secret4.使用方式 二.ConfigMap1.介绍2.创建 ConfigMap3.Pod 中使用 ConfigMap4.用 ConfigMap 设置命令行参数5.通过数据卷插件使用ConfigMap6.ConfigMap 的热更新7.ConfigMap 更新后滚动更新 Pod K8S…...

Redis 的集群模式实现高可用

来源:Redis高可用:武林秘籍存在集群里,那稳了~ (qq.com) 1. 引言 前面我们已经聊过 Redis 的主从同步(复制)和哨兵机制,这期我们来聊 Redis 的集群模式。 但是在超大规模的互联网应用中,业务规…...

21、嵌套路由实战操作

1、创建内嵌子路由,你需要添加一个vue文件,同时添加一个与该文件同名的目录用来存放子视图组件。 2、在父组件(.vue)内增加用于显示子视图内容 新建文件 pages\index_id.vue 生成的对应路由 {path: "/",component: _…...

WPF 控件的缩放和移动

WPF 控件的缩放和移动 1.页面代码 <ContentControl ClipToBounds"True" Cursor"SizeAll"><Viewboxx:Name"viewbox"MouseDown"viewbox_MouseDown"MouseMove"viewbox_MouseMove"MouseWheel"Viewbox_MouseWhee…...

Python and和or的优先级实例比较

Python and和or的优先级 and和or都是Python的逻辑运算符&#xff0c;都为保留字。通常情况下&#xff0c;在没有括号影响&#xff0c;and和or的优先级中and在代码的逻辑运算过程中会相对优先一些&#xff0c;及在同一行的Python代码中&#xff0c;and会优先与or执行。下面将通…...

数据结构与算法编程题2

逆置线性表&#xff0c;使空间复杂度为 O(1) #include <iostream> using namespace std;typedef int ElemType; #define Maxsize 100 #define OK 1 #define ERROR 0 typedef struct SqList {ElemType data[Maxsize];int length; }SqList;void Init_SqList(SqList& …...

Java开发者的Python快速进修指南:控制之if-else和循环技巧

简单介绍 在我们今天的学习中&#xff0c;让我们简要了解一下Python的控制流程。考虑到我们作为有着丰富Java开发经验的程序员&#xff0c;我们将跳过一些基础概念&#xff0c;如变量和数据类型。如果遇到不熟悉的内容&#xff0c;可以随时查阅文档。但在编写程序或逻辑时&…...

二进制部署k8s集群-过程中的问题总结(接上篇的部署)

1、kube-apiserver部署过程中的问题 kube-apiserver.conf配置文件更改 2、calico的下载地址 curl https://docs.projectcalico.org/v3.20/manifests/calico.yaml -O 这里如果kubernetes的节点服务器为多网卡配置会产生报错 修改calino.yaml配置文件 解决方法&#xff1a; 调…...

IOS 关于CoreText的笔记

放大 一.CoreText计算attributeString显示所占区域 百度搜索有三种方法&#xff1a; 1.方法 - (CGRect)boundingRectWithSize:(CGSize)size options:(NSStringDrawingOptions)options context:(nullable NSStringDrawingContext *)context 2.使用CTFrameRef 的 CTFrameGetLin…...

基础课6——开放领域对话系统架构

开放领域对话系统是指针对非特定领域或行业的对话系统&#xff0c;它可以与用户进行自由的对话&#xff0c;不受特定领域或行业的知识和规则的限制。开放领域对话系统需要具备更广泛的语言理解和生成能力&#xff0c;以便与用户进行自然、流畅的对话。 与垂直领域对话系统相比…...

Hive常见的面试题(十二道)

Hive 1. Hive SQL 的执行流程 ⾸先客户端通过shell或者Beeline等⽅式向Hive提交SQL语句,之后sql在driver中经过 解析器&#xff08;SQL Parser&#xff09;&#xff1a;将 SQL 字符串转换成抽象语法树 AST&#xff0c;这一步一般都用第三方工具库完成&#xff0c;比如 ANTLR&…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...