线索二叉树基本操作详解
线索二叉树基本操作详解巧若拙（欢迎转载，但请注明出处：http://blog.）
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序，中序或后序序列。这实际上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是，当以二叉链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只能在遍历的动态过程中才能得到。
因为在有n个结点的二叉链表中必定存在n+1个空链域，故可以利用这些空链域来存放结点的前驱和后继信息。
试做如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，需要改变结点结构，增加两个标志域：LTag，RTag。
其中：LTag = 0，lchild域指示其左孩子； LTag = 1，lchild域指示其前驱。
RTag = 0，rchild域指示其右孩子； RTag = 1，rchild域指示其后继。
以这种结点组成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树以某种次序遍历使其变成线索二叉树的过程叫做线索化。
在线索二叉树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直到其后继为空为止；当然也可以找结点的前驱，进行逆序遍历。
求各种次序线索树非叶子结点的前驱和后继的方法：
前序线索树非叶子结点p的前驱：p的双亲结点；
前序线索树非叶子结点p的后继：若p有左孩子，则后继为其左孩子，否则后继是其右孩子。
后序线索树非叶子结点p的前驱：若p有右孩子，则后继为其右孩子；否则后继是其左孩子。
后序线索树非叶子结点p的后继：若p为根结点，则其后继为空；若p为其双亲结点的右孩子，或p为左孩子且其双亲结点无右孩子，则p的后继为其双亲结点；
若p为左孩子，且其双亲结点有右孩子，则其后继为双亲结点右子树的第一个结点（最左边结点）。
中序线索树非叶子结点p的前驱：左子树的最后一个结点（最右边的结点）。
中序线索树非叶子结点p的后继：右子树的第一个结点（最左边结点）。
前序线索树的后继很好找，但前驱是双亲结点，不便查找；虽然中序线索树前驱和后继都不是直接指向，但不需要求双亲，查找还是比较方便的；后序线索树的前驱很好找，但是后继需要分类讨论，情况复杂，而且需要求双亲。综合考虑，中序线索树是最佳的选择。
为了方便起见，我们仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
我们先来分析如何将一颗普通二叉树改造成线索二叉树。因为普通二叉树没有头结点，故我们需要先创建一个头结点，然后对原二叉树做中序线索化处理。
/*
函数名称：InOrderThreading
函数功能：创建头结点，并将二叉树改造成中序线索树
输入变量：BiThrTree T：指向原二叉树根结点的指针
输出变量：BiThrTree：指向中序线索树头结点的指针
*/
BiThrTree InOrderThreading(BiThrTree T)
{
BiThrTree Thrt, pre;
Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); //建立头结点
if (!Thrt)
{
printf("Out of space!");
exit(0);
}
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指
if (! T)//若二叉树为空，则左指针回指
{
Thrt->lchild = Thrt;
}
else
{
Thrt->lchild = T;
pre = Thrt;
InThreading_2(&T, &pre);//中序线索化
pre->rchild = Thrt; //最后一个结点线索化，此时pre指向最后一个结点
pre->RTag = Thread;
Thrt->rchild = pre;
}
return Thrt;
}
中序线索化二叉树和中序遍历二叉树算法非常相似，也有递归和非递归有两种算法。代码如下。
/*
函数名称：InThreading_1
函数功能：中序遍历二叉树，并将其中序线索化（递归算法）
输入变量：BiThrTree *p：指向二叉树当前结点指针的指针
BiThrTree *pre：指向二叉树树当前结点的前驱结点指针的指针
输出变量：无
*/
void InThreading_1(BiThrTree *p, BiThrTree *pre)
{
if (*p != NULL)
{
InThreading(&(*p)->lchild, pre); //左子树线索化
if ((*p)->lchild == NULL) //若当前结点的左子树为空，则建立前驱线索
{
(*p)->LTag = Thread;
(*p)->lchild = (*pre);
}
else
{
(*p)->LTag = Link;
}
if (*pre != NULL && (*pre)->rchild == NULL) //若前驱结点的右子树为空，则建立后继线索
{
(*pre)->RTag = Thread;
(*pre)->rchild = *p;
}
*pre = *p; //中序遍历结点，保持pre指向p的前驱
(*pre)->RTag = Link;//默认前驱结点右孩子非空
InThreading(&(*p)->rchild, pre); //右子树线索化
}
}
/*
函数名称：InThreading_2
函数功能：中序遍历二叉树，并将其中序线索化（非递归算法）
输入变量：BiThrTree *p：指向二叉树当前结点指针的指针
BiThrTree *pre：指向二叉树树当前结点的前驱结点指针的指针
输出变量：无
*/
void InThreading_2(BiThrTree *root, BiThrTree *pre) //中序遍历二叉树，并将其中序线索化（非递归算法）
{
BiThrTree stack[MAXSIZE];
BiThrTree p = *root;
int top = -1;
while (p != NULL || top >= 0)
{
if (p != NULL) //先处理左子树
{
stack[++top] = p;
p = p->lchild;
}
else
{
p = stack[top--];
//线索化当前结点及其前驱结点
if (*pre != NULL && (*pre)->rchild == NULL)
{
(*pre)->RTag = Thread;
(*pre)->rchild = p;
}
if (p->lchild == NULL)
{
p->LTag = Thread;
p->lchild = *pre;
}
else
{
p->LTag = Link;
}
*pre = p;
p = p->rchild; //线索化其右子树
}
}
}
接下来我们讨论遍历中序线索树的算法。要想遍历中序线索树，必须先根据其特征，设计一个能返回结点前驱或后继的函数。
/*
函数名称：Successor
函数功能：返回结点p的后继
输入变量：BiThrTree p：指向中序线索树结点的指针
输出变量：BiThrTree： 指向结点后继的指针
若结点无右孩子，则由后继线索直接得到后继结点；否则后继为右子树的第一个结点（最左边结点）。
*/
BiThrTree Successor(BiThrTree p)
{
if (p->RTag == Thread) //由后继线索直接得到
return p->rchild;
//后继为右子树的第一个结点（最左边结点）
p = p->rchild;
while (p->LTag == Link)
{
p = p->lchild;
}
return p;
}
/*
函数名称：Precursor
函数功能：返回结点p的前驱
输入变量：BiThrTree p：指向中序线索树结点的指针
输出变量：BiThrTree： 指向结点前驱的指针。
若结点无左孩子，则由前驱线索直接得到前驱结点；否则前驱为左子树的最后一个结点（最右边结点）。
*/
BiThrTree Precursor(BiThrTree p)
{
if (p->LTag == Thread) //由前驱线索直接得到
return p->lchild;
//前驱为左子树的最后一个结点（最右边结点）
p = p->lchild;
while (p->RTag == Link)
{
p = p->rchild;
}
return p;
}
顺序遍历中序线索树，需要先找到第一个结点，即最左边的结点，然后顺序访问其后继即可。代码如下：
/*
函数名称：InOrderTraverse_Thr
函数功能：顺序遍历中序线索树
输入变量：BiThrTree T：指向中序线索树头结点的指针
输出变量：无
*/
void InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p = T->lchild;
while (p->LTag == Link) //先找到第一个结点（最左边结点）
{
p = p->lchild;
}
while (p != T)
{
printf("%c ", p->data);
p = Successor(p);//返回结点p的后继
}
}
因为线索树的头结点的右指针指向最后一个结点，所以逆序遍历中序线索树比顺序遍历要来的方便。代码如下：
/*
函数名称：ReInOrderTraverse_Thr
函数功能：逆序遍历中序线索树
输入变量：BiThrTree T：指向中序线索树头结点的指针
输出变量：无
*/
void ReInOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p = T->rchild; //p指向最后一个结点
while (p != T)
{
printf("%c ", p->data);
p = Precursor(p);//返回结点p的前驱
}
}
《大话数据结构》中提供了一个顺序遍历中序线索树的函数，思路很清晰，代码页也很简洁，在这里和大家分享一下。
/*
函数名称：InOrderTraverse_Thr_1
函数功能：顺序遍历中序线索树
输入变量：BiThrTree T：指向中序线索树头结点的指针
输出变量：无
*/
void InOrderTraverse_Thr_1(BiThrTree T)
{
BiThrTree p = T->lchild;
while (p != T)
{
while (p->LTag == Link) //寻找第一个结点（最左边的结点）
{
p = p->lchild;
}
printf("%c ", p->data);
while (p->RTag == Thread && p->rchild != T) //访问直接后续结点（直接由右指针指向）
{
p = p->rchild;
printf("%c ", p->data);
}
p = p->rchild; //访问右子树
}
}
到这里，中序线索树的基本操作就介绍完了，大家可以尝试设计在中序线索树中插入新结点或删除结点的函数，其操作和循环双链表差不多，请试试看吧。
[ 本帖最后由 巧若拙 于 2014-10-2 09:45 编辑 ]
