文章目录
问题
我们的二叉树学到现在，会产生两个问题：
在n个结点的二叉树中，必定有n+1个空链域（叶子结点的左右子树空间浪费了）
怎么得出n+1个节点的呢？
我们每个节点有2n个指针（左右子树）
我们有 n - 1 个节点
所以我们空闲的节点数是 2n - (n-1) = n+1个节点
二叉树的遍历，无论是递归还是非递归算法，效率都不算高。
那我们能不能利用原本浪费掉的空间，来解决第二个问题呢？
倘若对下图二叉树进行中序遍历，可以得到1、3、6、8、10，我们可以知道3的前驱结点为1，后驱结点为6。但是，这种关系的建立是在完成遍历后得到的，那么，**可不可以在建立二叉树的同时记录下前驱后继的关系，**这样我们在寻找前驱后继结点时的效率将会大大提升！
线索化
我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 。
现将某结点的空指针域指向该结点的前驱后继，定义规则如下：
若结点的左子树为空，则该结点的左孩子指针指向其前驱结点
若结点的右子树为空，则该结点的右孩子指针指向其后继结点
这种指向前驱和后继的指针称为线索，将一棵普通的二叉树以某种次序遍历，并添加线索的过程称为线索化
线索化带来的问题与解决
此时新的问题又产生了：我们如何区分一个lchild指针是指向左孩子还是前驱结点呢？
为了解决这个问题，我们需要添加标志位ltag和rtag,并定义以下规则
ltag==0，指向左孩子；ltag==1，指向前驱结点
rtag==0，指向右孩子；rtag==1，指向后继结点
线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树的时候才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
往期回顾
1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
