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

作者：正经夜光杯 | 2024-06-20 13:25:25

踩

问题

我们的二叉树学到现在，会产生两个问题：

在n个结点的二叉树中，必定有n+1个空链域（叶子结点的左右子树空间浪费了）

怎么得出n+1个节点的呢？

我们每个节点有2n个指针（左右子树）

我们有 n - 1 个节点

所以我们空闲的节点数是 2n - (n-1) = n+1个节点

二叉树的遍历，无论是递归还是非递归算法，效率都不算高。
那我们能不能利用原本浪费掉的空间，来解决第二个问题呢？

倘若对下图二叉树进行中序遍历，可以得到1、3、6、8、10，我们可以知道3的前驱结点为1，后驱结点为6。但是，这种关系的建立是在完成遍历后得到的，那么，**可不可以在建立二叉树的同时记录下前驱后继的关系，**这样我们在寻找前驱后继结点时的效率将会大大提升！

在这里插入图片描述

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

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

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

在这里插入图片描述

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

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

ltag==0，指向左孩子；ltag==1，指向前驱结点
rtag==0，指向右孩子；rtag==1，指向后继结点
1
2

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

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/739938