从零开始学数据结构系列之第三章《后续线索二叉树线索化理论》

本文主要是介绍从零开始学数据结构系列之第三章《后续线索二叉树线索化理论》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 线索化
  • 线索化带来的问题与解决
  • 后续线索化
  • 查找首节点
  • 往期回顾


线索化

我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 。

现将某结点的空指针域指向该结点的前驱后继,定义规则如下:

若结点的左子树为空,则该结点的左孩子指针指向其前驱结点
若结点的右子树为空,则该结点的右孩子指针指向其后继结点这种指向前驱和后继的指针称为线索,将一棵普通的二叉树以某种次序遍历,并添加线索的过程称为线索化

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

线索化带来的问题与解决

此时新的问题又产生了:我们如何区分一个lchild指针是指向左孩子还是前驱结点呢?

为了解决这个问题,我们需要添加标志位ltag和rtag,并定义以下规则

ltag==0,指向左孩子;ltag==1,指向前驱结点
rtag==0,指向右孩子;rtag==1,指向后继结点

在这里插入图片描述
  线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树的时候才能得到,所以线索化的过程就是在遍历的过程中修改空指针的过程。

在这里插入图片描述

我们会中序线索二叉树的话,基本也会后续两个二叉树的,原理其实差不多的
就例如创树和结构初始化都是一样的

后续线索化

在这里插入图片描述
  我们继续还是用这个图,我们根据前面学习的中序线索二叉树和先序线索二叉树,来看看着后续线索二叉树怎么写

​ 我们再看到中序线索二叉树是怎么写的,看看稍微修改下直接用行不行

void inThreadTree(TreeNode* T, TreeNode** pre) 
{if(T){	inThreadTree(T->lchild,pre);inThreadTree(T -> rchild, pre);if(T->lchild == NULL){T->ltag = 1;T->lchild = *pre;}if(*pre != NULL && (*pre)->rchild == NULL){(*pre)->rtag = 1;(*pre)->rchild = T;}*pre = T;}
}

我们看一下这个有没有坑

答案是没有的,可以直接正常运行的,那我们接下来看看下面的是否可以直接用

查找首节点

​ 这是我们中序线索二叉树写的

/* 找到最左的节点数 */
TreeNode* getFirst(TreeNode* T) 
{while (T -> ltag == 0)T = T -> lchild;return T;}

  仔细想想,我们中序遍历这个是 左 右 中,而我们这个先序遍历是直接寻找最左边的节点,所以我们以防万一下图这种情况

在这里插入图片描述
  如果是这种情况,我们想上述的代码是不能有效的完成工作的,所以我们需要一些简单的修改

/* 找到最左的节点数 */
TreeNode* getFirst(TreeNode* T) 
{while (T -> ltag == 0)T = T -> lchild;if(T -> rtag == 0)getFirst(T -> rchild);return T;
}

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》

这篇关于从零开始学数据结构系列之第三章《后续线索二叉树线索化理论》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1074461

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr