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