一 實質
周遊二叉樹過程中用線索（前驅和後繼）取代空指針的的做法
主要是增加倆個指針，pre指針始終指向剛剛通路過的節點，p指針始終指向目前通路的節點其中，*pre是*p的前驅，*p是*pre的後繼
三 中序線索化算法：
//将二叉樹按中序線索化算法
typedef enum {link,thread} pointertag;//枚舉值分别為0,1
typedef struct node
{
datatype data;
pointertag ltag,rtag; //左右标志
struct node *lchild ,*rchild;
}binthrnode;//線索二叉樹節點類型
typedef binthrnode *binthrtree;
void inorderthreading(binthrtree p)
{//将二叉樹p中序線索化
if(p)//p非空時，目前通路結點是*p
{
inorderthreading(p->lchild);//左子樹線索化
//建立正在通路節點的前驅結點之間的線索
t->ltag = (t->lchild)?link:thread;
t->rtag = (t->rchild)?link:thread;
if(pre)
{
if(pre->rtag==thread)
pre->rchild = p;
if(p->ltag==thread)
p->lchid = pre;
}
pre = p;
inorderthreading(t->rchild);//右子樹線索化
}
}
算法分析：和中序周遊一樣遞歸過程對每個節點僅做一次通路，是以對于n個節點的二叉樹算法複雜度為o(n)
四 前驅和後繼的查找
binthrnode *inordersuccessor(binthrnode *p)
{//在中序線索樹查找*p的後繼
binthrnode *q;
if(p->rtag==thread)
return p->rchlid;//傳回其所指的後繼
else
q = p->rchild;//從*p的右孩子開始查找
while(q->ltag==link)
q = q->lchild;//左子樹為空，沿左鍊往下查找
return q;
binthrnode *inorderpre(binthrnode *p)
{//在中序線索樹中找結點*p的中序前趨，設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的右子樹為空時，它就是最右下結點
} //end if
}
從上面可以看出，對與非線索二叉樹，查找其節點十分困難需要周遊，而線索二叉樹加入了前驅和後繼之後是這種查找變得簡單易行
轉載：http://blog.csdn.net/xsf50717/article/details/40106441