如何将线索二叉树的中序线索化操作改写成长尾？

本文共计2210个文字，预计阅读时间需要9分钟。

为什么研究二叉搜索树？

当我们用二叉链表作为二叉树的存储结构时，可以很方便地找到某个节点的左右孩子；但在某些情况下，无法直接找到节点在某种遍历顺序序列中的前驱和后继。

为什么要研究线索二叉树？

当我们用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

利用二叉链表中的空指针域：

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继。

——这种改变指向的指针称为线索，加上了线索的二叉树称为线索二叉树（Threaded Binary Tree）。

对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

为区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域LTag和RTag，并约定：

LTag=0,lchild指向该结点的左孩子；

LTag=1，lchild指向该结点的前驱；

RTag=0,rchild指向该结点的右孩子；

RTag=1，rchild指向该结点的后继。

线索二叉树的目的，是为了直观的表示出某结点的前驱和后继。如果每个结点的前驱或后继都能确定，则对二叉树的遍历就会变得非常简单，一条循环语句即可完成：

for (p=First(T);p!=NULL;p=succ(p))

Visit(p);

二叉链表中，直观的表示出了某结点左右孩子的信息。