数据结构 之 线索二叉树(七)

提示:本篇主要讲解线索二叉树的基本概念和二叉树、树,森林之间的转换

文章目录

  • 线索二叉树基本概念
  • 线索二叉树类型定义
  • 线索二叉树的基本概念
  • 中根线索二叉树
  • 树向二叉树的转换
  • 森林转换二叉树
  • 树和森林的遍历(知道即可)


线索二叉树基本概念

`提示:【问题】有n个结点的二叉链表中,有( )个指针域被闲置。

所以可以利用这些空闲的指针域:
当某结点无左孩子时,令其左指针指向它的前趋结点;
当该结点无右孩子时,令其右指针指向它的后继结点。

线索:指向前驱或后继结点的指针称为线索。

为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点, 需在原结点结构中增加两个标志域。 因此二叉链表的结点结构可重新定义为:
在这里插入图片描述

线索二叉树类型定义

struct thrnode {  int  data;struct  thrnode  *lchild , *rchild;int Ltag,Rtag; /* 左、右标志域 */};

对二叉树以某种次序进行遍历并且加上线索的过程称为线索化。经过线索化后生成的二叉链表称为线索二叉树

根据遍历的顺序,线索二叉树可以分为

  1. 前序线索二叉树
  2. 中序线索二叉树
  3. 后序线索二叉树

线索二叉树的基本概念

在这里插入图片描述

中根线索二叉树

在这里插入图片描述
中根遍历序列:DBGEACF

树向二叉树的转换

方法:树中结点的孩子放在二叉树的左子树中,树中结点的兄弟放在二叉树的右子树中,简而言之就是,左孩子右兄弟。

转换步骤:
(1)在兄弟节点之间连一条线;
(2)每个结点仅保留其与最左孩子之间的连线,其余连线删除;
(3)以根为轴心将整棵树顺时针旋转45度。

树向二叉树的转换如图所示:
在这里插入图片描述

那么问题来了,思考:如何将一棵二叉树还原成树?

还原步骤如下:
(1)将二叉树中的根结点与其右孩子间的连线,及沿右分支搜索到的所有右孩子间的连线全部抹掉,使之变成孤立的二叉树;
(2)根据左孩子右兄弟法则,进行连接,结果下图所示。
(3) 逆时针旋转45°。

森林转换二叉树

可以看出这和树向二叉树的转换相同,只不过最后把多个二叉树合并成了一个而已,遵循的规则还是左孩子右兄弟原则.

树和森林的遍历(知道即可)

结论:
树的先根遍历序列与其转换后对应的二叉树的先根遍历序列序列相同。
树的后根遍历序列与其转换后对应的二叉树的中根遍历序列相同。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/49.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

二十九、Python基础语法(继承-上)

一、概念介绍 继承:继承描述的是类与类之间的关系,集成之后子类对象可以直接使用父类中定义的方法的属性,可以减少代码冗余,提高编码效率。 二、继承语法 三、继承例子 # 定义一个父类 Animal class Animal:def __init__(self,…

arcgis坐标系问题

2000数据框的工程只能打开2000坐标系的矢量数据和栅格数据(影像图),如果打开80的数据则会投影错误,出现较大偏差。 解决方案:80数据框打开80数据,2000数据库打开2000数据。

Java基础05

目录 一、引入 插入方法currentTimeMillis()的介绍 二、详细介绍 1.String 2.StringBuilder ①StringBuilder与String的区别 ②StringBuilder的常用方法 3.StringBuffer 拓展(缓冲区) 三、对比 1.⭐String,StringBuffer&#xff0c…

033_Structure_Static_In_Matlab求解结构静力学问题两套方法

结构静力学问题 静力学问现在是已经很简单的问题,在材料各向同性的情况下,对于弹性固体材料,很容易通过有限元求解。特别是线弹性问题,方程的矩阵形式可以很容易的写出(准确得说是很容易通过有限元表达)&a…

Zabbix Agent端安装部署

文章目录 1. 功能概述2. 版本说明3. Agent安装说明4. Agent2安装说明 Zabbix Agent是Zabbix监控系统中的一个重要组件,它部署在被监控的目标主机上,负责收集主机的各类数据(如性能指标、日志信息等),并将这些数据发送到…

C#/WinForm 鼠标穿透自定义区域截图(后续实现录屏)

效果 窗体截图录屏 git地址:https://gitee.com/feng-cai/screenshot-recording

Golang文件操作

1.文件介绍:文件是数据源,主要作用是保存数据 2.文件在程序中是以流的形式来操作的 对文件的操作主要用File(os包)结构体来实现 文件的基本操作 1)打开一个文件进行读操作: os.Open(name string)(*File,error) 2)关…

8. 数据结构——邻接表、邻接矩阵的基本操作

一、邻接表 1. 内容 2. 实现代码(直接可以复制使用) //邻接表的相关操作 #include<bits/stdc.h> #define MVnum 100 #define OK 1 #define ERROR -1 using namespace std;typedef int Status; typedef char VerTexType; //假设顶点的数据类型为char typedef int ArcT…

【问题记录】当机器人存在多个串口需要绑定时udevadm的作用

一、正常绑定 输入sudo udevadm info -a /dev/ttyUSBx | grep KERNELS 命令 会出现KERNELS的编号&#xff0c;记录编号。 修改规则文件/etc/udev/rules.d/99-usb.rules 添加以下命令 KERNEL"ttyUSB*", KERNELS"2-1.2:1.0", MODE:"0666", GROU…

快消品行业数字化转型:定制开发 S2B2C 商城小程序的主战场选择与突破

摘要&#xff1a;在快消品行业数字化转型的背景下&#xff0c;企业内部各部门虽积极尝试数字化但效果欠佳&#xff0c;核心问题在于数字化规模小难以实现企业整体转型&#xff0c;快消品龙头企业更为突出。定制开发 21 链动模式 S2B2C 商城小程序为解决这一问题提供了新途径。该…

Windows、Linux系统上进行CPU和内存压力测试

CPU和内存压力测试 1. Linux环境 Linux环境下&#xff0c;我们可以用 stress 工具进行内存、CPU等的压力测试。 【1】. stress工具说明 [kalamikysrv1 ~]$ stress --help stress imposes certain types of compute stress on your systemUsage: stress [OPTION [ARG]] ...-…

STM32使用串口下载程序

STM32使用串口下载程序 FluMcu软件下载地址 单片机在线编程网 STM32 MCU启动模式配置(Boot Configuration) 单片机复位后&#xff0c;SYSCLK的第4个上升沿&#xff0c;BOOT引脚上的值将锁存&#xff0c;用户可以通过设置BOOT0和BOOT1引脚的值&#xff0c;来选择复位后的启动…

每天五分钟深度学习pytoroch:基于pytorch搭建逻辑回归算法模型

本文重点 前面我们学习了线性回归模型的搭建,无论是基于pytorch还是不基于pytorch,以上的模型都是回归模型,本文我们将使用pytorch搭建逻辑回归模型,逻辑回归模型是一个经典的分类问题。 模型搭建 class LogisticRegression(nn.Module) : def __init__(self) :super (Lo…

Mybatis-18.动态SQL-sqlinclude

一.sql&include 为什么需要<sql>和<include>标签&#xff1f; 这是因为这些代码是重复的&#xff0c;能够消除重复会提高代码的可读性和效率。 那我们就可以使用<sql>标签对这些片段进行一个抽取。然后在原来抽取的地方再将这个<sql>片段引用进来。…

探索开源MiniMind项目:让大语言模型不再神秘(1)

简介&#xff1a; 声明&#xff1a;本人非此项目作者&#xff0c;仅仅是探索项目&#xff0c;分享项目。如有不妥&#xff0c;请联系我删除&#xff01; 原项目地址&#xff1a;GitHub - jingyaogong/minimind: 「大模型」3小时完全从0训练26M的小参数GPT&#xff0c;个人显卡即…

HTML 基础标签——文本内容标签 <ul>、<ol>、<blockquote> 、<code> 等标签的用法详解

文章目录 1. 标题标签2. 段落标签3. 文本格式化标签4. 列表标签4.1 无序列表 `<ul>`4.2 有序列表 `<ol>`5. 引用标签5.1 块引用 `<blockquote>`5.2 行内引用 `<q>`5.3 作品引用 `<cite>`6. 代码和预格式文本标签6.1 代码标签 `<code>`6.2 …

qt QMenuBar详解

1、概述 QMenuBar是Qt框架中用于创建菜单栏的类&#xff0c;它继承自QWidget。QMenuBar通常位于QMainWindow对象的标题栏下方&#xff0c;用于组织和管理多个QMenu&#xff08;菜单&#xff09;和QAction&#xff08;动作&#xff09;。菜单栏提供了一个水平排列的容器&#x…

GenAI 生态系统现状:不止大语言模型和向量数据库

自 20 个月前 ChatGPT 革命性的推出以来&#xff0c;生成式人工智能&#xff08;GenAI&#xff09;领域经历了显著的发展和创新。最初&#xff0c;大语言模型&#xff08;LLMs&#xff09;和向量数据库吸引了最多的关注。然而&#xff0c;GenAI 生态系统远不止这两个部分&#…

聪明的你能从千门八将108局学到什么,对你的未来人生有哪些深远的影响?

千门八将108局&#xff1a;智慧的启迪与人生指引 在古老智慧的宝库中&#xff0c;千门八将108局犹如璀璨星辰&#xff0c;闪耀着神秘而深邃的光芒。那些认真钻研过这些局的人&#xff0c;仿佛经历了一场穿越时空的智慧洗礼&#xff0c;从中收获了无价的人生财富。 一、从千门八…

GraphQL 与 Elasticsearch 相遇:使用 Hasura DDN 构建可扩展、支持 AI 的应用程序

作者&#xff1a;来自 Elastic Praveen Durairaju GraphQL 提供了一种高效且灵活的数据查询方式。本博客将解释 Hasura DDN 如何与 Elasticsearch 配合使用&#xff0c;以实现高性能和元数据驱动的数据访问。 此示例的代码和设置可在此 GitHub 存储库 - elasticsearch-subgraph…