數(shù)據(jù)結(jié)構(gòu)六樹

1、第六章二樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)§6.1 樹的定義« 定義v 定義：樹(tree)是n(n>0)個結(jié)點的有限集T，其中：l 有且僅有一個特定的結(jié)點，稱為樹的根(root)l 當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)v 特點：ll至少有一個結(jié)點根子樹是互不相交的集合只有根結(jié)點的樹A有子樹的樹根ABCDEFGHIJKLM子樹« 基本術(shù)語v 結(jié)點(node)表示指向其子樹的分支的元素，包括數(shù)據(jù)項及若干v 結(jié)點的度(degree)

2、結(jié)點擁有的子樹數(shù)v 葉子(leaf)度為0的結(jié)點v 孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子v 雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的v 兄弟(sibling)同一雙親的孩子v 樹的度一棵最大的結(jié)點度數(shù)v 結(jié)點的層次(level)從根結(jié)點算起，根為第一層， 它的孩子為第二層v 深度(depth)結(jié)點的最大層次數(shù)v 森林(forest)m(m³0)棵互不相交的樹的集合結(jié)點A的度：3 結(jié)點B的度：2 結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點I的雙親：D 結(jié)點L的雙親：E結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)A結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟BCD樹的

3、度：3EFGHIJ樹的深度：4KLM結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先結(jié)點A的層次：1 結(jié)點M的層次：4§6.2 二« 定義v 定義：二是n(n³0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子右子樹的互不相交的二v 特點l 每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)l 二的子樹有左、右之分，且其次序不能任意顛倒v 基本形態(tài)FAAAABBCB只有根結(jié)點樹均非空右子樹為空左子樹為空的二空二«二性質(zhì)的第 i層上至多有2i-1個結(jié)點(i ³ 1)v 性質(zhì)1：在二證明：用歸納法證明之i=1時，只有一個根結(jié)點，2i

4、-1= 1 是對的= 20假設(shè)對所有j(1£j<i)命題成立，即第j層上至多有2 j -1個結(jié)點那么，第i-1層至多有2i -2 個結(jié)點每個結(jié)點的度至多為2又二 第i層上最大結(jié)點數(shù)是第i-1層的2倍，即2 × 2i-2故命題得證= 2i-1至多有2k -1個結(jié)點(k³1)v 性質(zhì)2：深度為k的二證明：由性質(zhì)1，可得深度為k 的二最大結(jié)點數(shù)是kkå(第i層的最大結(jié)點數(shù) ) = å2i-1 = 2k -1i=1i=1v 性質(zhì)3：對任何一棵二T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1證明：n1為二因為：二T中度為1的結(jié)點

5、數(shù)中所有結(jié)點的度均小于或等于2所以：其結(jié)點總數(shù)n=n0+n1+n2又二分支進入中，除根結(jié)點外，其余結(jié)點都只有一個設(shè)B為分支總數(shù)，則n=B+1又：分支由度為1和度為2的結(jié)點射出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1« 幾種特殊形式的二v 滿二l 定義：一棵深度為k且有2k -1個結(jié)點的二l 特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)v 完全二稱為 l 定義：深度為k，有n個結(jié)點的二當且僅當其每一個結(jié)點都與深度為k的滿二的結(jié)點一一對應(yīng)時，稱為l 特點中編號從1至nu點只可能在層次最大的兩層上出現(xiàn)u 對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左

6、分支下子孫的最大層次必為l 或l+111232345456789111212323456764589101112l 性質(zhì)u 性質(zhì)4：具有n個結(jié)點的完全二的 深度為ëlog 2 nû + 1u 性質(zhì)5：如果對一棵有n個結(jié)點的完全二點按層序編號，則對任一結(jié)點i(1£i£n)，有：的結(jié)(1)如果i=1，則結(jié)點i是二的根，無雙親；如果i>1，則其雙親是ëi/2û；如果2i£n，則其(2)如果2i>n，則結(jié)點i無是2i如果2i+1>n，則結(jié)點i無右孩子；如果2i+1£n，(3)則其右孩子是2i+1§

7、;6.3 樹的« 樹的結(jié)構(gòu)結(jié)構(gòu)v 雙親表示法l 實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：u 數(shù)據(jù)域：存放結(jié)點本身信息u 雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置l 特點：找雙親容易，找孩子難typedef struct nodedatatypedata;int parent;JD;JDtM;0號單元不用或存結(jié)點個數(shù)adataparentbc0123456789fdeghi如何找孩子結(jié)點09a0b1c1d2e2f3g5h5i5v 孩子表示法l 多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根u 結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度Du 結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)

8、點的度dl 孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表孩子結(jié)點：typedefstructnode，再用含n個int child;/該結(jié)點在表頭數(shù)組中下標struct node *next;JD;/指向下一孩子結(jié)點表頭結(jié)點：typedefstruct tnodedatatypedata;/數(shù)據(jù)域/指向第一個孩子結(jié)點struct node *fc;TD;TDtM;/t0不用datadegreechild1child2 .childddatachild1child2.childDabcdatafcfde0123456789ghi如何找雙親結(jié)點46abcdefghil 帶雙親

9、的孩子鏈表parentdatafca123456789bcfdeghi987546a0b1c1d2e2f3g5h5i532v 孩子兄弟表示法（二l 實現(xiàn)：用二叉鏈表作樹的表示法）結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點l 特點u 操作容易u 破壞了樹的層次typedef struct nodedatatypedata;structJD;node*fch,*nsib;abcfdeghiihgefdcba«二v 順序的結(jié)構(gòu)結(jié)構(gòu)l 實現(xiàn)：按滿二據(jù)元素l 特點：u 結(jié)點間關(guān)系蘊含在其u 浪費空間，適于存滿二的結(jié)點層次編號，依次存放二中的數(shù)位置中和完全二a123

10、4567891011bcdefgabcde0000fgv 鏈式結(jié)構(gòu)l 二叉鏈表struct BiTNodetypedefdatatypedata;struct BiTNode*lchild,*rchild; BiTNode; * BiTree;ABCDFEG在n個結(jié)點的二叉鏈表中，有n+1個空指針域GFEDCBAlchilddatarchildl 三叉鏈表typedefstruct TriTNodedatatypedata;structnode *lchild,*rchild,*parent; TriTNode, TriTree;ABCDFEGGFECDBAlchilddataparentrc

11、hild« 樹與二樹A轉(zhuǎn)換二A對應(yīng)BBCECDDEEDDCECBBAAECDBAv 將樹轉(zhuǎn)換成二l 加線：在兄弟之間加一連線l 抹線：對每個結(jié)點，除了其間的關(guān)系外，去除其與其余孩子之l 旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45°AAABCDBCDBCDEFGHIEFGHIEFGHIAABECBCDFDEFGHIGHI樹轉(zhuǎn)換成的二其右子樹一定為空v 將二轉(zhuǎn)換成樹l 加線：若p結(jié)點是雙親結(jié)點的，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來l 抹線：抹掉原二中雙親與右孩子之間的連線l 調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)AAAABBBBECEC

12、ECECFDFDFDFDGGHHGGHHIIIIABCDEFGHIv 森林轉(zhuǎn)換成二l 將各棵樹分別轉(zhuǎn)換成二l 將每棵樹的根結(jié)點用線相連l 以第一棵樹根結(jié)點為二的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，E二G型結(jié)構(gòu)AGEABHHIFBCDFICJDJAAEGBEBHGFCFCIHDDJIJv二轉(zhuǎn)換成森林l 抹線：將二中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二l 還原：將孤立的二還原成樹AGAEABEBHGBFECFCIGHDCFDJIHDJIJEGAHIFBCDJ§6.4二的遍歷« 樹的遍歷v 遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅

13、被一次，即找一個完整而有規(guī)律的走法，以得到所有結(jié)點的一個線性排列v 常用方法l 先根（序）遍歷：先每棵子樹l 后根（序）遍歷：先依次后根遍歷每棵子樹，然后樹的根結(jié)點，然后依次先根遍歷根的根結(jié)點l 按層次遍歷：先第一層上的結(jié)點，然后依次遍歷第二層，第n層的結(jié)點ABCDGEFHJKLMINO先序遍歷：A B E F IH J K L N O M后序遍歷：E I F G B C J K N O L M H D A層次遍歷：A B C D E F G H I J K L MN O«二v 方法l 先序遍歷：先的遍歷根結(jié)點,然后分別先序遍歷左子樹、右子樹l 中序遍歷：先中序遍歷左子樹，然后遍歷右

14、子樹根結(jié)點，最后中序l 后序遍歷：先后序遍歷樹，然后根結(jié)點l 按層次遍歷：從上到下、從左到右各結(jié)點DLRLDR、LRD、DLR RDL、RLD、DRL-+/a*efb-cd先序遍歷： -+a * bb * c- cd / e fa +a b- d - e / f中序遍歷：cd-*+ef/-后序遍歷：- + / a * e f b - c d層次遍歷：中序遍歷:AACBDBC算法的遞歸定義是：若二為空，則遍歷結(jié)束；否則 中序遍歷左子樹(遞歸調(diào)用本算法)；D根結(jié)點； 中序遍歷右子樹(遞歸調(diào)用本算法)。中序遍歷序列：BDACv 中序遍歷的遞歸算法voidInorderTraverse(BTNode*

15、T)if(T!=NULL)InorderTraverse(T->Lchild) ;visit(T->data) ;/*/根結(jié)點InorderTraverse(T->Rchild) ;中序遍歷非遞歸算法思路：設(shè)T是指向二算法是：根結(jié)點的指針變量，非遞歸為空，則返回；否則，令p=T若二 若p不為空，p進棧， p=p->Lchild ； 否則(即p為空)，退棧到p，的結(jié)點； p=p->Rchild ，轉(zhuǎn)(1)； 直到棧空為止。p所指向中序遍歷的非遞歸算法：#define MAX_NODE 50void InorderTraverse( BTNode *T)BTNode

16、*StackMAX_NODE ,*p=T ; int top=0 , bool=1 ;if (T=NULL) printf(“ Binary Tree is Empty!n”) ;else do while (p!=NULL) stack+top=p ;if (top=0) bool=0 ;else p=stacktop ;p=p->Lchild ; /*向左走到盡頭*/*?？毡闅v結(jié)束*/top- ;visit( p->data ) ; p=p->Rchild ; / while (bool!=0) ;*/結(jié)點，l 中序遍歷的非遞歸算法執(zhí)行過程ppAABBiCDCDiEFEF

17、(2)G(1)GAABBpiiCDCDp=NULLFFEE(3)(4)GG：CP->BP->AP->CP->BP->AP->AP->BP->AApABpBCDiCDiFEFE(5)(6)GGAABBiiCDCDFEFEp：C B E：C BGG(8)(7)pP->DP->AP->EP->DP->AP->DP->AP->AAABiBiCDCDFEFEGP=NULLA(9)(10)GpABpBpiCDCDiEFFEGG(12)(11)：C B E G D：C B E G DP->AP->FP

18、->A：C B E G：C B EP->DP->AP->GP->DP->ApAABBCDCDiEFiFEp=NULLG(14)G(13)p=NULLABCDEFiG(15)：C B E G D F A：C B E G D F：C B E G D F AP->A先序遍歷:AACBDBC算法的遞歸定義是：若二為空，則遍歷結(jié)束；否則D根結(jié)點； 先序遍歷左子樹(遞歸調(diào)用本算法)； 先序遍歷右子樹(遞歸調(diào)用本算法)。先序遍歷序列：A BD Cv 先序遍歷的遞歸算法void PreorderTraverse(BTNode if (T!=NULL)*T) visit

19、(T->data) ;/*根結(jié)點 */PreorderTraverse(T->Lchild) ;PreorderTraverse(T->Rchild) ;說明：visit()函數(shù)是結(jié)點的數(shù)據(jù)域，其要求視具體問題而定。用二叉鏈表的結(jié)構(gòu)，用指針變量T來指向。voidPreorderTraverse(BTNode *T) (T!=NULL)printf("%dt",bt->data);/*Aif根結(jié)點 */BC左是空返回右是空返回D左是空返回右是空返回PreorderTraverse(T->Lchild) ;左是空返回PreorderTraverse

20、(T->Rchild) ;DA主程序printf(A);pre(TL);Pre( T )pre(TR);C先序序列：ABDCprintf(C);pre(TL);pre(TR);printf(D);pre(TL);pre(TR);返回T返回T返回TT返回TTT返回TBprintf(B);pre(TL);pre(TR);T先序遍歷的非遞歸算法設(shè)T是指向二法是：根結(jié)點的指針變量，非遞歸算為空，則返回；否則，令p=T；若二p所指向的結(jié)點； q=p->Rchild ，若q不為空，則q進棧； p=p->Lchild ，若p不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)(4)； 退棧到p ，轉(zhuǎn)(1)，直到?？諡?/p>

21、止。#define MAX_NODE 50voidPreorderTraverse( BTNode *T)BTNode *StackMAX_NODE ,*p=T, *q ; int top=0 ;if (T=NULL) printf(“ Binary Tree is Empty!n”) ;else do visit( p-> data ) ;q=p->Rchild ;if ( q!=NULL ) stack+top=q ; p=p->Lchild ;if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ;后序遍歷:AACBDBC算法的

22、遞歸定義是：若二為空，則遍歷結(jié)束；否則 后序遍歷左子樹(遞歸調(diào)用本算法)； 后序遍歷右子樹(遞歸調(diào)用本算法) ；D根結(jié)點 。后序遍歷序列： DBCAv 后序遍歷的遞歸算法voidPostorderTraverse(BTNode*T)if(T!=NULL)PostorderTraverse(T->Lchild) ;PostorderTraverse(T->Rchild) ;visit(T->data) ;/*根結(jié)點 */遍歷二的算法中基本操作是結(jié)點，因此，無論是哪種次序的遍歷，對有n個結(jié)點的二叉樹，其時間復(fù)雜度均為O(n) 。后序遍歷的非遞歸算法在后序遍歷中，根結(jié)點是最后被的。

23、因此，在遍歷過程中，當搜索指針指向某一根 結(jié)點時，不能立即，而要先遍歷其左子樹，此時根結(jié)點進棧。當其左子樹遍歷完后再搜索到該根結(jié)點時，還是不能，還需遍歷其右子樹。所以，此根結(jié)點還需再次進棧，當其右子樹遍歷完后再退棧到到該根結(jié)點時，才能被。因此，設(shè)立一個狀態(tài)標志變量tag ：0 ： 結(jié)點暫不能tag=1 ： 結(jié)點可以被其次，設(shè)兩個堆棧S1、S2 ，S1保存結(jié)點，S2保存結(jié)點的狀態(tài)標志變量tag 。S1和S2共用一個棧頂指針。設(shè)T是指向根結(jié)點的指針變量，非遞歸算法是：若二為空，則返回；否則，令p=T；第一次經(jīng)過根結(jié)點p，不：p進棧S1 ， tag 賦值0，進棧S2，p=p->Lchild 。

24、若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標志值tag ： 若tag=0：對棧S1，不，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1top->Rchild ，轉(zhuǎn)(1)； 若tag=1：S1退棧，直到?？諡橹?。該結(jié)點；算法實現(xiàn)：#define MAX_NODE 50voidPostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE , top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else dowhile

25、 (p!=NULL) S1+top=p ; S2top=0 ;p=p->Lchild ;if (top=0) bool=0 ; else if (S2top=0) p=S1top->Rchild ; S2top=1 ;else p=S1top ; top- ;visit( p->data ) ; p=NULL ;/* 使循環(huán)繼續(xù)進行而不至于死循環(huán)*/ while (bool!=0) ;層次遍歷二層次遍歷二序“自上而下，從，是從根結(jié)點開始遍歷，按層次次”的各結(jié)點。為保證是按層次遍歷，必須設(shè)置一個隊列，初始化時為空。設(shè)T是指向根結(jié)點的指針變量，層次遍歷非遞歸算 法是：為空，則返回

26、；否則，令p=T，p入隊；若二 隊首元素出隊到p；p所指向的結(jié)點；將p所指向的結(jié)點的到隊空為止。結(jié)點依次入隊。直#define MAX_NODE50voidLevelorderTraverse( BTNode*T)BTNode*QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if(p!=NULL)Queue+rear=p;while (front<rear)/*根結(jié)點入隊*/p=Queue+front; visit( p->data );if (p->Lchild!=NULL)Queue+rear=p; if (p->Rchild!

27、=NULL)Queue+rear=p;/*/左結(jié)點入隊/*左結(jié)點入隊*/v 遍歷算法應(yīng)用l “遍歷”是二最重要的基本操作，是各種其它操作的基礎(chǔ)，二的許多其它操作都可以通過遍歷來實現(xiàn)。如建立二的結(jié)構(gòu)、求二的結(jié)點數(shù)、求二的深度等。l 按先序遍歷序列建立二的二叉鏈表，已知先序序列為：F F中F G F F F F點個數(shù)算法FFA B Cl 統(tǒng)計二D EAl 求二深度算法BCDFEGGFEDCBA（1）按先序遍歷方式建立二叉鏈表對一棵二樹所擴充的二進行“擴充”，就可以得到有該二叉。AACBCBDEFFDEGG(a)二T1(b)T1的擴充二T2?二的擴充方法是：在二中結(jié)點的每一個空鏈點，用方框“”域處增

28、加一個擴充的結(jié)點(總是表示)。對于二的結(jié)點值： 是char類型：擴充結(jié)點值為“？”； 是int類型：擴充結(jié)點值為0或-1；下面的算法是二的前序創(chuàng)建的遞歸算法，讀入一的前序遍歷的結(jié)點值序列。每棵二對應(yīng)的擴充二讀入一個結(jié)點值就進行分析：指針為NULL； 若是擴充結(jié)點值： 若是(正常)結(jié)點值：動態(tài)地為根指針分配一個結(jié)點，將該值賦給根結(jié)點，然后遞歸地創(chuàng)建根的左子 右子樹。利用先序序列創(chuàng)建二叉鏈表算法實現(xiàn)：#define NULLKY ?#define MAX_NODEtypedef struct BTNodechar data ;50struct BTNode *Lchild , *Rchild ;B

29、TNode ;BTNode*Preorder_Create_BTree(BTNode *T)/*/建立鏈式二，返回指向根結(jié)點的指針變量char ch ;ch=getchar() ; getchar(); if (ch=NULLKY)T=NULL;return(T) ; elseT=(BTNode *)malloc(sizeof(BTNode) ; T>data=ch ; Preorder_Create_BTree(T->Lchild) ; Preorder_Create_BTree(T->Rchild) ;return(T) ;創(chuàng)建圖6-10(a)所示的二時，輸入的字符序列應(yīng)

30、當是：ABD?E?G?CF?（2）求二的點數(shù)算法求二算法中可以直接利用先序遍歷二點數(shù)。只要將先序遍歷二的visit()函數(shù)簡單地進行修改就可以。#define MAX_NODE 50intsearch_leaves( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int top=0, num=0; if (T!=NULL)stack+top=p ; while (top>0) p=stacktop- ;if (p->Lchild=NULL&&p->Rchild=NULL) if (p->Rchild!=NULL )stac

31、k+top=p->Rchild; if (p->Lchild!=NULL )stack+top=p->Lchild;num+ ;return(num) ;（3）求二的深度利用層次遍歷算法可以直接求得二算法實現(xiàn)：#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T; int front=0 , rear=0, depth=0, level ;的深度。/* level總是指向if (T!=NULL) Queue+rear=p;層的最后一個結(jié)點在隊列的位置 */*根結(jié)點入隊 */lev

32、el=rear ;/* 根是第1層的最后一個節(jié)點 */while (front<rear)p=Queue+front;if (p->Lchild!=NULL) Queue+rear=p;if (p->Rchild!=NULL)Queue+rear=p; if (front=level)/*左結(jié)點入隊*/*/左結(jié)點入隊/* 正的是當前層的最后一個結(jié)點 */ depth+ ; level=rear ; 6.5線索二遍歷二是按一定的規(guī)則將的結(jié)點排列成一個線性序列，即是對非線性結(jié)構(gòu)的線性化操作。如何找到遍歷過程中動態(tài)得到的每個結(jié)點的直接前驅(qū)和直接后繼(第一個和最后一個除外)?如何保存

33、這些信息?有n個結(jié)點，則有n-1條邊(指針連線) ， 而n設(shè)一棵二個結(jié)點共有2n個指針域(Lchild和Rchild) ，顯然有n+1個空閑指針域未用。則可以利用這些空閑的指針域來存放結(jié)點的直 接前驅(qū)和直接后繼信息。對結(jié)點的指針域做如下規(guī)定： 若結(jié)點有向其直接前驅(qū)； 若結(jié)點有右孩子，則Rchild指向其右孩子，否則，指向其直接后繼；，則Lchild指向其，否則，指,對結(jié)點結(jié)構(gòu)加以改進，增加兩個標志域，如圖6-為避免10所示。線索二的結(jié)點結(jié)構(gòu)0：Lchild域指示結(jié)點的Ltag=1：Lchild域指示結(jié)點的前驅(qū)0：Rchild域指示結(jié)點的右孩子Rtag=1：Rchild域指示結(jié)點的后繼Lchil

34、dLtagdataRchildRtag用這種結(jié)點結(jié)構(gòu)的二的結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點前驅(qū)和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二稱之為線索二。線索二的結(jié)點結(jié)構(gòu)與示例typedef struct BiThrNodeElemType data;struct BiTreeNode *Lchild , *Rchild ; int Ltag , Rtag ;BiThrNode ;AACBCBFDEFDENILHIGHIG(b)先序線索樹的邏輯形式結(jié)點序列：ABDCEGFHIA(a)二ACCBBNILNILFNILFDEDEHIHIGG(c)中序線索樹的邏輯形式結(jié)點序列：DBAGECHFI(

35、d)后序線索樹的邏輯形式結(jié)點序列：DBGEHIFCA(e)中序線索樹的鏈表結(jié)構(gòu)說明：畫線索二時，實線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅(qū)或直接后繼。索樹上進行遍歷，只要先找到序列中的第一個結(jié)點， 然后就可以依次找結(jié)點的直接后繼結(jié)點直到后繼為空為止。1F11H11 G10F00E11 D10C00B10A0如何索找結(jié)點的直接后繼?結(jié)點的右鏈都是線索。右鏈直接所指示了結(jié)點的直接后繼，如結(jié)點G的直接后繼是結(jié)點E。所有非點的右鏈都是指針。根據(jù)中點的直接后繼是遍歷其右序遍歷的規(guī)律，非子樹時(的第一個結(jié)點，即右子最左下的點。如結(jié)點C的直接后繼：沿右指針找到右子樹的根結(jié)點F，然后沿結(jié)點即

36、為C的直接后繼結(jié)點H。往下直到Ltag=1的如何索找結(jié)點的直接前驅(qū)?若結(jié)點的是線索，指示其直接前驅(qū)；否則，Ltag=1，則遍歷左子樹時右往下的結(jié)點)的最后一個結(jié)點(即沿左子為其直接前驅(qū)結(jié)點。最對于后序遍歷的線索復(fù)雜，可分以下三種情況：找結(jié)點的直接后繼比較 點沒若結(jié)點是二的根結(jié)點：其直接后繼為空；若結(jié)點是其父結(jié)點的或右孩子且其父結(jié)樹：直接后繼為其父結(jié)點；若結(jié)點是其父結(jié)點的且其父結(jié)點樹：直接后繼是對其父結(jié)點的右子樹按后序遍歷的第一個結(jié)點。6.5.1二線索化二的線索化指的是依照某種遍歷次序使二叉樹成為線索二的過程。線索化的過程就是在遍歷過程中修改空指針使其指向直接前驅(qū)或直接后繼的過程。仿照線性表的結(jié)

37、構(gòu)，在二的線索鏈表上也添加一個頭結(jié)點head，頭結(jié)點的指針域的安排是： Lchild域：指向二的根結(jié)點； Rchild域：指向中序遍歷時的最后一個結(jié)點；中序序列中的第一個結(jié)點Lchild指針域和 二最后一個結(jié)點Rchild指針域均指向頭結(jié)點head。如同為二建立了一個雙向線索鏈表，對一 棵線索二既可從頭結(jié)點也可從最后一個結(jié)點開始按尋找直接后繼進行遍歷。顯然，這種遍歷不需要堆棧，如圖6-12所示。結(jié)點類型定義#defineMAX_NODE50typedef enmuLink , Thread PointerTag ;/* Link=0表示指針， Thread=1表示線索typedef struc

38、t BiThrNode*/ElemTypedata;struct BiTreeNode *Lchild , *Rchild ;PointerTagBiThrNode;Ltag , Rtag ;AACBBCNILFDEFNILDEHIG(a)HIGhead二(b)中序線索樹的邏輯形式Thrt0F 0(c)中序線索二叉鏈表中序線索二及其結(jié)構(gòu)1F11H11 G10E11 D10C00B10A0011先序線索化二void preorder_Threading(BiThrNode *T)BiThrNode *stackMAX_NODE;BiThrNodeint top=0 ;*last=NULL, *p

39、 ;if(T!=NULL)stack+top=T;while (top>0)p=stacktop- ;if (p->Lchild!=NULL)p->Ltag=0 ;else p->Ltag=1 ; p->Lchild!=last ;if (last!=NULL)if (last->Rchild!=NULL) last->Rtag=0 ;elselast->Rtag=1 ; last->Rchild!=p ;last=p ;if (p->Rchild!=NULL) stack+top=p->Rchild ;if (p->Lc

40、hild!=NULL)stack+top=p->Lchild ;Last->Rtag=1;/*點 */最后一個結(jié)點是2中序線索化二void inorder_Threading(BiThrNode *T)BiThrNode *stackMAX_NODE;BiThrNode *last=NULL, *p=T ; while (p!=NULL|top>0)int top=0 ;if (p!=NULL) stack+top=p; p=p->Lchild; else p=stacktop- ;if (p->Lchild!=NULL) p->Ltag=0 ; else

41、p->Ltag=1 ; p->Lchild!=last ; if (last!=NULL)if (last->Rchild!=NULL) last->Rtag=0 ;else last->Rtag=1 ; last->Rchild!=p ; last=p ;P=p->Rchild;last->Rtag=1; /*/最后一個結(jié)點是點6.5.2線索二的遍歷索二中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點在某種遍歷序列中的直接前驅(qū)或直接后繼。此外，索上進二上進行某種遍歷比在一般的二行這種遍歷要容易得多，不需要設(shè)置堆棧，且算法十分簡潔。1先序線

42、索二的先序遍歷void preorder_Thread_bt(BiThrNode *T)BiThrNode*p=T ;while (p!=NULL)visit(p->data) ;if (p->Ltag=0)p=p->Lchild ;elsep=p->Rchild2中序線索二的中序遍歷void inorder_Thread_bt(BiThrNode *T)BiThrNode *p ;if(T!=NULL)p=T;while (p->Ltag=0 )p=p->Lchild;/* 尋找最左的結(jié)點*/while (p!=NULL)visit(p->data)

43、 ; if (p->Rtag=1)p=p->Rchild ;/* 通過右線索找到后繼*/else/* 否則，右子樹的最左結(jié)點為后繼 */ p=p->Rchild ;while (p->Ltag=0 ) p=p->Lchild;TABDCET中序序列：BCAED中序線索二頭結(jié)點：lt=0, lc指向根結(jié)點rt=1, rc指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的lc域和最后一個結(jié)點的rc域都指向頭結(jié)點中序序列：BCAED結(jié)點的中序線索二1E11C10D11B00A0011E11C10D11B00A0ABDCEiprbtpt010E00C00D00B00A0P->AJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t