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

1、第六章 樹和二叉樹 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)6.1 樹的定義定義定義：樹(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)根樹中各子樹是互不相交的集合A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹基本術(shù)語(yǔ)結(jié)點(diǎn)(node)表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點(diǎn)孩子(child)結(jié)點(diǎn)

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

3、6.2 二叉樹定義定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質(zhì)性質(zhì)1：) 1(21iii個(gè)結(jié)點(diǎn)層上至多有在二叉樹的第證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)， 是對(duì)的 假設(shè)對(duì)所有j(1j1，則其雙親是i/2l (2) 如果2in，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2il (3) 如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩

4、子；如果2i+1n，則其右孩子是2i+11log2nn深度為個(gè)結(jié)點(diǎn)的完全二叉樹的具有l(wèi)性質(zhì)l性質(zhì)4：6.3 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)雙親表示法實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)v孩子表示法v多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹的根v結(jié)點(diǎn)同

5、構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度Dv結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表孩子結(jié)點(diǎn)：typedef struct node int child; /該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點(diǎn) JD;表頭結(jié)點(diǎn)：typedef struct tnode datatype data; /數(shù)據(jù)域 struct node *fc; /指向第一個(gè)孩子結(jié)點(diǎn) TD

6、; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點(diǎn)l帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法（二叉樹表示法）v實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)v特點(diǎn)v操作容易v破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a

7、b c d e f g h i二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)v二叉鏈表typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild; BiTNode; * BiTree;lchild data rchild ABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域 AB C D

8、 E F Gl三叉鏈表typedef struct TriTNode datatype data; struct node *lchild, *rchild, *parent; TriTNode, TriTree;lchild data parent rchildABCDEFG A B C D E F G樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋v將樹轉(zhuǎn)換成二叉樹v加線：在兄弟之間加一連線v抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系v旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45ABCDEFGHI

9、ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空v將二叉樹轉(zhuǎn)換成樹v加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)v抹線：抹掉原二叉樹中雙親與右孩子之間的連線v調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林轉(zhuǎn)換成二叉樹v將各棵樹分別轉(zhuǎn)換成二叉樹v將每棵樹的根結(jié)點(diǎn)用線相連v以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABC

10、DEFGHIJABCDEFGHIJv二叉樹轉(zhuǎn)換成森林v抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹v還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6.4 樹和二叉樹的遍歷樹的遍歷遍歷按一定規(guī)律走遍樹的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列常用方法先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，第n層

11、的結(jié)點(diǎn)ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn)DLRLDR、LRD、DLRRDL、RLD、DRL-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a * b - c d / e f-+a*b-cd/

12、ef- +a *b - c d/e f-+a*b-c d/e fADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:算法的遞歸定義是：算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 中序遍歷左子樹中序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 中序遍歷右子樹中序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。v中序遍歷的遞歸算法中序遍歷的遞歸算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;visit

13、(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */InorderTraverse(T-Rchild) ; 中序遍歷非遞歸算法思路：中序遍歷非遞歸算法思路：設(shè)設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空，則返回；否則，若二叉樹為空，則返回；否則，令令p=T 若若p不為空，不為空，p進(jìn)棧，進(jìn)棧， p=p-Lchild ； 否則否則(即即p為空為空)，退棧到，退棧到p，訪，訪問問p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； p=p-Rchild ，轉(zhuǎn)，轉(zhuǎn)(1)；直到?？諡橹?。直到?？諡橹?。中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：#define M

14、AX_NODE 50void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走向左走到底到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結(jié)點(diǎn)，向右一步訪問結(jié)點(diǎn)，向右一步 /while; l中序遍歷的非遞歸算法執(zhí)行過(guò)程中序遍歷的非遞歸算法執(zhí)行過(guò)程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABC

15、DEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)

16、ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)ADBCD L RAD L RD L RBDCD L R算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷左子樹先序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 先序遍歷右子樹先序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)。先序遍歷:先序遍歷序列：A B D Cv先序遍歷的遞歸算法先序遍歷的遞歸算法void PreorderTraverse(BTNode *T) if (T!=NULL)

17、 visit(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 說(shuō)明：說(shuō)明：visit()函數(shù)是訪問結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問題而定。樹采函數(shù)是訪問結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問題而定。樹采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T來(lái)指向。來(lái)指向。void PreorderTraverse(BTNode *T) if (T!=NULL) printf(%dt,bt-data);/* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */PreorderTraverse(T-Lchil

18、d) ;PreorderTraverse(T-Rchild) ; 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C先序遍歷的非遞歸算法先序遍歷的非遞歸算法設(shè)設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針是指向二叉樹根結(jié)點(diǎn)的指針變量，非遞歸算法是：變量，非遞歸算法是：若二叉樹為空

19、，則返回；否則，若二叉樹為空，則返回；否則，令令p=T； 訪問訪問p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； q=p-Rchild ，若，若q不為空，不為空，則則q進(jìn)棧；進(jìn)棧； p=p-Lchild ，若，若p不為空，不為空，轉(zhuǎn)轉(zhuǎn)(1)，否則轉(zhuǎn)，否則轉(zhuǎn)(4)； 退棧到退棧到p ，轉(zhuǎn)，轉(zhuǎn)(1)，直到棧空，直到棧空為止。為止。先序遍歷的非遞歸算法先序遍歷的非遞歸算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL

20、 ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結(jié)點(diǎn)，訪問結(jié)點(diǎn)，向右一步向右一步 /wh

21、ile ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B算法的遞歸定義是：算法的遞歸定義是： 若二叉樹為空，則遍歷結(jié)束；否則若二叉樹為空，則遍歷結(jié)束；否則 后序遍歷左子樹后序遍歷左子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 后序遍歷右子樹后序遍歷右子樹(遞歸調(diào)用本算法遞歸調(diào)用本算法) ； 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 。v后序遍歷的遞歸算法后序遍歷的遞歸算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T-Lchild) ;PostorderTraverse(T-Rchil

22、d) ; visit(T-data) ; /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */ 遍歷二叉樹的算法中基本操作是訪問結(jié)點(diǎn)，因遍歷二叉樹的算法中基本操作是訪問結(jié)點(diǎn)，因此，無(wú)論是哪種次序的遍歷，對(duì)有此，無(wú)論是哪種次序的遍歷，對(duì)有n個(gè)結(jié)點(diǎn)的二叉?zhèn)€結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)雜度均為樹，其時(shí)間復(fù)雜度均為O(n) 。后序遍歷的非遞歸算法后序遍歷的非遞歸算法 在后序遍歷中，根結(jié)點(diǎn)是最在后序遍歷中，根結(jié)點(diǎn)是最后被訪問的。因此，在遍歷過(guò)程后被訪問的。因此，在遍歷過(guò)程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不能立即訪問，而要先遍歷時(shí)，不能立即訪問，而要先遍歷其左子樹，此時(shí)根結(jié)點(diǎn)進(jìn)棧。當(dāng)其左子樹，此時(shí)根結(jié)點(diǎn)

23、進(jìn)棧。當(dāng)其左子樹遍歷完后再搜索到該根其左子樹遍歷完后再搜索到該根結(jié)點(diǎn)時(shí)，還是不能訪問，還需遍結(jié)點(diǎn)時(shí)，還是不能訪問，還需遍歷其右子樹。所以，此根結(jié)點(diǎn)還歷其右子樹。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧，當(dāng)其右子樹遍歷完需再次進(jìn)棧，當(dāng)其右子樹遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪問。被訪問。 因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量量tag ：0 ： 結(jié)點(diǎn)暫不能訪問結(jié)點(diǎn)暫不能訪問1 ： 結(jié)點(diǎn)可以被訪問結(jié)點(diǎn)可以被訪問tag= 其次，設(shè)兩個(gè)堆棧S1、S2 ，S1保存結(jié)點(diǎn)，S2保存結(jié)點(diǎn)的狀態(tài)標(biāo)志變量tag 。S1和S2共用一個(gè)棧頂指針。 設(shè)T是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是

24、：若二叉樹為空，則返回；否則，令p=T； 第一次經(jīng)過(guò)根結(jié)點(diǎn)p，不訪問： p進(jìn)棧S1 ， tag 賦值0，進(jìn)棧S2，p=p-Lchild 。 若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值tag ： 若tag=0：對(duì)棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1top-Rchild ，轉(zhuǎn)(1)； 若tag=1：S1退棧，訪問該結(jié)點(diǎn)；直到棧空為止。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：#define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE

25、, top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (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ù)進(jìn)行而不至于死使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán)循環(huán) */ while (bool!=0) ;層次遍歷二叉樹層次遍歷二

26、叉樹 層次遍歷二叉樹，是從根結(jié)點(diǎn)開始遍歷，按層次次層次遍歷二叉樹，是從根結(jié)點(diǎn)開始遍歷，按層次次序序“自上而下，從左至右自上而下，從左至右”訪問樹中的各結(jié)點(diǎn)。訪問樹中的各結(jié)點(diǎn)。 為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化時(shí)為空。時(shí)為空。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算法是：法是：若二叉樹為空，則返回；否則，令若二叉樹為空，則返回；否則，令p=T，p入隊(duì)；入隊(duì)； 隊(duì)首元素出隊(duì)到隊(duì)首元素出隊(duì)到p；訪問訪問p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； 將將p所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)所指向的結(jié)點(diǎn)的左

27、、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止?？諡橹埂?define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根結(jié)點(diǎn)入隊(duì)根結(jié)點(diǎn)入隊(duì) */while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ v遍歷算法應(yīng)用v

28、“遍歷”是二叉樹最重要的基本操作，是各種其它操作的基礎(chǔ)，二叉樹的許多其它操作都可以通過(guò)遍歷來(lái)實(shí)現(xiàn)。如建立二叉樹的存儲(chǔ)結(jié)構(gòu)、求二叉樹的結(jié)點(diǎn)數(shù)、求二叉樹的深度等。v按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：v A B C D E G F l求二叉樹深度算法ABCDEFG A B C D E F G l統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法（1）按先序遍歷方式建立二叉鏈表）按先序遍歷方式建立二叉鏈表 對(duì)一棵二叉樹進(jìn)行對(duì)一棵二叉樹進(jìn)行“擴(kuò)充擴(kuò)充”，就可以得到有該二叉，就可以得到有該二叉樹所擴(kuò)充的二叉樹。樹所擴(kuò)充的二叉樹。ABCDEFG(a) 二叉樹二叉樹T1(b) T1的擴(kuò)充二叉樹的擴(kuò)充二叉樹T2AB

29、CDEFG? 二叉樹的擴(kuò)充方法是：在二叉樹中結(jié)點(diǎn)的每一個(gè)空鏈二叉樹的擴(kuò)充方法是：在二叉樹中結(jié)點(diǎn)的每一個(gè)空鏈域處增加一個(gè)擴(kuò)充的結(jié)點(diǎn)域處增加一個(gè)擴(kuò)充的結(jié)點(diǎn)(總是葉子結(jié)點(diǎn)，用方框總是葉子結(jié)點(diǎn)，用方框“”表示表示)。對(duì)于二叉樹的結(jié)點(diǎn)值：。對(duì)于二叉樹的結(jié)點(diǎn)值： 是是char類型：擴(kuò)充結(jié)點(diǎn)值為類型：擴(kuò)充結(jié)點(diǎn)值為“？”； 是是int類型：擴(kuò)充結(jié)點(diǎn)值為類型：擴(kuò)充結(jié)點(diǎn)值為0或或-1； 下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一棵二叉樹對(duì)應(yīng)的擴(kuò)充二叉樹的前序遍歷的結(jié)點(diǎn)值序列。每棵二叉樹對(duì)應(yīng)的擴(kuò)充二叉樹的前序遍歷的結(jié)點(diǎn)值序列。每讀入一個(gè)結(jié)點(diǎn)值就進(jìn)行分析：讀入一個(gè)結(jié)點(diǎn)

30、值就進(jìn)行分析： 若是擴(kuò)充結(jié)點(diǎn)值：令根指針為若是擴(kuò)充結(jié)點(diǎn)值：令根指針為NULL； 若是若是(正常正常)結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針分配一個(gè)結(jié)點(diǎn)，將結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針分配一個(gè)結(jié)點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹和右子樹。該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹和右子樹。利用先序序列創(chuàng)建二叉鏈表算法實(shí)現(xiàn)：利用先序序列創(chuàng)建二叉鏈表算法實(shí)現(xiàn)：#define NULLKY ?#define MAX_NODE 50typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;BTNode *Preorder_Cr

31、eate_BTree(BTNode *T) /* 建立鏈?zhǔn)蕉鏄洌祷刂赶蚋Y(jié)點(diǎn)的指針變量建立鏈?zhǔn)蕉鏄?，返回指向根結(jié)點(diǎn)的指針變量 */ char ch ; ch=getchar() ; getchar(); if (ch=NULLKY) T=NULL; return(T) ; else T=(BTNode *)malloc(sizeof(BTNode) ;Tdata=ch ;Preorder_Create_BTree(T-Lchild) ;Preorder_Create_BTree(T-Rchild) ;return(T) ; 當(dāng)希望創(chuàng)建圖當(dāng)希望創(chuàng)建圖6-10(a)所示的二叉樹時(shí)，輸入的字符

32、序列應(yīng)當(dāng)是：所示的二叉樹時(shí)，輸入的字符序列應(yīng)當(dāng)是：ABD?E?G?CF?（2）求二叉樹的葉子結(jié)點(diǎn)數(shù)）求二叉樹的葉子結(jié)點(diǎn)數(shù) 可以直接利用先序遍歷二叉可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結(jié)點(diǎn)數(shù)。樹算法求二叉樹的葉子結(jié)點(diǎn)數(shù)。只要將先序遍歷二叉樹算法中只要將先序遍歷二叉樹算法中visit()函數(shù)簡(jiǎn)單地進(jìn)行修改就可以函數(shù)簡(jiǎn)單地進(jìn)行修改就可以。#define MAX_NODE 50int search_leaves( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) if (p-Lchild=NULL) & (p-Rchild

33、=NULL ) num+ ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /whilereturn(num) ;（3）求二叉樹的深度）求二叉樹的深度 利用層次遍歷算法可以直接求得利用層次遍歷算法可以直接求得二叉樹的深度。二叉樹的深度。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int front=0 , rear=0, depth=0, level ;/* l

34、evel總是指向訪問層的最后一總是指向訪問層的最后一個(gè)結(jié)點(diǎn)在隊(duì)列的位置個(gè)結(jié)點(diǎn)在隊(duì)列的位置 */if (T!=NULL) Queue+rear=p; /* 根結(jié)根結(jié)點(diǎn)入隊(duì)點(diǎn)入隊(duì) */level=rear ; /* 根是第根是第1層的最層的最后一個(gè)節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn) */while (frontLchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì)左結(jié)點(diǎn)入隊(duì) */ if (front=level) /* 正訪問的是當(dāng)前層的最后一個(gè)結(jié)點(diǎn)正訪問的是當(dāng)前層的最后一個(gè)結(jié)點(diǎn) */ depth+

35、 ; level=rear ; 遍歷二叉樹是按一定的規(guī)則將樹中的結(jié)點(diǎn)排列成一個(gè)線性序列，即是對(duì)非線性結(jié)構(gòu)的線性化操作。如何找到遍歷過(guò)程中動(dòng)態(tài)得到的每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼(第一個(gè)和最后一個(gè)除外)?如何保存這些信息? 設(shè)一棵二叉樹有n個(gè)結(jié)點(diǎn)，則有n-1條邊(指針連線) ， 而n個(gè)結(jié)點(diǎn)共有2n個(gè)指針域(Lchild和Rchild) ，顯然有n+1個(gè)空閑指針域未用。則可以利用這些空閑的指針域來(lái)存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。對(duì)結(jié)點(diǎn)的指針域做如下規(guī)定： 6.5線索二叉樹線索二叉樹 若結(jié)點(diǎn)有左孩子，則若結(jié)點(diǎn)有左孩子，則Lchild指向其左孩子，否指向其左孩子，否則，指向其直接前驅(qū)；則，指向其直接前

36、驅(qū)； 若結(jié)點(diǎn)有右孩子，則若結(jié)點(diǎn)有右孩子，則Rchild指向其右孩子，否指向其右孩子，否則，指向其直接后繼；則，指向其直接后繼；為避免混淆為避免混淆,對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域，如圖所示。域，如圖所示。Lchild Ltag data Rchild Rtag線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)0：Lchild域指示結(jié)點(diǎn)的左孩子1 1：LchildLchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū)Ltag=0 0：RchildRchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 1：RchildRchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼Rtag= 用這種結(jié)點(diǎn)結(jié)

37、構(gòu)構(gòu)成的二叉樹的存儲(chǔ)結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)與示例typedef struct BiThrNode ElemType data;struct BiTreeNode *Lchild , *Rchild ; int Ltag , Rtag ;BiThrNode ; AFHIEGBDC(a) 二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹的邏輯形式后序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBGEHIFCA(

38、c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 (e) 中序線索樹的鏈表結(jié)構(gòu)中序線索樹的鏈表結(jié)構(gòu)說(shuō)明：畫線索二叉樹時(shí)，實(shí)線表示指針，指向其左、右孩子；說(shuō)明：畫線索二叉樹時(shí)，實(shí)線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅(qū)或直接后繼。虛線表示線索，指向其直接前驅(qū)或直接后繼。 在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，在線索樹上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后就可以依

39、次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。 如何在線索樹中找結(jié)點(diǎn)的直接后繼如何在線索樹中找結(jié)點(diǎn)的直接后繼? ? 樹中所有葉子結(jié)點(diǎn)的右鏈都是線索。右鏈直接樹中所有葉子結(jié)點(diǎn)的右鏈都是線索。右鏈直接指示了結(jié)點(diǎn)的直接后繼，如結(jié)點(diǎn)指示了結(jié)點(diǎn)的直接后繼，如結(jié)點(diǎn)G G的直接后繼是結(jié)點(diǎn)的直接后繼是結(jié)點(diǎn)E E。 樹中所有非葉子結(jié)點(diǎn)的右鏈都是指針。根據(jù)中序樹中所有非葉子結(jié)點(diǎn)的右鏈都是指針。根據(jù)中序遍歷的規(guī)律，非葉子結(jié)點(diǎn)的直接后繼是遍歷其右子樹遍歷的規(guī)律，非葉子結(jié)點(diǎn)的直接后繼是遍歷其右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)，即右子樹中最左下的時(shí)訪問的第一個(gè)結(jié)點(diǎn)，即右子樹中最左下的(

40、 (葉子葉子) )結(jié)結(jié)點(diǎn)。如結(jié)點(diǎn)點(diǎn)。如結(jié)點(diǎn)C C的直接后繼：沿右指針找到右子樹的根的直接后繼：沿右指針找到右子樹的根結(jié)點(diǎn)結(jié)點(diǎn)F F，然后沿左鏈往下直到，然后沿左鏈往下直到Ltag=1Ltag=1的結(jié)點(diǎn)即為的結(jié)點(diǎn)即為C C的直的直接后繼結(jié)點(diǎn)接后繼結(jié)點(diǎn)H H。 如何在線索樹中找結(jié)點(diǎn)的直接前驅(qū)?若結(jié)點(diǎn)的Ltag=1，則左鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn)(即沿左子樹中最右往下的結(jié)點(diǎn)) 為其直接前驅(qū)結(jié)點(diǎn)。 對(duì)于后序遍歷的線索樹中找結(jié)點(diǎn)的直接后繼比較復(fù)雜，可分以下三種情況： 若結(jié)點(diǎn)是二叉樹的根結(jié)點(diǎn)：其直接后繼為空； 若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子或右孩子且其父結(jié)點(diǎn)沒有右子樹：直接后

41、繼為其父結(jié)點(diǎn)； 若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子且其父結(jié)點(diǎn)有右子樹：直接后繼是對(duì)其父結(jié)點(diǎn)的右子樹按后序遍歷的第一個(gè)結(jié)點(diǎn)。6.5.1 線索化二叉樹線索化二叉樹 二叉樹的線索化指的是依照某種遍歷次序二叉樹的線索化指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過(guò)程。使二叉樹成為線索二叉樹的過(guò)程。 線索化的過(guò)程就是在遍歷過(guò)程中修改空指針線索化的過(guò)程就是在遍歷過(guò)程中修改空指針使其指向直接前驅(qū)或直接后繼的過(guò)程。使其指向直接前驅(qū)或直接后繼的過(guò)程。 仿照線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹的線索鏈仿照線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個(gè)頭結(jié)點(diǎn)表上也添加一個(gè)頭結(jié)點(diǎn)head，頭結(jié)點(diǎn)的指針域，頭結(jié)點(diǎn)的指針域的安排是：的安

42、排是： Lchild域：指向二叉樹的根結(jié)點(diǎn)；域：指向二叉樹的根結(jié)點(diǎn)； Rchild域：指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)域：指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)； 二叉樹中序序列中的第一個(gè)結(jié)點(diǎn)二叉樹中序序列中的第一個(gè)結(jié)點(diǎn)Lchild指針指針域和最后一個(gè)結(jié)點(diǎn)域和最后一個(gè)結(jié)點(diǎn)Rchild指針域均指向頭結(jié)點(diǎn)指針域均指向頭結(jié)點(diǎn)head。 如同為二叉樹建立了一個(gè)雙向線索鏈表，如同為二叉樹建立了一個(gè)雙向線索鏈表，對(duì)一棵線索二叉樹既可從頭結(jié)點(diǎn)也可從最后對(duì)一棵線索二叉樹既可從頭結(jié)點(diǎn)也可從最后一個(gè)結(jié)點(diǎn)開始按尋找直接后繼進(jìn)行遍歷。顯一個(gè)結(jié)點(diǎn)開始按尋找直接后繼進(jìn)行遍歷。顯然，這種遍歷不需要堆棧，如圖然，這種遍歷不需要堆棧，如圖6

43、-126-12所示。所示。結(jié)點(diǎn)類型定義結(jié)點(diǎn)類型定義#define MAX_NODE 50#define MAX_NODE 50typedef enmuLink , Thread PointerTag ;typedef enmuLink , Thread PointerTag ;/ /* * Link=0 Link=0表示指針，表示指針， Thread=1 Thread=1表示線索表示線索 * */ /typedef struct BiThrNodetypedef struct BiThrNode ElemType data; ElemType data;struct BiTreeNode st

44、ruct BiTreeNode * *Lchild , Lchild , * *Rchild ; Rchild ; PointerTag Ltag , Rtag ;PointerTag Ltag , Rtag ;BiThrNode;BiThrNode;(a) 二叉樹二叉樹(b) 中序線索樹的邏輯形式中序線索樹的邏輯形式AFHIEGBDCNILNILAFHIEGBDC中序線索二叉樹及其存儲(chǔ)結(jié)構(gòu)中序線索二叉樹及其存儲(chǔ)結(jié)構(gòu)(c) 中序線索二叉鏈表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1Thrt 0 1head 1 先序線索化二叉樹先

45、序線索化二叉樹 void preorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ;InitStack(S); while (p!=NULL) if (p-Lchild!=NULL) p-Ltag=0 else p-Ltag=1 ; p-Lchild=last ; if (p-Rchild!=NULL) push(S, p-Rchild) ; if (last!=NULL)if (last-Rchild!=NULL) last-Rtag=0 ;else last-Rtag=1 ; last-Rchild=p ; last=p ;p

46、=p-Lchild;if (p=NULL) pop(S,p) ;/ /whileLast-Rtag=1; /* 最后一個(gè)結(jié)點(diǎn)是葉子結(jié)最后一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)點(diǎn) */先序遍歷的非遞歸算法先序遍歷的非遞歸算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while2 中序線索化二叉樹中序線索化二叉

47、樹void inorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ; InitStack(S);while (p!=NULL| !StackEmpty(S)if (p!=NULL) push(S,p); p=p-Lchild; else pop(S,p) ; if (p-Lchild!=NULL) p-Ltag=0 ; else p-Ltag=1 ; p-Lchild=last ; if (last!=NULL) if (last-Rchild!=NULL) last-Rtag=0 ; else last-Rtag=1 ; las

48、t-Rchild=p ; last=p ; p=p-Rchild; last-Rtag=1; /* 最后一個(gè)結(jié)點(diǎn)是葉子結(jié)最后一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)點(diǎn) */中序遍歷的非遞歸算法：中序遍歷的非遞歸算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 訪問結(jié)點(diǎn)，

49、向右訪問結(jié)點(diǎn)，向右一步一步 /while 6.5.2 線索二叉樹的遍歷線索二叉樹的遍歷 在線索二叉樹中，由于有線索存在，在某在線索二叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點(diǎn)在某種遍歷些情況下可以方便地找到指定結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)或直接后繼。此外，在線索序列中的直接前驅(qū)或直接后繼。此外，在線索二叉樹上進(jìn)行某種遍歷比在一般的二叉樹上進(jìn)二叉樹上進(jìn)行某種遍歷比在一般的二叉樹上進(jìn)行這種遍歷要容易得多，不需要設(shè)置堆棧，且行這種遍歷要容易得多，不需要設(shè)置堆棧，且算法十分簡(jiǎn)潔。算法十分簡(jiǎn)潔。1 先序線索二叉樹的先序遍歷先序線索二叉樹的先序遍歷void preorder_Thread

50、_bt(BiThrNode *T) BiThrNode *p=T ;while (p!=NULL) visit(p-data) ; if (p-Ltag=0) p=p-Lchild ; else p=p-Rchild 在先序線索二叉樹中找結(jié)點(diǎn)后繼的方法：在先序線索二叉樹中找結(jié)點(diǎn)后繼的方法：（1）若）若Ltag=0, 則則Lchild域直接指向其后繼域直接指向其后繼（2）若）若Ltag=1, 則則Rchild域直接指向其后繼域直接指向其后繼2 中序線索二叉樹的中序遍歷中序線索二叉樹的中序遍歷void inorder_Thread_bt(BiThrNode *T) BiThrNode *p ;if

51、 (T!=NULL) p=T;while (p-Ltag=0 ) p=p-Lchild; /* 尋找最左的結(jié)點(diǎn)尋找最左的結(jié)點(diǎn) */while (p!=NULL) visit(p-data) ; if (p-Rtag=1) p=p-Rchild ; /* 通過(guò)右線索找通過(guò)右線索找到后繼到后繼 */ else /* 否則，右子樹的最左結(jié)點(diǎn)否則，右子樹的最左結(jié)點(diǎn)為后繼為后繼 */ p=p-Rchild ; while (p-Ltag=0 ) p=p-Lchild; /else /while/if 在中序線索二叉樹中找結(jié)點(diǎn)后繼的方法：在中序線索二叉樹中找結(jié)點(diǎn)后繼的方法：（1）若）若Rtag=1, 則則

52、Rchild域直接指向其后繼域直接指向其后繼（2）若）若Rtag=0, 則結(jié)點(diǎn)的后繼應(yīng)是其右子樹則結(jié)點(diǎn)的后繼應(yīng)是其右子樹的左鏈尾（的左鏈尾（Ltag=1)的結(jié)點(diǎn)的結(jié)點(diǎn)拓展思考：拓展思考：在中序線索二叉樹中找結(jié)點(diǎn)前驅(qū)的方法：在中序線索二叉樹中找結(jié)點(diǎn)前驅(qū)的方法：（1）若）若Ltag=1, 則則Lchild域直接指向其前驅(qū)域直接指向其前驅(qū)（2）若）若Ltag=0, 則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子樹的右鏈尾（樹的右鏈尾（Rtag=1)的結(jié)點(diǎn)的結(jié)點(diǎn)中序線索樹的邏輯形式中序線索樹的邏輯形式AFHIEGBDCNILNIL中序線索二叉樹及其存儲(chǔ)結(jié)構(gòu)中序線索二叉樹及其存儲(chǔ)結(jié)構(gòu)(c) 中序線索二叉鏈

53、表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹 0 1頭結(jié)點(diǎn)：Ltag=0, Lchild指向根結(jié)點(diǎn)Rtag=1, Rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的Lchild域和最后一個(gè)結(jié)點(diǎn)的Rchild域都指向頭結(jié)點(diǎn) A B D C ET中序序列：BCAED中序線索二叉樹00001111116.6 二叉樹的應(yīng)用哈夫曼樹哈夫曼樹(Huffman)帶權(quán)路徑長(zhǎng)度最短的樹定義路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)

54、之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑長(zhǎng)度：路徑上的分支數(shù)樹的路徑長(zhǎng)度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的帶權(quán)路徑長(zhǎng)度：樹中所有帶權(quán)結(jié)點(diǎn)的路徑長(zhǎng)度之和結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中：記作：kknkkklwlwwpl1lHuffman樹設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹叫例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1

55、vHuffman樹應(yīng)用v最佳判定樹等級(jí)分?jǐn)?shù)段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a2n-1 */ typedef structint Weight ; /* 權(quán)值域權(quán)值域 */int Parent , Lchild , Rchild ; HTNode ;(2) Huffman樹的生成樹的生成算法實(shí)現(xiàn)算法實(shí)現(xiàn)void Create_Huffman(int n, HTNode HT , int m)

56、 /* 創(chuàng)建一棵葉子結(jié)點(diǎn)數(shù)為創(chuàng)建一棵葉子結(jié)點(diǎn)數(shù)為n的的Huffman樹樹 */ int w ; int k , j ;for (k=1 ; km ; k+) if (k=n) printf(“n Please Input Weight : w=?”); scanf(“%d”, &w) ;HTk.weight=w ; /* 輸入時(shí)，所有葉子結(jié)點(diǎn)都有權(quán)值輸入時(shí)，所有葉子結(jié)點(diǎn)都有權(quán)值 */else HTk.weight=0; /* 非葉子結(jié)點(diǎn)沒有權(quán)非葉子結(jié)點(diǎn)沒有權(quán)值值 */HTk.Parent=HTk.Lchild=HTk.Rchild=0 ; /* 初始化向量初始化向量HT */ for

57、(k=n+1; km ; k+) int w1=32767 , w2=w1 ; /* w1 , w2分別保存權(quán)值最小的兩個(gè)權(quán)值分別保存權(quán)值最小的兩個(gè)權(quán)值 */ int p1=0 , p2=0 ; /* p1 , p2保存兩個(gè)最小權(quán)值的下標(biāo)保存兩個(gè)最小權(quán)值的下標(biāo) */for (j=1 ; j=k-1 ; j+) if (HTk.Parent=0) /* 尚未合并尚未合并 */ if (HTj.Weightw1) w2=w1 ; p2=p1 ; w1=HTj.Weight ; p1=j ; else if (HTj.Weightw2) w2=HTj.Weight ; p2=j ; /* 找到權(quán)值最小的兩個(gè)值及其下標(biāo)找到權(quán)值最小的兩個(gè)值及其下標(biāo) */HTk.Lchild=p1 ; HTk.Rchild=p2 ;HTk.weight=w1+w2 ;HTp1.Parent=k ; HTp2.Parent=k ; 說(shuō)明：生成說(shuō)明：生成Huffman樹后，樹的根結(jié)點(diǎn)的下標(biāo)是樹后，樹的根結(jié)點(diǎn)的下標(biāo)是2n-1 ，即，即m-1 。(3) Huffman編碼算法編碼算法 根據(jù)出現(xiàn)頻度根據(jù)出現(xiàn)頻度(權(quán)值權(quán)值)Weight，對(duì)葉子結(jié)點(diǎn)的，對(duì)葉子結(jié)點(diǎn)的Huffman編碼有編碼有