有 n 個結(jié)點的二叉鏈表中，其二叉鏈表的 n 個結(jié)點中共有 2n 個指針域柬批，在這 2n 個指針域中实幕，真正用于指向后件（左子結(jié)點或右子結(jié)點）的指針域只有 n-1 個卸奉，而另外的 n+1 個指針域都是空的空厌。這樣就利用二叉鏈表中的空指針域庐船，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指針（這種附加的指針稱為 " 線索 "），這種加上了線索的二叉鏈表稱為線索鏈表嘲更，相應(yīng)的二叉樹稱為線索二叉樹 (ThreadedBinaryTree) 筐钟。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹赋朦、中序線索二叉樹和后序線索二叉樹三種篓冲。
線索鏈表的結(jié)點結(jié)構(gòu)
線索鏈表中的結(jié)點結(jié)構(gòu)為：
ltag 和 rtag 是增加的兩個標志域，用來區(qū)分結(jié)點的左宠哄、右指針域是指向其左壹将、右孩子的指針，還是指向其前趨或后繼的線索毛嫉。
二叉樹的線索化
線索化和線索化實質(zhì)
將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化 瞭恰。按某種次序?qū)⒍鏄渚€索化的實質(zhì)是：按該次序遍歷二叉樹，在遍歷過程中用線索取代空指針狱庇。
二叉樹的中序線索化
算法與中序遍歷算法類似惊畏，只需要將遍歷算法中訪問結(jié)點的操作具體化為建立正在訪問的結(jié)點與其非空中序前趨結(jié)點間線索。
a). 若上次訪問到的結(jié)點的右指針為空密任，則將當前訪問到的結(jié)點地址填入颜启，并置右標志域為 1
b). 若當前訪問到的結(jié)點的左指針為空，則將上次訪問到的結(jié)點地址填入浪讳，并置左標志域為 1
如何使用二叉線索樹
在中序線索二叉樹中缰盏，查找結(jié)點 *p 的中序后繼結(jié)點分兩種情形：
a). 若 *p 的右子樹空 ( 即 p->rtag 為 Thread) ，則 p->rchild 為右線索淹遵，直接指向 *p 的中序后繼口猜。
b). 若 *p 的右子樹非空 ( 即 p->rtag 為 Link) ，則 *p 的中序后繼必是其右子樹中第一個中序遍歷到的結(jié)點透揣。也就是從*p 的右孩子開始济炎，沿該孩子的左鏈往下查找，直至找到一個沒有左孩子的結(jié)點為止辐真，該結(jié)點是 *p 的右子樹中 “ 最左下 ” 的結(jié)點须尚，即 *P 的中序后繼結(jié)點。
具體算法如下：
BinThrNode *Inorderpre(BinThrNode *p)
{ //在中序線索樹中找結(jié)點*p的中序前趨侍咱，設(shè)p非空
BinThrNode *q耐床；
if (p->ltag==Thread) //*p的左子樹為空
return p->lchild； //返回左線索所指的中序前趨
else{
q=p->lchild楔脯； //從*p的左孩子開始查找
while (q->rtag==Link)
q=q->rchild撩轰； //右子樹非空時，沿右鏈往下查找
return q昧廷； //當q的右子樹為空時堪嫂，它就是最右下結(jié)點
} //end if
}
