從上節的討論得知：遍歷二杈樹是以一定規則將二杈樹中結點排列成一個線性序列，得到二杈樹中結點的先序序列或中序序列或后序序列。這實際上是對一個非線性結構進行線性化操作，使每個結點（除第一個和最后一個外）在這些線性序列中有且僅有一個直接前驅和直接后繼。但是，當以二杈鏈表作為存儲結構時，只能找到結點的左，右孩子的信息，而不能直接得到結點在任一序列中的前驅和后繼信息，這種信息只能在遍歷的動態過程中才能得到。
????? 因為在有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); //遍歷右子樹
?}
}