数据结构和算法-线索二叉树中的线索化和在线索二叉树中找前驱后继

线索二叉树的概念

在这里插入图片描述
找到某个节点得按照遍历得到的序列开始遍历才能遍历全部节点，非常繁琐
在这里插入图片描述

中序线索二叉树

在这里插入图片描述

线索二叉树的存储结构

在这里插入图片描述

先序线索二叉树

在这里插入图片描述

后序线索二叉树

在这里插入图片描述

三种线索二叉树的对比

即对应前驱后后继判断标准不同
在这里插入图片描述

小结

在这里插入图片描述

二叉树的线索化

在这里插入图片描述

用土办法找中序前驱

当访问到某个节点时先看是否和目标节点一致，一致就保存在final指针中，不一致就更新将当前节点赋值给pre指针。然后依次访问下一个节点

在这里插入图片描述

中序线索化

判断前驱的右孩子和当前节点的左孩子，二者符合条件则连接，然后再更新前驱节点位当前节点
在这里插入图片描述
在这里插入图片描述

王道教材版

pre参数为引用类型，这样才能做到修改变量的值
在这里插入图片描述

先序线索化

此时访问第三个节点后还需遍历左子树，但左孩子已经在visit中被更新为第二个节点，这样又会开始遍历第二个节点，从而陷入反复循环
在这里插入图片描述

多了个判断左孩子

在这里插入图片描述

王道教材版

在这里插入图片描述

后序线索化

不会出现访问节点后再去遍历节点的左孩子
在这里插入图片描述

王道教材版

在这里插入图片描述

小结

在这里插入图片描述

在线索二叉树中找前驱后继

中序线索二叉树找中序后继

在这里插入图片描述

中序线索二叉树找中序前驱

在这里插入图片描述

先序线索二叉树找先序后继

在这里插入图片描述

先序线索二叉树找先序前驱

因为节点的左右孩子都只可能是后继，不用不能通过左右孩子来找前驱。此时需要再加入一个父节点的元素或从头遍历
第三种情况中优先右走，没有右子树则左走
在这里插入图片描述

后序线索二叉树找后序前驱

在这里插入图片描述

后序线索二叉树找后序后继

左右孩子只可能是前驱不可能是后继，所以得加个父节点元素或从头遍历
在这里插入图片描述
第三种情况中优先左走，没有左子树则右走

小结

在这里插入图片描述
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

「Verilog学习笔记」自动贩售机1

「Verilog学习笔记」自动贩售机1

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点，刷题网站用的是牛客网 自动贩售机中可能存在的几种金额：0，0.5，1，1.5，2，2.5，3。然后直接将其作为状态机的几种状…
阅读更多...
13.字符串处理函数——输入输出

13.字符串处理函数——输入输出

文章目录 前言一、题目描述 二、解题 程序运行代码 三、总结 前言 本系列为字符串处理函数编程题&#xff0c;点滴成长&#xff0c;一起逆袭。 一、题目描述 二、解题 程序运行代码 #include<stdio.h> #include<string.h> int main() {char str[10];printf(&q…
阅读更多...
Ubuntu22.04无需命令行安装中文输入法

Ubuntu22.04无需命令行安装中文输入法

概要&#xff1a;Ubuntu22.04安装完成后&#xff0c;只需在设置中点点点即可完成中文输入法的安装&#xff0c;无需命令行。 一、安装中文语言包 1、点击屏幕右上角&#xff0c;如下图所示。 2、点击设置 3、选择地区与语言&#xff0c;点击管理已安装的语言 4、点击安装 5、输…
阅读更多...
nodejs微信小程序＋python＋PHP药品招标采购系统的设计与实现-计算机毕业设计推荐MySQL

nodejs微信小程序＋python＋PHP药品招标采购系统的设计与实现-计算机毕业设计推荐MySQL

目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性&#xff1a;…
阅读更多...
二维码设备安全巡检手指口述应用

二维码设备安全巡检手指口述应用

二维码设备安全巡检手指口述应用 在安全管理中&#xff0c;”手指口述”工作法是通过心想、眼看、手指、口述等一系列行为&#xff0c;对工作过程中的每一道工序进行确认&#xff0c;使“人”的注意力和“物”的可靠性达到高度统一&#xff0c;从而达到避免违章、消除隐患、杜绝…
阅读更多...
JAVA代码优化：记录日志

JAVA代码优化：记录日志

登录中的一条日志记录代码&#xff1a; //异步任务管理器&#xff08;详见文章异步任务管理器&#xff09; //me() 初始化线程池 AsyncManager.me() .execute( //异步工厂记录登录信息 AsyncFactory.recordLogininfor ( //使用者姓名 username, //常量登录失败public static …
阅读更多...
vivado实现分析与收敛技巧8-布局规划技巧

vivado实现分析与收敛技巧8-布局规划技巧

布局规划技巧 对于从未满足时序的设计以及不适合更改网表或约束的设计 &#xff0c; 可考虑采用门级布局规划。 分层布局规划 分层布局规划支持您将一个或多个层级布局在片上某个区域内。此区域可向布局器提供全局层面的指导信息 &#xff0c; 并由布局器执行详细布局。分层…
阅读更多...
BUUCTF 间谍启示录 1

BUUCTF 间谍启示录 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 在城际公路的小道上&#xff0c;罪犯G正在被警方追赶。警官X眼看他正要逃脱&#xff0c;于是不得已开枪击中了罪犯G。罪犯G情急之下将一个物体抛到了前方湍急的河流中&#xff0c;便头一歪突然倒地。警官X接近一看&…
阅读更多...
6.6 Windows驱动开发：内核枚举Minifilter微过滤驱动

6.6 Windows驱动开发：内核枚举Minifilter微过滤驱动

Minifilter 是一种文件过滤驱动&#xff0c;该驱动简称为微过滤驱动&#xff0c;相对于传统的sfilter文件过滤驱动来说&#xff0c;微过滤驱动编写时更简单&#xff0c;其不需要考虑底层RIP如何派发且无需要考虑兼容性问题&#xff0c;微过滤驱动使用过滤管理器FilterManager提…
阅读更多...
人工智能 - 人脸识别：发展历史、技术全解与实战

人工智能 - 人脸识别：发展历史、技术全解与实战

目录 一、人脸识别技术的发展历程早期探索&#xff1a;20世纪60至80年代技术价值点&#xff1a; 自动化与算法化&#xff1a;20世纪90年代技术价值点&#xff1a; 深度学习的革命&#xff1a;21世纪初至今技术价值点&#xff1a; 二、几何特征方法详解与实战几何特征方法的原理…
阅读更多...
20.Oracle11g中的触发器

20.Oracle11g中的触发器

oracle11g中的触发器 一、触发器的概述1、什么是触发器2、触发器的类型3、触发器的组成4、触发器的作用 二、触发器的创建语法1、创建语法2、数据库启动触发器3、 用户登录触发器&#xff1a; 三、对触发器的基本操作点击此处跳转下一节&#xff1a;21.Oracle的程序包(Package)…
阅读更多...
Opencv框选黑色字体进行替换(涉及知识点：selectROI,在控制台输入字体大小,颜色,内容替换所选择的区域)

Opencv框选黑色字体进行替换(涉及知识点：selectROI,在控制台输入字体大小,颜色,内容替换所选择的区域)

import cv2 from PIL import Image,ImageDraw,ImageFont import numpy as npimg_path ../img/ img_clean_path ../img_clean/ name xiao_ben suf .pngimg cv2.imread(img_pathnamesuf) cv2.imshow(original, img)# 选择ROI roi cv2.selectROI(windowName"original&q…
阅读更多...
面试题：项目中如何解决跨域问题（HttpClient、注解、网关）

面试题：项目中如何解决跨域问题（HttpClient、注解、网关）

文章目录 为什么会有跨域问题常见的跨域解决方式网关整合项目中使用Httpclient 为什么会有跨域问题 因为浏览器的同源政策&#xff0c;就会产生跨域。比如说发送的异步请求是不同的两个源&#xff0c;就比如是不同的的两个端口或者不同的两个协议或者不同的域名。由于浏览器为…
阅读更多...
Java毕业设计 SSM SpringBoot vue 夜市摊位管理系统

Java毕业设计 SSM SpringBoot vue 夜市摊位管理系统

Java毕业设计 SSM SpringBoot vue 夜市摊位管理系统 SSM SpringBoot vue 夜市摊位管理系统 功能介绍 首页 图片轮播 通知公告 留言反馈 摊位信息 摊位详情 收藏 评论 赞 踩 登录注册 个人中心 更新信息 我的收藏 大数据夜市摊位统计 系统介绍 后台管理 登录 轮博图管理 通知…
阅读更多...
【STM32】STM32学习笔记-课程简介(01)

【STM32】STM32学习笔记-课程简介(01)

00. 目录 文章目录 00. 目录01. 课程简介02. 硬件设备03. 软件工具04. 硬件套件4.1 面包板和跳线/飞线4.2 杜邦线和STM32最小系统板4.3 STLINK和OLED显示屏4.4 LED和按键4.5 电位器和蜂鸣器4.6 传感器和旋转编码器4.7 USB转串口和MPU60504.8 Flash闪存和电机模块4.9 SG90舵机 0…
阅读更多...
geemap学习笔记015：下载哨兵2号(Sentinel-2)数据

geemap学习笔记015：下载哨兵2号(Sentinel-2)数据

前言 使用GEE下载数据应该是最常见的功能了&#xff0c;今天就介绍一下如何使用geemap下载哨兵2号(Sentinel-2)数据&#xff0c;分别包括自己画感兴趣&#xff0c;以及利用Assets中的shp文件进行下载。 1 自己画感兴趣下载哨兵2号影像 import geemap import eeMap geemap.M…
阅读更多...
c++--类型行为控制

c++--类型行为控制

1.c的类 1.1.c的类关键点 c类型的关键点在于类存在继承。在此基础上&#xff0c;类存在构造&#xff0c;赋值&#xff0c;析构三类通用的关键行为。 类型提供了构造函数&#xff0c;赋值运算符&#xff0c;析构函数来让我们控制三类通用行为的具体表现。 为了清楚的说明类的构…
阅读更多...
百度智能云推出“千帆AI原生应用开发工作台” 助力开发者创新

百度智能云推出“千帆AI原生应用开发工作台” 助力开发者创新

在这个智能互联的世界&#xff0c;每一次技术的飞跃都预示着无限可能。你是否曾梦想&#xff0c;一款产品能够打破创新的边界&#xff0c;让开发不再是高门槛的技术挑战&#xff1f;12月20日&#xff0c;百度云智大会智算大会将为你揭开这幕神秘面纱——“千帆AI原生应用开发工…
阅读更多...
Python中的并发编程

Python中的并发编程

目录 一、引言 二、Python中的线程 1、线程的概念 2、创建线程 3、线程同步和锁 4、线程池 三、Python中的进程 1、进程的概念 2、创建进程 四、Python中的异步IO 1、异步IO的概念 2、异步IO的实现 3、异步IO的并发执行 五、总结 一、引言 并发编程是一种计算机…
阅读更多...
消息中间件——RabbitMQ（七）高级特性 2

消息中间件——RabbitMQ（七）高级特性 2

前言 上一篇消息中间件——RabbitMQ&#xff08;七&#xff09;高级特性 1中我们介绍了消息如何保障100%的投递成功&#xff1f;,幂等性概念详解,在海量订单产生的业务高峰期&#xff0c;如何避免消息的重复消费的问题&#xff1f;,Confirm确认消息、Return返回消息。这篇我们…
阅读更多...
最新文章

Copyright @ 2022~2023