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

文章目录

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

线索化

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

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

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

在这里插入图片描述

线索化带来的问题与解决

此时新的问题又产生了：我们如何区分一个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【第三章】《先序线索二叉树查找及总代码》