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

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

文章目录

  • 线索化
  • 线索化带来的问题与解决
  • 结构初始化
  • 创树
  • 先序线索化
  • 往期回顾


线索化

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

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

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

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

线索化带来的问题与解决

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

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

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

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

在这里插入图片描述

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

结构初始化

typedef struct TreeNode 
{char data;struct TreeNode *lchild;struct TreeNode *rchild;int ltag;int rtag;}TreeNode;

这边对比之前中序二叉树就多出这两个东西

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

创树

void createTree(TreeNode** T,char* temp,int* index)
{char ch;ch = temp[*index];(*index)++;if( ch == '#') *T = NULL;else{*T =(TreeNode*)malloc(sizeof(TreeNode));(*T)->data = ch;(*T)->ltag = 0;(*T)->rtag = 0;createTree(&(*T)->lchild,temp,index);createTree(&(*T)->rchild,temp,index);		}
}

先序线索化

我们还是拿这张图
在这里插入图片描述

那么中序二叉树的排序则是
在这里插入图片描述

我们发现,那他与中序线索二叉树的区别只是从“左中右”更改成“中左右而已”

那我们先看之前我们中序线索二叉树是怎么成的

void inThreadTree(TreeNode* T, TreeNode** pre) 
{if(T){inThreadTree(T->lchild,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;inThreadTree(T -> rchild, pre);}
}

那我们先序线索二叉树直接这样子不就行了

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

但是我们我们可以注意到,这样的排序是有问题的,我们仔细思索一下问题出现在哪里

由于我们是先遍历根,然后再去找他左右子树

把思维放宽些,假设我们遍历到节点“D”的时候

*此时的 pre = B 节点的,由于我们的D没有左子树,于是根据下面这个

if(T->lchild == NULL)
{T->ltag = 1;T->lchild = *pre;
}

则B变成D的左子树了

  后面判断后继节点时由于不满足条件,则跳过,再将*pre 赋值为D节点,于是我们继续向下执行

inThreadTree(T->lchild,pre);

​   看出问题没有,由于我们上面的D节点的左孩子已经赋值了,他后面再根据这个进行跳转回B节点,这样子的话就会无限递归了,那这样子我们要怎么解决呢?

​   我们看图知道,我们执行到D节点的时候,应该是不该继续执行inThreadTree(T->lchild,pre)这一段的,执行到B的时候是应该执行的,那么这两者的区别是啥?

B -----> ltag = 0
D -----> ltag = 1

​   于是,我们则可以根据我们之前给他设计的标签来进行判断,我们的inThreadTree(T->lchild,pre)这一段函数应不应该继续执行

最后我们可以得出这个

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

往期回顾

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.【第三章】《中序线索二叉树线索化及总代码》

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



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

相关文章

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