【正文】 ltag=Thread。 qlchild=t。 //結(jié)點t為q的前驅(qū)結(jié)點 trchild=q。 trtag=Link。 if(qrtag==Link) //當(dāng)結(jié)點t原來有右子樹 { p=qrchild。 while(pltag==Link) p=plchild。 //查找t的后繼結(jié)點 plchild=q。 //使t的后繼作為q的后繼結(jié)點 }}函數(shù)void InOrder_Thr(BiThrTree Thrt,void(*Prt)(BiThrTree))的功能是遍歷中序線索二叉樹Thrt（Thrt的含義如前所述）。算法的實現(xiàn)過程是：（1）令指針p指向根結(jié)點，當(dāng)二叉樹非空或遍歷未結(jié)束時，繼續(xù)如下操作；（2）順著p的左鏈域?qū)ふ抑钡浇Y(jié)點p的ltag=Thread為止；（3）訪問結(jié)點p的數(shù)據(jù)域（Prt(p)）；（4）當(dāng)p的rtag=Thread且prchild!=Thrt時，重復(fù)執(zhí)行語句：p=prchild；并且同時訪問結(jié)點p的數(shù)據(jù)域（Prt(p)）；（5）當(dāng)p的rtag=Link時，令：p=prchild；（6）當(dāng)p指向非空樹或遍歷未結(jié)束（即p!=Thrt）時，重復(fù)執(zhí)行（2）～（5）。算法的程序?qū)崿F(xiàn)如下：void InOrder_Thr(BiThrTree Thrt,void(*Prt)(BiThrTree)){ BiThrTree p=Thrtlchild。 while(p!=Thrt) { while(pltag==Link) p=plchild。 Prt(p)。 while(prtag==Threadamp。amp。prchild!=Thrt) { p=prchild。 Prt(p)。 } p=prchild。 } coutendl。}void visit(BiThrTree p) {//訪問p的操作為輸出數(shù)據(jù)域ltag、lchilddata、data、rtag、rchilddata的數(shù)據(jù)信息。 cout39。(39。pltagplchilddata39。,39。pdata39。,39。prtagprchilddata39。)39。}由于線索化的實則是將二叉鏈表中的所有空指針指向該結(jié)點的前驅(qū)或后繼結(jié)點，而前驅(qū)或后繼結(jié)點的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改結(jié)點的空指針域和相應(yīng)的標(biāo)志域的過程。（1）函數(shù)void InThreading(BiThrTree p,BiThrTree amp。pre)的功能是，對以根結(jié)點指針p所指的線索二叉鏈表進(jìn)行中序遍歷，并在遍歷的過程中進(jìn)行線索化，其中p為當(dāng)前指針，pre為其前驅(qū)結(jié)點指針。該函數(shù)被調(diào)用后pre指向中序遍歷序列的最后一個結(jié)點。void InThreading(BiThrTree p,BiThrTree amp。pre){ if(p) { InThreading(plchild,pre)。 //對結(jié)點p的左子樹中序線索化 if(!plchild) //對結(jié)點p加線索 { pltag=Thread。 plchild=pre。 } //使pre為結(jié)點p的前驅(qū)結(jié)點 if(!prerchild) //對結(jié)點pre加線索 { prertag=Thread。 prerchild=p。 } //使p為pre的后繼結(jié)點 pre=p。 //修改前驅(qū)結(jié)點pre的值 InThreading(prchild,pre)。 //對結(jié)點p的右子樹中序線索化 }}（2）函數(shù)void InOrderThreading(BiThrTree amp。Thrt,BiThrTree T)的功能是，首先生成一個頭結(jié)點Thrt并使其左孩子指針指向二叉樹T，然后通過語句：pre=Thrt。InThreading(T,pre)。對T加線索。void InOrderThreading(BiThrTree amp。Thrt,BiThrTree T){ BiThrTree pre。 Thrt=new BiThrNode。 Thrtdata=39。39。 Thrtltag=Link。 Thrtrtag=Thread。 Thrtrchild=Thrt。 if(!T) Thrtlchild=Thrt。 else { Thrtlchild=T。 pre=Thrt。 InThreading(T,pre)。 prerchild=Thrt。 // Thrt為遍歷序列的最后一個結(jié)點pre的后繼 prertag=Thread。 Thrtrchild=pre。 // Thrt的右孩子為遍歷序列的最后一個結(jié)點 }}該演示程序的功能為：（1）先序建立一棵線索二叉鏈表T；（2）對二叉樹T進(jìn)行中序全線索化并顯示輸出中序遍歷序列；（3）通過求前驅(qū)結(jié)點的方法逆序輸出二叉樹T的中序遍歷序列；（4）通過求后繼結(jié)點的方法輸出二叉樹T的中序遍歷序列；（5）在T中插入一個值為x的結(jié)點，使其成為根結(jié)點的右孩子，并顯示輸出插入結(jié)點后的中序遍歷序列。void main(){ BiThrTree T,Thrt,p。 cout（1）先序建立一棵二叉樹T,輸入T的先序遍歷全序列:\n。 Create_BiThr(T)。 cout對二叉樹T進(jìn)行中序全線索化:\n。 InOrderThreading(Thrt,T)。 cout（2）對中序全線索二叉樹T的遍歷結(jié)果為:\n。 InOrder_Thr(Thrt,visit)。 cout（3）通過求前驅(qū)結(jié)點的方法逆序輸出二叉樹T的中序遍歷序列:\n。 p=Thrtrchild。 do{ visit(p)。 }while((p=Prior_Thr(Thrt,p))!=Thrt)。 coutendl。 cout（4）通過求后繼結(jié)點的方法輸出二叉樹T的中序遍歷序列:\n。 p=Thrtlchild。 while(plchild!=Thrt)p=plchild。 //求中序序列的頭結(jié)點p do{ visit(p)。 }while((p=Next_Thr(Thrt,p))!=Thrt)。 coutendl。 cout（5）插入一個值為x的結(jié)點，使其成為根結(jié)點的右孩子:\n。 InsertRC_Thr(T,39。X39。)。 cout插入后對中序全線索二叉樹T的遍歷結(jié)果為:\n。 InOrder_Thr(Thrt,visit)。}程序運行演示結(jié)果如下：（1）先序建立一棵二叉樹T,輸入T的先序遍歷全序列:ABD**E**G*FG***↙對二叉樹T進(jìn)行中序全線索化:（2）對中序全線索二叉樹T的遍歷結(jié)果為:(1,D,1B)(0D,B,0E)(1B,E,1A)(0B,A,0G)(1A,G,0F)(1G,G,1F)(0G,F,1)（3）通過求前驅(qū)結(jié)點的方法逆序輸出二叉樹T的中序遍歷序列:(0G,F,1)(1G,G,1F)(1A,G,0F)(0B,A,0G)(1B,E,1A)(0D,B,0E)(1,D,1B)（4）通過求后繼結(jié)點的方法輸出二叉樹T的中序遍歷序列:(1,D,1B)(0D,B,0E)(1B,E,1A)(0B,A,0G)(1A,G,0F)(1G,G,1F)(0G,F,1)（5）插入一個值為x的結(jié)點，使其成為根結(jié)點的右孩子:插入后對中序全線索二叉樹T的遍歷結(jié)果為:(1,D,1B)(0D,B,0E)(1B,E,1A)(0B,A,0X)(1A,X,0G)(1X,G,0F)(1G,G,1F)(0G,F,1)（視圖中沒有插入結(jié)點x）。本節(jié)將主要討論樹的存儲表示及其遍歷操作，并建立森林、樹與二叉樹的對應(yīng)關(guān)系。樹在實際應(yīng)用中的存儲表示是多種多樣的，這里僅介紹4種常用的存儲表示方法。1．雙親表示法這種表示方法要求用一維數(shù)組來存儲樹的有關(guān)信息，每個結(jié)點對應(yīng)一個數(shù)組元素，它包括兩個域：一個是數(shù)據(jù)域(data)，存放結(jié)點中的數(shù)據(jù)；一個是指針域(parent)，存放該結(jié)點的雙親結(jié)點在數(shù)組中的下標(biāo)值。雙親表示法的類型定義如下：define MAXSIZE 100 //定義結(jié)點數(shù)的最大值樹的結(jié)點類型定義：Struct PTNode{ TElemType data。 //數(shù)據(jù)域 int parent。 //雙親結(jié)點下標(biāo)}。樹的順序存儲結(jié)構(gòu)類型定義：Struct PTree{ PTNode nodes[MAXSIZE]。 int r,n。 //r表示根所在的位置，n表示結(jié)點個數(shù)}。例如。在雙親表示法中，查找一個結(jié)點的雙親非常容易，比如下標(biāo)值為4的結(jié)點的data值為E，其雙親結(jié)點的下標(biāo)為1，所以在下標(biāo)為1的元素中的data值B即為E的雙親。但是，要查找一個結(jié)點的所有孩子時需要從頭到尾掃描一次遍才能知道。2．孩子鏈表表示法對于一棵度為m的樹，可以用類似于二叉鏈表表示二叉樹的方法，建立每個結(jié)點具有m個指針域的m叉鏈表來存儲表示。但是，每棵樹的度數(shù)可以不同，所以樹的結(jié)點類型不易統(tǒng)一，這樣對樹的各種操作帶來很大不便。如果將m的值取得很大，并為每個結(jié)點設(shè)置m個指針域，那么在存儲一棵樹時結(jié)點的多數(shù)指針域為空，從而帶來存儲空間的巨大浪費。為了便于找到1個結(jié)點的所有孩子，可以將它們用一個單鏈表來存儲，生成一個線性鏈表。這樣，要為含有n個結(jié)點的樹建立n個單鏈表（葉結(jié)點的孩子單鏈表為空表）；而n個頭指針又組成一個順序表，此即為樹的孩子鏈表表示法。例如。孩子鏈表結(jié)構(gòu)類型定義如下：define MAXSIZE 100 //定義結(jié)點數(shù)的最大值鏈表結(jié)點類型定義：typedef struct CTNode{ //孩子鏈表結(jié)點結(jié)構(gòu)定義 int child。 //孩子結(jié)點對應(yīng)的下標(biāo)值 CTNode* next。 //指向下一個孩子結(jié)點}*ChildPtr。 鏈表頭結(jié)點類型定義：Struct CTBox{ //孩子鏈表頭結(jié)點結(jié)構(gòu)定義 TElemType data。 //孩子鏈表頭結(jié)點數(shù)據(jù)域 ChildPtr firstchild //指向第一個孩子結(jié)點}。孩子鏈表表示樹的類型定義：Struct CTree{ //孩子鏈表存儲結(jié)構(gòu)定義 CTBox node[MAXSIZE]。 //孩子鏈表頭結(jié)點的數(shù)組 Int r,n。 // r表示根所在的位置，n表示結(jié)點個數(shù)}。與雙親表示法相反，孩子表示法便于查找樹中每個結(jié)點的所有孩子，由表中某個結(jié)點指針域中的next即可得到該結(jié)點的所有孩子結(jié)點在數(shù)組中的下標(biāo)值。而要查找某個結(jié)點的雙親需要按照該結(jié)點在頭結(jié)點順序表中的下標(biāo)對頭結(jié)點數(shù)組中每個結(jié)點的孩子鏈表進(jìn)行逐個掃描。也就是說，查找一個結(jié)點的孩子可遍歷相應(yīng)的鏈表，而查找一個結(jié)點的雙親則要遍歷整個樹。3．孩子雙親表示法把雙親表示法和孩子鏈表表示法結(jié)合起來就是孩子雙親表示法。在這樣的存儲結(jié)構(gòu)中，查找一個結(jié)點的孩子可遍歷相應(yīng)的鏈表，而查找一個結(jié)點的雙親可從頭表中直接找到。4．孩子兄弟表示法該方法又稱為二叉樹表示法或二叉鏈表表示法。即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中每個結(jié)點的存儲結(jié)構(gòu)相同，都有3個域：數(shù)據(jù)域(data)存放結(jié)點的數(shù)據(jù)信息，孩子域(firstchild)存放該結(jié)點的第一個孩子結(jié)點（從左到右的順序）的地址，兄弟域(nextsibling)存放該結(jié)點的下一個兄弟結(jié)點（從左到右的順序）的地址。孩子兄弟結(jié)點結(jié)構(gòu)類型定義如下：typedef struct CSNode{Etype data。CSNode* firstchild,*nextsibling。}*CSTree。例如?？梢钥闯?，應(yīng)用孩子兄弟表示法的二叉鏈表來存儲有序樹的最大優(yōu)點是：（1）結(jié)點的結(jié)構(gòu)統(tǒng)一，（2）與二叉樹的二叉鏈表表示完全一樣，（3）可以利用對二叉樹的算法來實現(xiàn)對樹的操作。由于樹和二叉樹都可以用二叉鏈表作為存儲結(jié)構(gòu)，那么以二叉鏈表作為媒介可以導(dǎo)出樹與二叉樹之間的對應(yīng)關(guān)系：對于同一個二叉鏈表，當(dāng)按樹的存儲結(jié)構(gòu)（