遍歷二叉樹是按一定的規則將樹中的結點排列成一個線性序列，即是對非線性結構的線性化操作。
如何找到遍歷過程中動態得到的每個結點的直接前驅和直接後繼(第一個和最後一個除外)?如何保存這些信息?
問：一棵有n個結點的二叉樹，有多少個空閒指針域未用？
若一棵二叉樹有n個結點，則有n-1條指針連線 ， 而n個結點共有2n個指針域(Lchild和Rchild) ，所以有n+1個空閒指針域未用。
可以利用這些空閒的指針域來存放結點的直接前驅和直接後繼信息。
對結點的指針域做如下規定：
◆ 若結點有左孩子，則Lchild指向其左孩子，否則，指向其直接前驅；
◆ 若結點有右孩子，則Rchild指向其右孩子，否則，指向其直接後繼；
用這種結點結構構成的二叉樹存儲結構；叫做線索鏈表；指向結點前驅和後繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。
線索二叉樹的結點結構與示例
typedef struct BiTreeNode
{ ElemType data;
struct BiTreeNode *Lchild , *Rchild ;
int Ltag , Rtag ;
}BiThrNode ;
如何在線索樹中找結點的直接後繼?以圖 ，所示的中序線索樹為例：
![這裡寫圖片描述](https://www.aspphp.online/shujuku/UploadFiles_3118/201701/2017012309372235.png "\")
◆ 若樹中結點的右鏈是線索（Rtag=1），則右鏈直接指示了結點的直接後繼，如結點G的直接後繼是結點E。
◆ 若樹中結點的右鏈是指針（ Rtag=0）。根據中序遍歷的規律， Rtag=0的結點的直接後繼是遍歷其右子樹時訪問的第一個結點，即右子樹中最左下位置的(葉子)結點。如結點C的直接後繼：沿右指針找到右子樹的根結點F，然後沿左鏈往下直到Ltag=1的結點即為C的直接後繼結點H。
在後序遍歷的線索樹中找結點的直接後繼比較復雜，可分以下三種情況：
若結點是二叉樹的根結點：其直接後繼為空；
若結點是其父結點的左孩子且其父結點沒有右子樹：直接後繼為其父結點；
若結點是其父結點的左孩子且其父結點有右子樹：直接後繼是對其父結點的右子樹按後序遍歷的第一個結點。
二叉樹的線索化指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過程。
線索化的過程就是在遍歷過程中修改空指針使其指向直接前驅或直接後繼的過程。 下面主要討論按中序遍歷次序線索化二叉樹。 仿照線性表的存儲結構，在二叉樹的線索鏈表上也添加一個頭結點head，頭結點的指針域的安排是：
◆ Lchild域：指向二叉樹的根結點；
◆ Rchild域：指向中序遍歷時的最後一個結點；
◆ 二叉樹中序序列中的第一個結點Lchild指針域和最後一個結點Rchild指針域均指向頭結點head。
添加了頭結點的線索二叉樹，如同為二叉樹建立了一個雙向線索鏈表，對一棵線索二叉樹既可從頭結點也可從最後一個結點開始按尋找直接後繼進行遍歷。顯然，這種遍歷不需要堆棧。
#define MAX_NODE 50
typedef enmu{ Link , Thread} PointerTag ;
/* Link=0表示指針， Thread=1表示線索 */
typedef struct BiThrNode
{ ElemType data;
struct BiTreeNode *Lchild , *Rchild ;
PointerTag Ltag , Rtag ;
}BiThrNode, *BiThrTree;
ElemType Nil=‘#’; /*以#為空 */
Status CreateBiThrTree(BiThrTree *T)
{ ElemType ch;
scanf("%c",&ch);
if(h==Nil) *T=NULL;
else
{ *T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*T) return ERROR;
(*T)->data=ch; /* 生成根結點(前序) */
CreateBiThrTree(&(*T)->lchild); /* 遞歸構造左子樹 */
if((*T)->lchild) (*T)->LTag=Link; /* 有左孩子 */
CreateBiThrTree(&(*T)->rchild); /* 遞歸構造右子樹 */
if((*T)->rchild) (*T)->RTag=Link; /* 有右孩子 */
}
return OK;
}
BiThrNode *pre//全局變量，始終指向剛剛訪問過的結點
void InThreading (BiThrNode *T)
{ if(T)
{ Inorder_Threading(T->lchild) /* 遞歸左子樹線索化 */
if(!T->lchild) /* 沒有左孩子 */
{ T->LTag=Thread; /* 前驅線索 */
T->lchild=pre; /* 左孩子指針指向前驅 */
}
if(!pre->rchild) /* 前驅沒有右孩子 */
{ pre->RTag=Thread; /* 後繼線索 */
pre->rchild=T; /* 前驅右孩子指針指向後繼(當前結點T) */
}
pre=T; /* 保持pre指向T的前驅 */
Inorder_Threading(T->rchild); /* 遞歸右子樹線索化 */
}
}
前驅結點的線索化：if(!T->lchild)表示如果某結點的左指針域為空，因為其前驅結點剛剛訪問過，賦值給了pre，所以可將pre賦值給T->lchild，並修改T->LTag=Thread（即定義為1）以完成前驅結點的線索化；
後繼結點的線索化：因此時後繼結點還沒有訪問到，因此只能對它的前驅結點pre的右指針rchild做判斷， if(!pre->rchild)表示如果前驅的右指針域為空，則T就是pre的後繼，於是pre->rchild=T，並且設置pre->RTag=Thread，完成後繼結點的線索化。
完成前驅和後繼的判斷後，要將當前結點T賦值給pre，以便於下次使用。
/* 中序遍歷二叉樹T,並將其中序線索化,Thrt指向頭結點 */
Status InOrderThreading(BiThrTree *Thrdhead, BiThrTree T)
{ * Thrdhead =(BiThrTree)malloc(sizeof(BiThrNode));
if(!* Thrdhead ) return ERROR;
(* Thrdhead )->LTag=Link; /* 建頭結點 */
(* Thrdhead )->RTag=Thread;
(* Thrdhead )->rchild= NULL; //右指針此時為空
if(!T) (* Thrdhead )->lchild= * Thrdhead; //若二叉樹空,則左指針回指
else
{
(* Thrdhead )->lchild=T; //非空，指向根節點
pre=(* Thrdhead );
InThreading(T); /* 中序遍歷進行中序線索化 */
pre->rchild=* Thrdhead; //pre是中序遍歷的最後一個結點
pre->RTag=Thread; /* 最後一個結點線索化 */
(* Thrdhead )->rchild=pre;
}
return OK;
}
線索二叉樹的創建雖然比較復雜，但在線索二叉樹中，由於有線索存在，在某些情況下可以方便地找到指定結點在某種遍歷序列中的直接前驅或直接後繼。 此外，在線索二叉樹上進行某種遍歷比在一般的二叉樹上進行這種遍歷要容易得多，不需要設置堆棧，且算法十分簡潔。
/* 中序遍歷二叉線索樹T(頭結點)的非遞歸算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p指向根結點 */
while(p!=T) /* 空樹或遍歷結束時,p==T */
{ while(p->LTag==Link)
p=p->lchild; //當LTag==0時循環到中序序列第一個結點
visit(p->data);
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 訪問後繼結點 */
}
p=p->rchild;
}
return OK;
}
