建立線索二叉樹，或者說對二叉樹線索化，實質上就是遍歷一顆二叉樹。在遍歷過程中，訪問結點的草所是檢查當前的左，右指標域是否為空，將它們改為指向前驅結點或後續結點的線索。為實現這一過程，設指標pre始終指向剛剛訪問的結點，即若指標p指向當前結點，則pre指向它的前驅，以便設線索。

另外，在對一顆二叉樹加線索時，必須首先申請一個頭結點，建立頭結點與二叉樹的跟結點的指向關係，對二叉樹線索化後，還需建立最後一個結點與頭結點之間的線索。

下面是建立中序二叉樹的遞迴演算法，其中pre為全域性變數。

BiThrNodeType *pre;

BiThrTree InOrderThr(BiThrTree T)

{ /*中序遍歷二叉樹T，並將其中序線索化，pre為全域性變數*/

BiThrTree head;

head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*設申請頭結點成功*/

head->ltag=0;head->rtag=1;/*建立頭結點*/

head->rchild=head;/*右指標回指*/

if(！T)head->lchild=head;/*若二叉樹為空，則左指標回指*/

else{head->lchild=T;pre=head;

InThreading(T);/*中序遍歷進行中序線索化*/

pre->rchild=head;

pre->rtag=1;/*最後一個結點線索化*/

head->rchild=pre;

};

return head;

}

void InThreading(BiThrTree p)

{/*透過中序遍歷進行中序線索化*/

if(p)

{InThreading(p->lchild);/*左子樹線索化*/

if(p->lchild==NULL)/*前驅線索*/

{p->ltag=1;

p->lchild=pre;

}

if(p->lchild==NULL)/*後續線索*/

{p->rtag=1;

p->rchild=pre;

}

pre=p;

InThreading(p->rchild);/*右子樹線索化*/

}

}