從上節(jié)的討論得知：遍歷二杈樹是以一定規(guī)則將二杈樹中結(jié)點(diǎn)排列成一個線性序列，得到二杈樹中結(jié)點(diǎn)的先序序列或中序序列或后序序列。這實(shí)際上是對一個非線性結(jié)構(gòu)進(jìn)行線性化操作，使每個結(jié)點(diǎn)（除第一個和最后一個外）在這些線性序列中有且僅有一個直接前驅(qū)和直接后繼。但是，當(dāng)以二杈鏈表作為存儲結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左，右孩子的信息，而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼信息，這種信息只能在遍歷的動態(tài)過程中才能得到。
????? 因?yàn)樵谟衝個結(jié)點(diǎn)的二杈鏈表中必定存在n+1個空鏈域，故可以利用這些空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼信息。
????? 試做如下規(guī)定：若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼。為了避免混淆，需要改變結(jié)點(diǎn)結(jié)構(gòu)，增加兩個標(biāo)志域：LTag，RTag。
????? 其中：LTag = 0，lchild域指示其左孩子；? LTag = 1，lchild域指示其前驅(qū)。
??????????? RTag = 0，rchild域指示其右孩子；? RTag = 1，rchild域指示其后繼。
????? 以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二杈鏈表作為二杈樹的存儲結(jié)構(gòu)，叫做線索鏈表，其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針，叫做線索。加上線索的二杈樹叫做線索二杈樹。對二杈樹以某種次序遍歷使其變成線索二杈樹的過程叫做線索化。
????? 在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個結(jié)點(diǎn)，然后依次找結(jié)點(diǎn)后繼直到其后繼為空為止。
????? 求遍歷后的線性序列的前驅(qū)和后繼。前序線索化能依次找到后繼，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達(dá)到了要求。
????? //二杈樹的二杈線索存儲表示
typedef enum PointerTag {Link, Thread}; //Link:指針,Thread:線索
typedef struct BiThrNode{
????? ElemType data;
????? struct BiThrNode *lchild, *rchild;//左，右孩子指針
????? PointerTag LTag, RTag; //左，右標(biāo)志
} *BiThrTree;
????? 為了方便起見，我們仿照線性表的存儲結(jié)構(gòu)，在二杈樹的線索鏈表上也添加一個頭結(jié)點(diǎn)，并令其lchild域的指針指向二杈樹的根結(jié)點(diǎn)，其rchild域的指針指向中序遍歷時(shí)訪問的最后一個結(jié)點(diǎn)；反之，令二杈樹中序序列的第一個結(jié)點(diǎn)的lchild域的指針和最后一個結(jié)點(diǎn)的rchild域的指針均指向頭結(jié)點(diǎn)。這好比為二杈樹建立了一個雙向線索鏈表，既可以從第一個結(jié)點(diǎn)起順后繼進(jìn)行遍歷，也可以從最后一個結(jié)點(diǎn)起順前驅(qū)進(jìn)行遍歷。
?void InOrderTraverse_Thr(BiThrTree T)//中序遍歷線索二杈樹的非遞歸算法, T 指向頭結(jié)點(diǎn)
{
????? BiThrTree p = T->lchild; //p指向根結(jié)點(diǎn)
????? while (p != T) //空樹或遍歷結(jié)束時(shí)，p == T
????? {
??????????? while (p->LTag == Link)//尋找第一個結(jié)點(diǎn)
??????????? {
????????????????? p = p->lchild;
??????????? }
??????????? cout << p->data << ' ';//輸出該結(jié)點(diǎn)
??????????? while (p->RTag == Thread && p->rchild != T)//訪問后繼結(jié)點(diǎn)
??????????? {
????????????????? p = p->rchild;
????????????????? cout << p->data << ' ';//輸出該結(jié)點(diǎn)
??????????? }
??????????? p = p->rchild;
????? }
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序線索化
{
????? if (p)
????? {
??????????? InThreading(p->lchild, pre); //左子樹線索化
??????????? if (! p->lchild)//若當(dāng)前結(jié)點(diǎn)的左子樹為空，則建立前驅(qū)線索
??????????? {
????????????????? p->LTag = Thread;
????????????????? p->lchild = pre;
??????????? }
??????????? else
????????????????? p->LTag = Link;
??????????? if (pre && !pre->rchild)//若前驅(qū)結(jié)點(diǎn)非空，且其右孩子為空，則建立后繼線索
??????????? {
????????????????? pre->RTag = Thread;
????????????????? pre->rchild = p;
??????????? }
??????????? pre = p;??? //中序向前遍歷接點(diǎn) ，保持pre指向p的前驅(qū)
??????????? pre->RTag = Link;//默認(rèn)前驅(qū)結(jié)點(diǎn)右孩子非空
??????????? InThreading(p->rchild, pre); //右子樹線索化
????? }
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍歷二杈樹，并將其中序線索化
{
????? BiThrTree Thrt = new BiThrNode;? //建立頭結(jié)點(diǎn)
????? 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; //最后一個結(jié)點(diǎn)線索化
??????????? pre->RTag = Thread;
??????????? Thrt->rchild = pre; //此時(shí)pre指向最后一個結(jié)點(diǎn)
????? }
????? return Thrt;
}
////////////////////////////////////////////////////////////////////////////////////////
//應(yīng)用示例：我先生成一棵二杈排序樹（輸入單個字符，以#結(jié)束），并以遞歸方式遍歷輸出結(jié)點(diǎn)；
//然后把該二杈排序樹中序線索化，最后中序遍歷線索二杈樹輸出結(jié)點(diǎn)。
#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; //左，右標(biāo)志
} *BiThrTree;
void InOrderTraverse_Thr(BiThrTree T);//中序遍歷線索二杈樹的非遞歸算法, T 指向頭結(jié)點(diǎn)
void InThreading(BiThrTree & p, BiThrTree & pre); //中序線索化
BiThrTree InOrderThreading(BiThrTree T);//中序遍歷二杈樹，并將其中序線索化
void CreateBTree(BiThrTree & bt);//生成一棵二杈排序樹（輸入單個字符，以#結(jié)束）
BiThrTree NewBTree(ElemType x);//構(gòu)造一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)
void Insert(BiThrTree & b, BiThrTree s);//在二杈排序樹中插入新結(jié)點(diǎn)s
void InOrderPrint_1(BiThrTree p); //中序遍歷輸出結(jié)點(diǎn)（遞歸）
int main()
{
????? BiThrTree bt = NULL;
????? CreateBTree(bt);//生成一棵二杈排序樹（輸入單個字符，以#結(jié)束）
????? InOrderPrint_1(bt); //中序遍歷輸出結(jié)點(diǎn)（遞歸）
????? cout << endl;
????? BiThrTree BT = InOrderThreading(bt);//中序遍歷二杈樹，并將其中序線索化
????? InOrderTraverse_Thr(BT);//中序遍歷線索二杈樹的非遞歸算法, T 指向頭結(jié)點(diǎn)
????? system("PAUSE");
????? return EXIT_SUCCESS;
}
void InOrderTraverse_Thr(BiThrTree T)//中序遍歷線索二杈樹的非遞歸算法, T 指向頭結(jié)點(diǎn)
{
????? BiThrTree p = T->lchild; //p指向根結(jié)點(diǎn)
????? while (p != T) //空樹或遍歷結(jié)束時(shí)，p == T
????? {
??????????? while (p->LTag == Link)//尋找第一個結(jié)點(diǎn)
??????????? {
????????????????? p = p->lchild;
??????????? }
??????????? cout << p->data << ' ';//輸出該結(jié)點(diǎn)
??????????? while (p->RTag == Thread && p->rchild != T)//訪問后繼結(jié)點(diǎn)
??????????? {
????????????????? p = p->rchild;
????????????????? cout << p->data << ' ';//輸出該結(jié)點(diǎn)
??????????? }
??????????? p = p->rchild;
????? }
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序線索化
{
????? if (p)
????? {
??????????? InThreading(p->lchild, pre); //左子樹線索化
??????????? if (! p->lchild)//若當(dāng)前結(jié)點(diǎn)的左子樹為空，則建立前驅(qū)線索
??????????? {
????????????????? p->LTag = Thread;
????????????????? p->lchild = pre;
??????????? }
??????????? else
????????????????? p->LTag = Link;
??????????? if (pre && !pre->rchild)//若前驅(qū)結(jié)點(diǎn)非空，且其右孩子為空，則建立后繼線索
??????????? {
????????????????? pre->RTag = Thread;
????????????????? pre->rchild = p;
??????????? }
??????????? pre = p;??? //中序向前遍歷接點(diǎn) ，保持pre指向p的前驅(qū)
??????????? pre->RTag = Link;//默認(rèn)前驅(qū)結(jié)點(diǎn)右孩子非空
??????????? InThreading(p->rchild, pre); //右子樹線索化
????? }
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍歷二杈樹，并將其中序線索化
{
????? BiThrTree Thrt = new BiThrNode;? //建立頭結(jié)點(diǎn)
????? 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; //最后一個結(jié)點(diǎn)線索化
??????????? pre->RTag = Thread;
??????????? Thrt->rchild = pre; //此時(shí)pre指向最后一個結(jié)點(diǎn)
????? }
????? return Thrt;
}
void CreateBTree(BiThrTree & bt)//生成一棵二杈排序樹（輸入單個字符，以#結(jié)束）
{
????? ElemType x;
????? cin >> x;
????? while (x != '#')
????? {
??????????? BiThrTree s = NewBTree(x);//構(gòu)造一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)
??????????? Insert(bt, s);//在二杈排序樹中插入新結(jié)點(diǎn)s
??????????? cin >> x;
????? }
}
BiThrTree NewBTree(ElemType x)//構(gòu)造一個數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)
{
?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)//在二杈排序樹中插入新結(jié)點(diǎn)s
{
?if (b == NULL)
??b = s;
?else if (b->data == s->data)//不做任何插入操作
??return;
?else if(b->data > s->data)//把s所指結(jié)點(diǎn)插入到左子樹中
????? Insert(b->lchild, s);
?else?????????????? //把s所指結(jié)點(diǎn)插入到右子樹中
????? Insert(b->rchild, s);
}
void InOrderPrint_1(BiThrTree p) //中序遍歷輸出結(jié)點(diǎn)（遞歸）
{
?if (p != NULL)
?{
??InOrderPrint_1(p->lchild); //遍歷左子樹
??????????? cout << p->data << ' ';//輸出該結(jié)點(diǎn)
??InOrderPrint_1(p->rchild); //遍歷右子樹
?}
}