线索二叉树

线索二叉树：
对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉链表一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n+1个空指针域。这些空间不存储任何数据，浪费内存。
我们在做遍历时，比如下图中的二叉树，其中序遍历结果为BDAC，这样我们可以知道每个结点的前驱和后继。可是这是建立在已经遍历过的基础之上的，在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次，以后每次需要知道时，都需要遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢，可以节省很多时间。
经过分析，我们可以考虑利用那些空指针域，存放指向某结点在某种遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉树称为线索链表，相应的二叉树就称为线索二叉树

二叉树
将上图中的二叉树进行中序遍历后，即BDAC，将所有的空指针域中的rchild改为指向它的后继结点，而空指针域中的lchild改为指向它的前驱结点，如下图所示。
线索二叉树
其实线索二叉树，等于是把一棵二叉树变成了一个双向链表，这样对我们的插入、删除结点都带来了方便。，所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
双向链表
不过问题并没有解决，我们如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是后继？我们在每个结点增设两个标志域ltag和rtag（bool)，结点结构如下图所示。
结点
其中，ltag为0时指向该结点的左孩子，为1时指向该结点的前驱
rtag为0时指向该结点的右孩子，为1时指向该结点的后继，对于上图中的线索二叉树可以修改如下：
修改后的线索二叉树
线索化的实质就是将二叉链表中的空指针改为指向前驱或者后继的线索，由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
有了线索二叉树以后，我们对它遍历时发现，其实就等于操作一个双向链表。添加一个头结点，令其lchild的指针指向二叉树的根结点，rchild指向中序遍历时的最后一个结点，反之，令二叉树的中序序列中的第一个结点的lchild和最后一个结点的rchild与均指向头结点。这样操作的好处是我们既可以从第一个结点顺着后继遍历，也可以从最后一个结点顺着前驱遍历。
增加了头结点的线索二叉树
如果所用的二叉树需要经常遍历或者查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是非常不错的选择。