从上节的讨论得知：遍历二杈树是以一定规则将二杈树中结点排列成一个线性序列，得到二杈树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是，当以二杈链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只能在遍历的动态过程中才能得到。
因为在有n个结点的二杈链表中必定存在n+1个空链域，故可以利用这些空链域来存放结点的前驱和后继信息。
试做如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，需要改变结点结构，增加两个标志域：LTag，RTag。
其中：LTag = 0，lchild域指示其左孩子； LTag = 1，lchild域指示其前驱。
RTag = 0，rchild域指示其右孩子； RTag = 1，rchild域指示其后继。
以这种结点结构构成的二杈链表作为二杈树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二杈树叫做线索二杈树。对二杈树以某种次序遍历使其变成线索二杈树的过程叫做线索化。
在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直到其后继为空为止。
求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。
//二杈树的二杈线索存储表示
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild, *rchild;//左，右孩子指针
PointerTag LTag, RTag; //左，右标志
} *BiThrTree;
为了方便起见，我们仿照线性表的存储结构，在二杈树的线索链表上也添加一个头结点，并令其lchild域的指针指向二杈树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二杈树中序序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。这好比为二杈树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
BiThrTree p = T->lchild; //p指向根结点
while (p != T) //空树或遍历结束时，p == T
{
while (p->LTag == Link)//寻找第一个结点
{
p = p->lchild;
}
cout << p->data << ' ';//输出该结点
while (p->RTag == Thread && p->rchild != T)//访问后继结点
{
p = p->rchild;
cout << p->data << ' ';//输出该结点
}
p = p->rchild;
}
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
if (p)
{
InThreading(p->lchild, pre); //左子树线索化
if (! p->lchild)//若当前结点的左子树为空，则建立前驱线索
{
p->LTag = Thread;
p->lchild = pre;
}
else
p->LTag = Link;
if (pre && !pre->rchild)//若前驱结点非空，且其右孩子为空，则建立后继线索
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p; //中序向前遍历接点 ，保持pre指向p的前驱
pre->RTag = Link;//默认前驱结点右孩子非空
InThreading(p->rchild, pre); //右子树线索化
}
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树，并将其中序线索化
{
BiThrTree Thrt = new BiThrNode; //建立头结点
if (!Thrt)
{
printf("Out of space!");
return NULL;
}
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指
if (!T)//若二杈树为空，则左指针回指
Thrt->lchild = Thrt;
else
{
Thrt->lchild = T;
BiThrTree pre = Thrt;
InThreading(T, pre);//中序线索化
pre->rchild = Thrt; //最后一个结点线索化
pre->RTag = Thread;
Thrt->rchild = pre; //此时pre指向最后一个结点
}
return Thrt;
}
////////////////////////////////////////////////////////////////////////////////////////
//应用示例：我先生成一棵二杈排序树（输入单个字符，以#结束），并以递归方式遍历输出结点；
//然后把该二杈排序树中序线索化，最后中序遍历线索二杈树输出结点。
#include <iostream>
using namespace std;
//二杈树的二杈线索存储表示
typedef char ElemType;
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild, *rchild;//左，右孩子指针
PointerTag LTag, RTag; //左，右标志
} *BiThrTree;
void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二杈树的非递归算法, T 指向头结点
void InThreading(BiThrTree & p, BiThrTree & pre); //中序线索化
BiThrTree InOrderThreading(BiThrTree T);//中序遍历二杈树，并将其中序线索化
void CreateBTree(BiThrTree & bt);//生成一棵二杈排序树（输入单个字符，以#结束）
BiThrTree NewBTree(ElemType x);//构造一个数据域为x的新结点
void Insert(BiThrTree & b, BiThrTree s);//在二杈排序树中插入新结点s
void InOrderPrint_1(BiThrTree p); //中序遍历输出结点（递归）
int main()
{
BiThrTree bt = NULL;
CreateBTree(bt);//生成一棵二杈排序树（输入单个字符，以#结束）
InOrderPrint_1(bt); //中序遍历输出结点（递归）
cout << endl;
BiThrTree BT = InOrderThreading(bt);//中序遍历二杈树，并将其中序线索化
InOrderTraverse_Thr(BT);//中序遍历线索二杈树的非递归算法, T 指向头结点
system("PAUSE");
return EXIT_SUCCESS;
}
void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
BiThrTree p = T->lchild; //p指向根结点
while (p != T) //空树或遍历结束时，p == T
{
while (p->LTag == Link)//寻找第一个结点
{
p = p->lchild;
}
cout << p->data << ' ';//输出该结点
while (p->RTag == Thread && p->rchild != T)//访问后继结点
{
p = p->rchild;
cout << p->data << ' ';//输出该结点
}
p = p->rchild;
}
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
if (p)
{
InThreading(p->lchild, pre); //左子树线索化
if (! p->lchild)//若当前结点的左子树为空，则建立前驱线索
{
p->LTag = Thread;
p->lchild = pre;
}
else
p->LTag = Link;
if (pre && !pre->rchild)//若前驱结点非空，且其右孩子为空，则建立后继线索
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p; //中序向前遍历接点 ，保持pre指向p的前驱
pre->RTag = Link;//默认前驱结点右孩子非空
InThreading(p->rchild, pre); //右子树线索化
}
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树，并将其中序线索化
{
BiThrTree Thrt = new BiThrNode; //建立头结点
if (!Thrt)
{
printf("Out of space!");
return NULL;
}
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指
if (!T)//若二杈树为空，则左指针回指
Thrt->lchild = Thrt;
else
{
Thrt->lchild = T;
BiThrTree pre = Thrt;
InThreading(T, pre);//中序线索化
pre->rchild = Thrt; //最后一个结点线索化
pre->RTag = Thread;
Thrt->rchild = pre; //此时pre指向最后一个结点
}
return Thrt;
}
void CreateBTree(BiThrTree & bt)//生成一棵二杈排序树（输入单个字符，以#结束）
{
ElemType x;
cin >> x;
while (x != '#')
{
BiThrTree s = NewBTree(x);//构造一个数据域为x的新结点
Insert(bt, s);//在二杈排序树中插入新结点s
cin >> x;
}
}
BiThrTree NewBTree(ElemType x)//构造一个数据域为x的新结点
{
BiThrTree s = new BiThrNode;
if (!s)
{
printf("Out of space!");
exit (1);
}
s->data = x;
s->lchild = s->rchild = NULL;
s->LTag = s->RTag = Link;
return s;
}
void Insert(BiThrTree & b, BiThrTree s)//在二杈排序树中插入新结点s
{
if (b == NULL)
b = s;
else if (b->data == s->data)//不做任何插入操作
return;
else if(b->data > s->data)//把s所指结点插入到左子树中
Insert(b->lchild, s);
else //把s所指结点插入到右子树中
Insert(b->rchild, s);
}
void InOrderPrint_1(BiThrTree p) //中序遍历输出结点（递归）
{
if (p != NULL)
{
InOrderPrint_1(p->lchild); //遍历左子树
cout << p->data << ' ';//输出该结点
InOrderPrint_1(p->rchild); //遍历右子树
}
}
评论