[科普中國]-線索二叉樹

在二叉樹的結點上加上線索的二叉樹稱為線索二叉樹，對二叉樹以某種遍歷方式（如先序中序、后序）使其變?yōu)榫€索二叉樹的過程稱為對二叉樹進行線索化。1

概念對于n個結點的二叉樹，在二叉鏈存儲結構中有n+1個空鏈域，利用這些空鏈域存放在某種遍歷次序下該結點的前驅結點和后繼結點的指針，這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。

這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。

**注意：**線索鏈表解決了無法直接找到該結點在某種遍歷序列中的前驅和后繼結點的問題，解決了二叉鏈表找左、右孩子困難的問題。

本質二叉樹的遍歷本質上是將一個復雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和后繼（第一個結點無前驅，最后一個結點無后繼）。對于二叉樹的一個結點，查找其左右子女是方便的，其前驅后繼只有在遍歷中得到。為了容易找到前驅和后繼，有兩種方法。一是在結點結構中增加向前和向后的指針，這種方法增加了存儲開銷，不可??；二是利用二叉樹的空鏈指針。

優(yōu)勢與不足優(yōu)勢(1)利用線索二叉樹進行中序遍歷時，不必采用堆棧處理，速度較一般二叉樹的遍歷速度快，且節(jié)約存儲空間。

(2)任意一個結點都能直接找到它的前驅和后繼結點。2

不足(1)結點的插入和刪除麻煩，且速度也較慢。

(2)線索子樹不能共用。2

存儲結構線索二叉樹中的線索能記錄每個結點前驅和后繼信息。為了區(qū)別線索指針和孩子指針，在每個結點中設置兩個標志ltag和rtag。

當tag和rtag為0時，leftChild和rightChild分別是指向左孩子和右孩子的指針；否則，leftChild是指向結點前驅的線索(pre)，rightChild是指向結點的后繼線索(suc)。由于標志只占用一個二進位，每個結點所需要的存儲空間節(jié)省很多。3

現(xiàn)將二叉樹的結點結構重新定義如下：

|| ||

其中：ltag=0 時lchild指向左兒子；ltag=1 時lchild指向前驅；rtag=0 時rchild指向右兒子；rtag=1 時rchild指向后繼。

構建建立線索二叉樹，或者說對二叉樹線索化，實質上就是遍歷一棵二叉樹。在遍歷過程中，訪問結點的操作是檢查當前的左，右指針域是否為空，將它們改為指向前驅結點或后續(xù)結點的線索。為實現(xiàn)這一過程，設指針pre始終指向剛剛訪問的結點，即若指針p指向當前結點，則pre指向它的前驅，以便設線索。

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

下面是建立中序二叉樹的遞歸算法，其中pre為全局變量。

void InThreading(BiThrTree*p);//預先聲明BiThrNodeType*pre;BiThrTree*InOrderThr(BiThrTree*T){/*中序遍歷二叉樹T，并將其中序線索化，pre為全局變量*/BiThrTree*head;//線索二叉樹的頭結點，指向根結點head=(BitThrNodeType*)malloc（sizeof（BitThrNodeType））;/*設申請頭結點成功*/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;}returnhead;}voidInThreading(BiThrTree*p){/*通過中序遍歷進行中序線索化*/if(p){InThreading(p->lchild);/*左子樹線索化，遞歸*/if(p->lchild==NULL)/*前驅線索*/{ p->ltag=1;p->lchild=pre;}elsep->ltag=0;if(p->rchild==NULL)p->rtag=1;/*后驅線索*/elsep->rtag=0;if(pre!=NULL&&pre->rtag==1)pre->rchild=p;pre=p;InThreading(p->rchild);/*右子樹線索化*/}}進行中序線索化的算法：

bithptr*pre=NULL;/*全程變量*/voidINTHREAD(bithptr*p){if(p!=NULL){if(p->ltag==0)INTHREAD(p->lchild);/*左子樹線索化*/if(p->lchild==NULL){p->ltag=1;p->lchild=pre;}if(p->rchild==NULL)p->rtag=1;if(pre!=NULL&&pre->rtag==1)pre->rchild=p;pre=p;/*前驅指向當前結點*/if(p->rtag==0)INTHREAD(p->rchild);/*右子樹線索化*/}}線索二叉樹查找前驅和后繼：

（1）中序線索二叉樹：若結點的ltag=1，lchild指向其前驅；否則，該結點的前驅是以該結點為根的左子樹上按中序遍歷的最后一個結點。若rtag=1，rchild指向其后繼；否則，該結點的后繼是以該結點為根的右子樹上按中序遍歷的第一個結點。

求后繼的算法如下：

bithptr*INORDERNEXT(bithptr*p){if(p->rtag==1)return(p->rchild);else{q=p->rchild;/*找右子樹最先訪問的結點*/while(q->ltag==0)q=q->lchild;return(q);}}求前驅的算法如下：

bithptr*INORDERNEXT(bithptr*p){if(p->ltag==1)return(p->lchild);else{q=p->lchild;/*找左子樹最后訪問的結點*/while(q->rtag==0)q=q->rchild;return(q);}}（2） 后序線索二叉樹：

在后序線索二叉樹中查找結點*p的前驅：若結點*p無左子樹，則p->lchild指向其前驅；否則，若結點*p有左子樹，當其右子樹為空時，其左子樹的根（即p->lrchild）為其后序前驅。當其右子樹非空時，其右子樹的根（即p->rchild）為其后序前驅。

在后序線索二叉樹中查找結點*p的后繼：若結點*p為根，則無后繼；若結點*p為其雙親的右孩子，則其后繼為其雙親；若結點*p為其雙親的左孩子，且雙親無右子女，則其后繼為其雙親；若結點*p為其雙親的左孩子，且雙親有右子女，則結點*p的后繼是其雙親的右子樹中按后序遍歷的第一個結點。所以，求后序線索二叉樹中結點的后繼要知道其雙親的信息，要使用棧，所以說后序線索二叉樹是不完善的。

（3）先序線索二叉樹：

在先序線索二叉樹中查找結點的后繼較容易，而查找前驅要知道其雙親的信息，要使用棧，所以說先序線索二叉樹也是不完善的。4

本詞條內容貢獻者為:

徐恒山 - 講師 - 西北農林科技大學