【文章內(nèi)容簡介】 樹就是按一定規(guī)則將二叉樹中的結(jié)點排列成一個線性序列，把一個非線性結(jié)構(gòu)線性化。 ?以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到其左右兒子，而不能直接找到它的前趨或后繼； ?另一方面，對有 n個結(jié)點的二叉鏈表，有 n+1個指針域是空的，能否利用這些空指針域來存儲結(jié)點的前趨或后繼呢？ ?艾 .（ ）和查 .桑頓（ ） 提出了巧妙地利用這些空鏈的方法。 線索二叉樹 (續(xù)） （以中序遍歷為例） 若結(jié)點的左指針為空，則存放其前驅(qū)結(jié)點；若結(jié)點的右指針為空，則存放其后繼結(jié)點。用這種方法構(gòu)造的二叉樹叫 線索二叉樹。 把一個二叉樹變成一個線索二叉樹的過程叫作二叉樹的線索化。 ?以 中序遍歷 為例介紹二叉樹的線索化 基本思想： 若結(jié)點有左兒子，則其 lchild指向其左兒子；否則，令 lchild指向其前趨結(jié)點； 若結(jié)點有右兒子，則其 rchild指向其右兒子；否則，令 rchild指向其后繼結(jié)點； 在每個結(jié)點中增加兩個標志，即左線索標志ltag，右線索標志 rtag, 以區(qū)別是線索和兒子。 ?增加線索標志后的結(jié)點結(jié)構(gòu)為： ? 其中 ， ltag=0， Lchild指向其左兒子 ltag=1， Lchild指向其前趨 rtag=0， rchild指向其右兒子 rtag=1， rchild指向其后繼 ?注意 指針 和 線索 的區(qū)別 lchild ltag data rtag rchild 結(jié)點類型和相應結(jié)點的指針類型定義如下： typedef struct bithrnode { int ltag。 int rtag。 elementtype data。 struct bithrnode *lchild。 struct bithrnode *rchild。 }bithrtree。 圖 中序線索樹 ?與圖 示二叉樹對應的中序線索樹如左圖所示。圖中的虛線箭頭即為新加上的線索。 ○ A ○ C ○ F ○ G ○ B ○ D ○ E ○ H ○ I 線索二叉樹的構(gòu)造 基本思想： 已知一棵二叉樹，使其線索化。本質(zhì)是：將二叉鏈表中的空指針改為前趨或后繼，而前趨或后繼只有在遍歷過程中才能得到，因此線索化的過程就是在遍歷的過程中修改空指針的過程。 為了記下遍歷過程中訪問結(jié)點的先后次序，附設(shè)兩個指針： pre指向 剛訪問過 的結(jié)點 , p指向 正在訪問的 結(jié)點。 （以中序遍歷），在遍歷算法的輸出語句處加入下列語句即可。 if( plchild== null) { plchild=pre。 pltag=1 } if( prerchild== null) { prerchild=p。 prertag=1} 以中序為例 構(gòu)造 線索二叉樹算法 void Nrinorder(bithrtree *BT) { bithrtree *S[maxsize],*p,*pre。 /*定義棧 S[ ],中間變量 P*/ int top=0。 p=bt。 pre=null。 while ((p!=null) || (top!=0)） { while(p!=null) { s[top]=p。 /*若 P非空 ， 則進棧 */ top++。 p=plchild。 /*取其左兒子 */ } if (top!=0) { top。 p=s[top]。 /*退棧至 P中 */ if( plchild== null) { plchild=pre。 pltag=1 } if( prerchild== null) { prerchild=p。 prertag=1} pre=p。 p=prchild。 /*取其右兒子 */ } } } 中序線索樹求 后繼 結(jié)點 ?在中序遍歷線索樹過程中，按下述兩條原則即可找到后繼結(jié)點： 1) 如果結(jié)點的 rtag=1，說明其右指針域是線索，這個線索所指的即是該結(jié)點的后繼結(jié)點； 2) 如果結(jié)點的 rtag=0，則其右指針指向的是右兒子 , 其后繼是其右子樹最左下方的結(jié)點 . 中序線索二叉樹求 后繼 算法 tbtree *next (bithrtree *p) { bithrtree *q。 if (prtag==1) return(prchild)。 /*由后繼線索得到 */ else { q=prchild。 while(qltag==0) q=qlchild。 return(q)。 } } 在 中序線索樹中求 前趨 結(jié)點 ?找前趨結(jié)點相應的原則如下： 1) 如果某結(jié)點的 Ltag=1，說明其左指針域是線索，這個線索所指的即是該結(jié)點的前趨結(jié)點； 2) 如果某結(jié)點的 Ltag=0，則其左指針指向左兒子，它的前趨是該結(jié)點的左子樹最右下方的結(jié)點 . 在中序線索二叉樹中求前驅(qū)結(jié)點的算法 tbtree *pre (bithrtree *p) { bithrtree *q。 if (pLtag==1) return(pLchild)。 else { q=pLchild。 while(qRtag==0) q=qRchild。 return(q)。 } } 中序遍歷線索樹 ?從根結(jié)點起一直向左下方查找，找到左線索標志為 1的結(jié)點 (“最左下方”的結(jié)點 ),即為遍歷的第一個結(jié)點。 ?由此結(jié)點開始，反復進行尋找后繼結(jié)點的過程，并訪問這些結(jié)點，直至結(jié)束。 中序遍歷子線索二叉樹非遞歸算法 void thinorder(bithrtree *p) { if (p!=NULL) /*樹非空 */ { while(pltag==0) p=plchild。 /*找最左下方的結(jié)點 */ do { print(“%c” ,pdate)。 /*訪問結(jié)點 */ p=next(p)。 }while(p!=NULL)。 } } 返回 在中序線索二叉樹中插入結(jié)點 插入結(jié)點 T, 使其成為 S 的右兒子 . 插入過程： 1. 若 S的右子樹為空，則 T為 S的右兒子， S的后繼為 T的后繼， S成為 T的前趨； 2. 若 S的右子樹為非空，則當 T插入后， S 的右子樹成為 T的右子樹， S為 T的前 趨， S原來的后繼中的 lchild指針改為 T。 在中序線索二叉樹中插入結(jié)點的算法 Bithrtree insert(bithrtree *thrt,*s,*t) { bithrtree *p。 Trtag=srtag。 /*S的后繼 Trchild=srchild。 /*成為 T的后繼 Tltag=1。 /*S成為 T的前趨 */ Tlchild=s。 Srtag=0。 /*T成為 S的右子樹 */ Srchild=t。 在中序線索二叉樹中插入結(jié)點的算法（續(xù)） P=trchild。 If (trtag==0) /*若 T有右兒子，則找它右子樹的 { while (pltag==0) /*最左下方的結(jié)點 p=plchild。 } plchild=t。 /*最左下方的結(jié)點的 lchild return(thrt)。 /*指向其前趨 T } ?插入結(jié)點 T, 使其成為 S 的左兒子 樹 森林與二叉樹的轉(zhuǎn)換 普通樹可用鏈式存儲結(jié)構(gòu)來表示，每個結(jié)點包括數(shù)據(jù)域以及指向它各個兒子結(jié)點的指針域。 ? 由于同一樹的各結(jié)點