1、第6章 樹(shù) 本章中主要介紹下列內(nèi)容：l 樹(shù)的邏輯定義和存儲(chǔ)結(jié)構(gòu)l 二叉樹(shù)的邏輯定義、存儲(chǔ)結(jié)構(gòu)l 二叉樹(shù)的基本操作算法l 樹(shù)和二叉樹(shù)的轉(zhuǎn)換l 哈夫曼樹(shù)及其應(yīng)用n6.1 樹(shù)的概念與定義n6.2 二叉樹(shù)n6.3 二叉樹(shù)的遍歷n6.5 樹(shù)與森林n6.6 哈夫曼樹(shù)及其應(yīng)用章節(jié)安排：家譜結(jié)構(gòu)：張?jiān)磸堅(jiān)磸埫鲝埩翉埦S張麗張平張群張林張華張晶張壘6.1 6.1 樹(shù)的概念樹(shù)的概念 6.1.1 6.1.1 樹(shù)的定義樹(shù)的定義 定義： 樹(shù)是一種常用的非線性結(jié)構(gòu)。我們可以這樣定義：樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限集合。若n=0，則稱為空樹(shù)；1）否則，有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根，2）當(dāng)n1時(shí)，其余結(jié)點(diǎn)被分成m（m0）個(gè)互不相

2、交的子集T1，T2，.，Tm，每個(gè)子集又是一棵樹(shù)。由此可以看出，樹(shù)的定義是遞歸。圖 6-1 E F G H I J B C DAA(a)(b)(c)樹(shù)邏輯結(jié)構(gòu)：n樹(shù)中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)后繼（即孩子）結(jié)點(diǎn)，但至多只能有一個(gè)前驅(qū)（即雙親）結(jié)點(diǎn)。n只有根結(jié)點(diǎn)無(wú)前驅(qū)；n只有葉結(jié)點(diǎn)無(wú)后繼；樹(shù)的多種多種表示：A B E F I JCD G HIJECGHDBA( A(B(E, F(I, J), C, D(G, H) )F結(jié)點(diǎn) 數(shù)據(jù)元素的內(nèi)容及其指向其子樹(shù)根的分支統(tǒng)稱為結(jié)點(diǎn)。結(jié)點(diǎn)的度 結(jié)點(diǎn)的分支數(shù),也即子樹(shù)的個(gè)數(shù)。樹(shù)的度 樹(shù)中所有結(jié)點(diǎn)度的最大值。終端結(jié)點(diǎn)（葉子） 度為0的結(jié)點(diǎn)。非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)）

3、 度不為0的結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn) 除根結(jié)點(diǎn)外的分支結(jié)點(diǎn)樹(shù)的基本概念與術(shù)語(yǔ)（一）在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系又可以用家族關(guān)系描述，在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系又可以用家族關(guān)系描述，定義如下：定義如下： 孩子、雙親 結(jié)點(diǎn)子樹(shù)的根稱為這個(gè)結(jié)點(diǎn)的孩子，而這個(gè)結(jié)點(diǎn)又被稱為孩子的雙親。 兄弟 同一個(gè)雙親的孩子之間互為兄弟。 堂兄弟 雙親在同一層的結(jié)點(diǎn)互為堂兄弟。 路徑及其長(zhǎng)度 若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列K1，K2Kj，使得Ki是Ki+1(1=i0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹(shù)的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)作為左子集，另一個(gè)作為右子集，每個(gè)子集又是一個(gè)二叉樹(shù)。G HD E FB CA二叉樹(shù)的5種形態(tài)：圖圖 5

4、-7(a)(b)(c)(d)(e)6.2.2 6.2.2 二叉樹(shù)的4個(gè)重要性質(zhì) 【性質(zhì)1】 在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i1）。 二叉樹(shù)的第1層只有一個(gè)根結(jié)點(diǎn)，所以，i=1時(shí)，2i-1=21-1 =20=1成立。 假設(shè)對(duì)所有的j，1ji成立，即第j層上最多有2j-1個(gè)結(jié)點(diǎn)成立。若j=i-1，則第j層上最多有2j-1=2i-2個(gè)結(jié)點(diǎn)。只要證明j=i時(shí)，命題成立。由于在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的度最大為2，所以可以推導(dǎo)出第i層最多的結(jié)點(diǎn)個(gè)數(shù)就是第i-1層最多結(jié)點(diǎn)個(gè)數(shù)的2倍，即2i-2*2 =2i-1。【性質(zhì)2】 深度為K的二叉樹(shù)最多有2K-1個(gè)結(jié)點(diǎn)（K1）。qqaaSnn1*1 由性質(zhì)1可以

5、得出，1至K層各層最多的結(jié)點(diǎn)個(gè)數(shù)分別為：20,21,22,23,.,2K-1。這是一個(gè)以2為比值的等比數(shù)列，前n項(xiàng)之和的計(jì)算公式為：12212*1202KK證明：假設(shè)度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，結(jié)點(diǎn)總數(shù)為n，B為二叉樹(shù)中的分支數(shù)。 因?yàn)樵诙鏄?shù)中，所有結(jié)點(diǎn)的度均小于或等于2，所以結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2 （1） 再查看一下分支數(shù)。在二叉樹(shù)中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有一個(gè)從上向下的分支指向，所以，總的結(jié)點(diǎn)個(gè)數(shù)n與分支數(shù)B之間的關(guān)系為： n=B+1。【性質(zhì)3】 對(duì)于任意一棵二叉樹(shù)，如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。 又因?yàn)樵诙鏄?shù)中，度為1的結(jié)點(diǎn)產(chǎn)生1個(gè)分

6、支，度為2的結(jié)點(diǎn)產(chǎn)生2個(gè)分支，所以分支數(shù)B可以表示為：B=n1+2n2。 將此式代入上式，得：n=n1+2n2+1 （2） 用（1）式減去（2）式，并經(jīng)過(guò)調(diào)整后得到：n0=n2+1。 滿二叉樹(shù)： 如果一個(gè)深度為K的二叉樹(shù)擁有2K-1個(gè)結(jié)點(diǎn)，則將它稱為滿二叉樹(shù)。滿二叉樹(shù)滿二叉樹(shù) 8 9 10 11 12 13 14 154 5 6 72 31 完全二叉樹(shù)完全二叉樹(shù)：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若將它與一棵同深度的滿二叉樹(shù)中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹(shù)中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹(shù)中編號(hào)為1n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹(shù)為完全二叉樹(shù)?；蛘呷粢活w二叉樹(shù)至多

7、只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上。完全二叉樹(shù)完全二叉樹(shù) 8 9 10 11 12 13 144 5 6 72 31 證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為K，則根據(jù)性質(zhì)2可以得出： 2K-1-1 n 2K-1 將不等式兩端加1得到： 2K-1 n 2K 將不等式中的三項(xiàng)同取以2為底的對(duì)數(shù)，并經(jīng)過(guò)化簡(jiǎn)后得到： K-1 log2n K 由此可以得到：log2n =K-1。整理后得到：K= log2n+1?！拘再|(zhì)4】 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n+1。其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)。6.2.3 二叉樹(shù)

8、的抽象數(shù)據(jù)類型二叉樹(shù)的抽象數(shù)據(jù)類型ADT BinaryTree 數(shù)據(jù)對(duì)象D: 數(shù)據(jù)關(guān)系R： 基本操作P： P121 - P122 二叉樹(shù)也可以采用兩種存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。6.3.1 順序存儲(chǔ)結(jié)構(gòu) 把二叉樹(shù)所有的結(jié)點(diǎn)，按照一定的次序順序，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。 問(wèn)題：如何體現(xiàn)結(jié)點(diǎn)間的邏輯關(guān)系？6.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)完全二叉樹(shù)結(jié)點(diǎn)間邏輯關(guān)系（1）84 5 6 72 31 N個(gè)結(jié)點(diǎn) 自上到下，從左往右編號(hào)完全二叉樹(shù)結(jié)點(diǎn)間邏輯關(guān)系（2） 編號(hào)為i的結(jié)點(diǎn)是Ki（1= i 1, Ki的雙親就是 i/2 ；i=1, Ki是根，無(wú)雙親。n若2i=N, Ki的左孩子是編

9、號(hào)為2i；否則無(wú)左孩子，即Ki是葉結(jié)點(diǎn)。n若2i+1data = ch; s-lchild = NULL; s-rchild = NULL; rear +; Qrear = s; if ( rear = 1 ) root = s; else if (s & Qfront) if (rear % 2 = 0) Qfront-lchild = s; else Qfront-rchild = s; if (rear % 2 = 1) front +; Ch = getchar(); Return root; 二叉樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在對(duì)它進(jìn)行操作時(shí)，總是需要逐一對(duì)每個(gè)數(shù)據(jù)元素實(shí)施操作，

10、這樣就存在一個(gè)操作順序問(wèn)題，由此提出了二叉樹(shù)的遍歷操作。所謂遍歷二叉樹(shù)就是按某種順序訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)一次且僅一次的過(guò)程。這里的訪問(wèn)可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。 二叉樹(shù)的遍歷方式分為兩大類：二叉樹(shù)的遍歷方式分為兩大類：一類按根、左子樹(shù)和右子樹(shù)三個(gè)部分進(jìn)行訪問(wèn)；另一類按層次訪問(wèn)。下面我們將分別進(jìn)行討論。6.4 遍歷二叉樹(shù)遍歷二叉樹(shù) 1. 按根、左子樹(shù)和右子樹(shù)三部分進(jìn)行遍歷 遍歷二叉樹(shù)的順序存在下面6種可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三種順序在左右子樹(shù)之間

11、均是先右子樹(shù)后左子樹(shù)，這與人們先左后右的習(xí)慣不同，因此，往往不予采用。余下的三種順序TLR、LTR和LRT根據(jù)根訪問(wèn)的位置不同分別被稱為先序遍歷、中序遍歷和后序遍歷。1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是：若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； 先序遍歷左子樹(shù)先序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 先序遍歷右子樹(shù)先序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)。6.3.1 先序遍歷二叉樹(shù)先序遍歷二叉樹(shù)void PreorderTraverse(BTNode *T) if (T!=NULL) visit(T-data) ;

12、/* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 說(shuō)明：說(shuō)明：visit()函數(shù)是訪問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問(wèn)題函數(shù)是訪問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問(wèn)題而定。樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量而定。樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T T來(lái)指向。來(lái)指向。先序遍歷的遞歸算法先序遍歷的遞歸算法2 非遞歸算法非遞歸算法n設(shè)設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：n若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T； 訪問(wèn)訪問(wèn)p所指

13、向的結(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)，直到棧空為止。，直到?？諡橹埂?算法實(shí)現(xiàn)算法實(shí)現(xiàn)：#define MAX_NODE 50void PreorderTraverse( 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 ) ;

14、 q=p-Rchild ; if ( q!=NULL ) stack+top=q ; p=p-Lchild ; if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ;1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 中序遍歷左子樹(shù)中序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 訪問(wèn)根結(jié)點(diǎn)；訪問(wèn)根結(jié)點(diǎn)； 中序遍歷右子樹(shù)中序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)。6.3.2 中序遍歷二叉樹(shù)中序遍歷二叉樹(shù)void InorderTraverse(BTNode *T) if (T!=

15、NULL) InorderTraverse(T-Lchild) ;visit(T-data) ; /* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */InorderTraverse(T-Rchild) ; /*圖圖6-8(a) 的二叉樹(shù)，輸出的次序是：的二叉樹(shù)，輸出的次序是： cbegdfa */中序遍歷的遞歸算法中序遍歷的遞歸算法2 非遞歸算法非遞歸算法設(shè)設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：n若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T 若若p不為空，不為空，p進(jìn)棧，進(jìn)棧， p=p-Lchild ； p為空，退棧到為空，退棧到p，訪問(wèn)

16、，訪問(wèn)p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； p=p-Rchild ，轉(zhuǎn)，轉(zhuǎn)(1)；直到?？諡橹?。直到棧空為止。 算法實(shí)現(xiàn)算法實(shí)現(xiàn)：#define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *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 ; p=p-Lchild ; if (top=0) bool=0 ; else p=stacktop

17、; top- ; visit( p-data ) ; p=p-Rchild ; while (bool!=0) ; 1 遞歸算法遞歸算法算法的遞歸定義是：算法的遞歸定義是： 若二叉樹(shù)為空，則遍歷結(jié)束；否則若二叉樹(shù)為空，則遍歷結(jié)束；否則 后序遍歷左子樹(shù)后序遍歷左子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法)； 后序遍歷右子樹(shù)后序遍歷右子樹(shù)(遞歸調(diào)用本算法遞歸調(diào)用本算法) ； 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) 。6.3.3 后序遍歷二叉樹(shù)后序遍歷二叉樹(shù)后序遍歷的遞歸算法后序遍歷的遞歸算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T-

18、Lchild) ;PostorderTraverse(T-Rchild) ; visit(T-data) ; /* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */ / /* *圖圖6-8(a) 的二叉樹(shù)，輸出的次序是：的二叉樹(shù)，輸出的次序是： cgefdbacgefdba * */ / 遍歷二叉樹(shù)的算法中基本操作是訪問(wèn)結(jié)點(diǎn)，因此，無(wú)論是哪遍歷二叉樹(shù)的算法中基本操作是訪問(wèn)結(jié)點(diǎn)，因此，無(wú)論是哪種次序的遍歷，對(duì)有種次序的遍歷，對(duì)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為O(n) 。 如圖如圖6-9所示的二叉樹(shù)表示表達(dá)式：所示的二叉樹(shù)表示表達(dá)式：(a+b*(c-d)-e/f)按不同的次序遍歷此二

19、叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序按不同的次序遍歷此二叉樹(shù)，將訪問(wèn)的結(jié)點(diǎn)按先后次序排列起來(lái)的次序是：排列起來(lái)的次序是： 其先序序列為：其先序序列為： -+a*b-cd/ef 其中序序列為：其中序序列為： a+b*c-d-e/f 其后序序列為：其后序序列為： abcd-*+ef/-/fe-dcb*a+圖圖6-9 表達(dá)式表達(dá)式 (a+b*(c-d)-e/f)二叉樹(shù)二叉樹(shù)2 非遞歸算法非遞歸算法 在后序遍歷中，根結(jié)點(diǎn)是最后被訪問(wèn)的。因此，在后序遍歷中，根結(jié)點(diǎn)是最后被訪問(wèn)的。因此，在遍歷過(guò)程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不在遍歷過(guò)程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不能立即訪問(wèn)，而要先遍歷其左子樹(shù)，此時(shí)能立

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

21、志變量狀態(tài)標(biāo)志變量tag 。S1和和S2共用一個(gè)棧頂共用一個(gè)棧頂指針。指針。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：是指向根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T； 第一次經(jīng)過(guò)根結(jié)點(diǎn)第一次經(jīng)過(guò)根結(jié)點(diǎn)p，不訪問(wèn)：，不訪問(wèn)： p進(jìn)棧進(jìn)棧S1 ， tag 賦值賦值0，進(jìn)棧，進(jìn)棧S2，p=p-Lchild 。 若若p不為空，轉(zhuǎn)不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標(biāo)志值，否則，取狀態(tài)標(biāo)志值tag ： 若若tag=0：對(duì)棧：對(duì)棧S1，不訪問(wèn)，不出棧；修改，不訪問(wèn)，不出棧；修改S2棧頂棧頂元素值元素值(tag賦值賦值1) ，取，取S1棧頂元素的右子樹(shù)

22、，即棧頂元素的右子樹(shù)，即p=S1top-Rchild ，轉(zhuǎn)，轉(zhuǎn)(1)； 若若tag=1：S1退棧，訪問(wèn)該結(jié)點(diǎn)；退棧，訪問(wèn)該結(jié)點(diǎn)；直到?？諡橹?。直到?？諡橹?。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：#define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE , 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-Lchi

23、ld ; 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)使循環(huán)繼續(xù)進(jìn)行而不至于死循環(huán) */ while (bool!=0) ;6.3.4 層次遍歷二叉樹(shù)層次遍歷二叉樹(shù) 層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次序序“自上而下，從左至右自上而下，從左至右”訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。訪問(wèn)樹(shù)中的各結(jié)點(diǎn)。 為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化為

24、保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化時(shí)為空。時(shí)為空。 設(shè)設(shè)T是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算是指向根結(jié)點(diǎn)的指針變量，層次遍歷非遞歸算法是：法是：若二叉樹(shù)為空，則返回；否則，令若二叉樹(shù)為空，則返回；否則，令p=T，p入隊(duì)；入隊(duì)； 隊(duì)首元素出隊(duì)到隊(duì)首元素出隊(duì)到p； 訪問(wèn)訪問(wèn)p所指向的結(jié)點(diǎn)；所指向的結(jié)點(diǎn)； 將將p所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直所指向的結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止。到隊(duì)空為止。#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int f

25、ront=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ì) */ “遍歷遍歷”是二叉樹(shù)最重要的基本操作，是各種是二叉樹(shù)最重要的基本操作，是各種其它操作的基礎(chǔ)，二叉樹(shù)的許多其它操作都可以通其它操作的基礎(chǔ)，二叉樹(shù)的許多其它操作都可以通過(guò)遍歷來(lái)實(shí)現(xiàn)。如建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、求二叉過(guò)遍歷來(lái)實(shí)現(xiàn)。如建立二叉樹(shù)的

26、存儲(chǔ)結(jié)構(gòu)、求二叉樹(shù)的結(jié)點(diǎn)數(shù)、求二叉樹(shù)的深度等。樹(shù)的結(jié)點(diǎn)數(shù)、求二叉樹(shù)的深度等。6.3.5 二叉樹(shù)遍歷算法的應(yīng)用二叉樹(shù)遍歷算法的應(yīng)用按先序遍歷方式建立按先序遍歷方式建立 對(duì)一棵二叉樹(shù)進(jìn)行對(duì)一棵二叉樹(shù)進(jìn)行“擴(kuò)充擴(kuò)充”，就可以得到有該二叉，就可以得到有該二叉樹(shù)所擴(kuò)充的二叉樹(shù)。有兩棵二叉樹(shù)樹(shù)所擴(kuò)充的二叉樹(shù)。有兩棵二叉樹(shù)T1及其擴(kuò)充的二叉樹(shù)及其擴(kuò)充的二叉樹(shù)T2如圖如圖6-10所示。所示。圖圖6-10 二叉樹(shù)二叉樹(shù)T1及其擴(kuò)充及其擴(kuò)充二叉樹(shù)二叉樹(shù)T2ABCDEFG(a) 二叉樹(shù)二叉樹(shù)T1(b) T1的擴(kuò)充的擴(kuò)充二叉樹(shù)二叉樹(shù)T2ABCDEFG? 二叉樹(shù)的擴(kuò)充方法是：在二叉樹(shù)中結(jié)點(diǎn)的每一個(gè)空二叉樹(shù)的擴(kuò)充方法是：

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

28、LL；u 若是若是(正常正常)結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針?lè)峙湟粋€(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)值：動(dòng)態(tài)地為根指針?lè)峙湟粋€(gè)結(jié)點(diǎn)，將該值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹(shù)和右子樹(shù)。值賦給根結(jié)點(diǎn)，然后遞歸地創(chuàng)建根的左子樹(shù)和右子樹(shù)。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：#define NULLKY ?#define MAX_NODE 50typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;BTNode *Preorder_Create_BTree(BTNode *T) /* 建立鏈?zhǔn)蕉鏄?shù)，返回指向根結(jié)點(diǎn)的指針變量建立鏈?zhǔn)蕉鏄?shù)，返回指向根結(jié)

29、點(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ù)時(shí)，輸入的字所示的二叉樹(shù)時(shí)，輸入的字符序列應(yīng)當(dāng)是：符序列應(yīng)當(dāng)是：ABD?E?G?CF? 遍歷二叉樹(shù)是按一定的規(guī)則將樹(shù)中的結(jié)點(diǎn)排列成一

30、個(gè)線性序列，即是對(duì)非線性結(jié)構(gòu)的線性化操作。如何找到遍歷過(guò)程中動(dòng)態(tài)得到的每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼(第一個(gè)和最后一個(gè)除外)? 如何保存這些信息? 設(shè)一棵二叉樹(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ū)和直接后繼信息。6.3.6 6.3.6 線索樹(shù)線索樹(shù) （1）若結(jié)點(diǎn)有左孩子，則）若結(jié)點(diǎn)有左孩子，則Lchild指向其左孩子，指向其左孩子，否則，指向其直接前驅(qū)；否則，指向其直接前驅(qū)； （2） 若結(jié)點(diǎn)有右孩子若結(jié)點(diǎn)有右孩子，則則Rchild指向其右孩指向其右孩子子

31、，否則，指向其直接后繼；，否則，指向其直接后繼； 為避免混淆為避免混淆, ,對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)對(duì)結(jié)點(diǎn)結(jié)構(gòu)加以改進(jìn)，增加兩個(gè)標(biāo)志域。志域。 對(duì)結(jié)點(diǎn)的指針域做如下規(guī)定：對(duì)結(jié)點(diǎn)的指針域做如下規(guī)定： 用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，用這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做叫做線索鏈表線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索線索；按照某種次序遍歷，加上線索的二叉樹(shù)稱；按照某種次序遍歷，加上線索的二叉樹(shù)稱之為之為線索二叉樹(shù)線索二叉樹(shù)。Lchild Ltag data Rchild Rtag圖圖6-10 線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)0：Lchi

32、ld域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子1 1：Lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū)Ltag=0 0：Rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 1：Rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼Rtag=AFHIEGBDC(a) 二叉樹(shù)二叉樹(shù) (b) 先序線索樹(shù)的邏輯形式先序線索樹(shù)的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹(shù)的邏輯形式后序線索樹(shù)的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBGEHIFCA(c) 中序線索樹(shù)的邏輯形式中序線索樹(shù)的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNI

33、L 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) 中序線索樹(shù)的鏈表結(jié)構(gòu)中序線索樹(shù)的鏈表結(jié)構(gòu)說(shuō)明說(shuō)明：畫線索二叉樹(shù)時(shí)，畫線索二叉樹(shù)時(shí)，實(shí)線實(shí)線表示指針，指向其左表示指針，指向其左、右孩子；右孩子；虛線虛線表示線索，指向其直接前驅(qū)或直接后繼。表示線索，指向其直接前驅(qū)或直接后繼。 在線索樹(shù)上進(jìn)行遍歷，只要先找到序列中的第一個(gè)在線索樹(shù)上進(jìn)行遍歷，只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。為空為止。6.3.3 6.3.3 線索化二叉樹(shù)線索化二叉樹(shù)

34、二叉樹(shù)的線索化二叉樹(shù)的線索化指的是依照某種遍歷次序使二叉指的是依照某種遍歷次序使二叉樹(shù)成為線索二叉樹(shù)的過(guò)程。樹(shù)成為線索二叉樹(shù)的過(guò)程。 線索化的過(guò)程就是線索化的過(guò)程就是在遍歷過(guò)程中修改空指針使其指在遍歷過(guò)程中修改空指針使其指向直接前驅(qū)或直接后繼向直接前驅(qū)或直接后繼的過(guò)程。的過(guò)程。 仿照線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)的線索鏈表上也仿照線性表的存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)的線索鏈表上也添加一個(gè)頭結(jié)點(diǎn)添加一個(gè)頭結(jié)點(diǎn)head，頭結(jié)點(diǎn)的指針域的安排是：，頭結(jié)點(diǎn)的指針域的安排是： Lchild域：指向二叉樹(shù)的根結(jié)點(diǎn)；域：指向二叉樹(shù)的根結(jié)點(diǎn)； Rchild域：指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)；域：指向中序遍歷時(shí)的最后一個(gè)結(jié)點(diǎn)；

35、 二叉樹(shù)中序序列中的二叉樹(shù)中序序列中的第一個(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。(a) 二叉樹(shù)二叉樹(shù)(b) 中序線索樹(shù)的邏輯形式中序線索樹(shù)的邏輯形式AFHIEGBDCNILNILAFHIEGBDC圖圖6-12 中序線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)中序線索二叉樹(shù)及其存儲(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結(jié)點(diǎn)類型定義結(jié)點(diǎn)類型定義typedef enmuLink , Thread Pointer

36、Tag ;/* Link=0表示指針，表示指針， Thread=1表示線索表示線索 */typedef struct BiThrNode ElemType data;struct BiTreeNode *Lchild , *Rchild ; PointerTag Ltag , Rtag ;BiThrNode, BiThrTree;線索二叉樹(shù)中序遍歷（線索二叉樹(shù)中序遍歷（P134），中序線索化（），中序線索化（P134）線索二叉樹(shù)結(jié)構(gòu)定義6.4 6.4 樹(shù)與森林樹(shù)與森林 本節(jié)將討論樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)及本節(jié)將討論樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)及森林與二叉樹(shù)之間的相互轉(zhuǎn)換、樹(shù)的森林與二叉樹(shù)之間的相互轉(zhuǎn)換、樹(shù)的遍歷等

37、。遍歷等。6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)(一一) 雙親表示法雙親表示法(順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)) 用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器指示器(整數(shù)域整數(shù)域) ，用以指示雙親結(jié)用以指示雙親結(jié)點(diǎn)的位置點(diǎn)的位置(下標(biāo)值下標(biāo)值) 。數(shù)組元素及數(shù)組的類型定義如下。數(shù)組元素及數(shù)組的類型定義如下： #define MAX_SIZE 100 typedef struct PTNode ElemType data ; int parent ; PTNode ;typedef struct PTNode NodesMA

38、X_SIZE ;int root; /* 根結(jié)點(diǎn)位置根結(jié)點(diǎn)位置 */int num ; /* 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) */ Ptree ; 圖圖6-13所示是一棵樹(shù)及其雙親所示是一棵樹(shù)及其雙親表示的存儲(chǔ)結(jié)構(gòu)表示的存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)結(jié)構(gòu)利這種存儲(chǔ)結(jié)構(gòu)利用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)?？梢苑奖愕刂苯诱业娇梢苑奖愕刂苯诱业饺我唤Y(jié)點(diǎn)的父任一結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)，但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃但求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組描整個(gè)數(shù)組。FGHIRABCDE圖圖6-13 樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)R -10A 01B 02C 03D 14E 15F 36G 67H 68I 69 (二二)

39、 孩子鏈表表示法孩子鏈表表示法 樹(shù)中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其樹(shù)中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其一棵子樹(shù)的根結(jié)點(diǎn)一棵子樹(shù)的根結(jié)點(diǎn)。有。有兩種結(jié)點(diǎn)結(jié)構(gòu)兩種結(jié)點(diǎn)結(jié)構(gòu)。 定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu) 指針域的數(shù)目就是樹(shù)的度指針域的數(shù)目就是樹(shù)的度。 其特點(diǎn)是其特點(diǎn)是：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯。結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)如圖結(jié)構(gòu)如圖(a) 所示所示。在一棵有在一棵有n個(gè)結(jié)點(diǎn)，度為個(gè)結(jié)點(diǎn)，度為k的樹(shù)中必有的樹(shù)中必有n(k-1)+1空指針域空指針域。 不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu) 樹(shù)中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度，如圖樹(shù)中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)

40、的度，如圖(b) 所示。沒(méi)有多余的指針域，但操作不便。所示。沒(méi)有多余的指針域，但操作不便。圖圖 孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)孩子表示法的結(jié)點(diǎn)結(jié)構(gòu)data child1 child2 childn(a) 定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)(b) 不不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)data k child1 child2 childk復(fù)合鏈表結(jié)構(gòu)復(fù)合鏈表結(jié)構(gòu) 對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用帶頭結(jié)點(diǎn)的對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用帶頭結(jié)點(diǎn)的單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖所示單鏈表表示，表結(jié)點(diǎn)和頭結(jié)點(diǎn)的結(jié)構(gòu)如圖所示。 n個(gè)結(jié)點(diǎn)的樹(shù)有個(gè)結(jié)點(diǎn)的樹(shù)有n個(gè)個(gè)(孩子孩子)單鏈表單鏈表(葉子結(jié)點(diǎn)的孩子鏈葉子結(jié)點(diǎn)的孩子鏈表為空表

41、為空)，而，而n個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)結(jié)構(gòu)表示結(jié)構(gòu)表示。data firstchild(a) 頭結(jié)點(diǎn)頭結(jié)點(diǎn)childno next(b) 表結(jié)點(diǎn)表結(jié)點(diǎn)圖圖 孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)孩子鏈表結(jié)點(diǎn)結(jié)構(gòu)nodes789 35 012 6 0123456789MAX_NODE-1rootnumA B C D E F G H I R 49圖圖6-14 圖圖6-13的樹(shù)的樹(shù)T的孩子鏈表存儲(chǔ)結(jié)構(gòu)的孩子鏈表存儲(chǔ)結(jié)構(gòu) （三）（三）孩子兄弟表示法孩子兄弟表示法(二叉樹(shù)表示法二叉樹(shù)表示法) 兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下

42、一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：typedef struct CSnode ElemType data ;struct CSnode *firstchild, *nextsibing ;CSNode; 圖圖6-15 樹(shù)及孩子兄弟存儲(chǔ)結(jié)構(gòu)樹(shù)及孩子兄弟存儲(chǔ)結(jié)構(gòu)(b) 樹(shù)樹(shù) FGRABCDE(c) 孩子兄弟存儲(chǔ)結(jié)構(gòu)孩子兄弟存儲(chǔ)結(jié)構(gòu) R A D C G B F E 孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchild data nextsibing(a) 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)6.4.2 森林與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換 由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，由于二叉

43、樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。可以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。 從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而已。同的，只是對(duì)指針的邏輯解釋不同而已。 從樹(shù)的二叉鏈表表示的定義可知，任何一棵和從樹(shù)的二叉鏈表表示的定義可知，任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。 圖圖6-16直觀地展示了樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。直觀地展示了樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。圖圖

44、6-16 樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系二叉樹(shù)二叉樹(shù) CERADB R A D C B E 樹(shù)樹(shù) RABCDE對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系 R A D C B E C B E R A D 存儲(chǔ)存儲(chǔ)解釋解釋存儲(chǔ)存儲(chǔ)解釋解釋 （一）（一）樹(shù)轉(zhuǎn)換成二叉樹(shù)樹(shù)轉(zhuǎn)換成二叉樹(shù) 對(duì)于一般的樹(shù)，可以方便地轉(zhuǎn)換成一棵唯一的二叉樹(shù)與對(duì)于一般的樹(shù)，可以方便地轉(zhuǎn)換成一棵唯一的二叉樹(shù)與之對(duì)應(yīng)。將樹(shù)轉(zhuǎn)換成二叉樹(shù)在之對(duì)應(yīng)。將樹(shù)轉(zhuǎn)換成二叉樹(shù)在“孩子兄弟表示法孩子兄弟表示法”中已給出，中已給出，其詳細(xì)步驟是：其詳細(xì)步驟是： 加虛線加虛線。在樹(shù)的每層按從。在樹(shù)的每層按從“左至右左至右”的順序在兄弟結(jié)的順序在兄弟結(jié)點(diǎn)之間加虛線相連。點(diǎn)

45、之間加虛線相連。 去連線去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線都去掉。它子結(jié)點(diǎn)的連線都去掉。 旋轉(zhuǎn)旋轉(zhuǎn)。將樹(shù)順時(shí)針旋轉(zhuǎn)。將樹(shù)順時(shí)針旋轉(zhuǎn)450，原有的實(shí)線左斜。，原有的實(shí)線左斜。 整型整型。將旋轉(zhuǎn)后樹(shù)中的所有虛線改為實(shí)線，并向右斜。將旋轉(zhuǎn)后樹(shù)中的所有虛線改為實(shí)線，并向右斜。 這樣轉(zhuǎn)換后的二叉樹(shù)的特點(diǎn)是這樣轉(zhuǎn)換后的二叉樹(shù)的特點(diǎn)是： 二叉樹(shù)的二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)根結(jié)點(diǎn)沒(méi)有右子樹(shù)，只有左子樹(shù)；，只有左子樹(shù)； 左子結(jié)點(diǎn)仍然是原來(lái)樹(shù)中相應(yīng)結(jié)點(diǎn)的左子結(jié)左子結(jié)點(diǎn)仍然是原來(lái)樹(shù)中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)均是原來(lái)樹(shù)中點(diǎn)，而所有沿

46、右鏈往下的右子結(jié)點(diǎn)均是原來(lái)樹(shù)中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。圖圖6-17 樹(shù)向二叉樹(shù)的轉(zhuǎn)換過(guò)程樹(shù)向二叉樹(shù)的轉(zhuǎn)換過(guò)程(a) 一般的樹(shù)一般的樹(shù) FGRABCDEFGRABCDE(b) 加虛線加虛線，去連線后去連線后 (C) 轉(zhuǎn)換后的二叉樹(shù)轉(zhuǎn)換后的二叉樹(shù)FGRACDBE （二）（二）二叉樹(shù)轉(zhuǎn)換成樹(shù)二叉樹(shù)轉(zhuǎn)換成樹(shù) 對(duì)于一棵轉(zhuǎn)換后的二叉樹(shù)，如何還原成原來(lái)的樹(shù)對(duì)于一棵轉(zhuǎn)換后的二叉樹(shù)，如何還原成原來(lái)的樹(shù)? 加虛線加虛線。若某結(jié)點(diǎn)。若某結(jié)點(diǎn)i是其父結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)，是其父結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)則將該結(jié)點(diǎn)i的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜索所有的右的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜索所有的右子結(jié)點(diǎn)

47、，將所有這些右子結(jié)點(diǎn)與子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與i結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相連，相連，如圖如圖6-20(a)所示所示。 去連線去連線。去掉二叉樹(shù)中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之。去掉二叉樹(shù)中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之間的連線，間的連線，如圖如圖6-20(b)所示所示。 規(guī)整化規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線，變成實(shí)線，如圖如圖6-20(c)所示。所示。圖圖6-20 二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程(C) 還原后的樹(shù)還原后的樹(shù)FGRABCDE(b) 去連線后去連線后 (a) 加虛線后加虛線后 FGRACDBECFGR

48、ADBE二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程（三）（三）森林轉(zhuǎn)換成二叉樹(shù)森林轉(zhuǎn)換成二叉樹(shù) 當(dāng)一般的樹(shù)轉(zhuǎn)換成二叉樹(shù)后，二叉樹(shù)的右子樹(shù)必當(dāng)一般的樹(shù)轉(zhuǎn)換成二叉樹(shù)后，二叉樹(shù)的右子樹(shù)必為空為空。若把森林中的第二棵樹(shù)。若把森林中的第二棵樹(shù)( (轉(zhuǎn)換成二叉樹(shù)后轉(zhuǎn)換成二叉樹(shù)后) )的根的根結(jié)點(diǎn)作為第一棵樹(shù)結(jié)點(diǎn)作為第一棵樹(shù)(二叉樹(shù)二叉樹(shù))的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則可的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則可導(dǎo)出森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換算法如下：導(dǎo)出森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換算法如下： 設(shè)設(shè)F=T1, T2, ,Tn是森林，則按以下規(guī)則可轉(zhuǎn)換是森林，則按以下規(guī)則可轉(zhuǎn)換成一棵二叉樹(shù)成一棵二叉樹(shù)B=(root，LB，RB) 若若n=0，則，

49、則B是空樹(shù)是空樹(shù)。 若若n0，則二叉樹(shù)，則二叉樹(shù)B的根是森林的根是森林T1的根的根root(T1)，B的左子樹(shù)的左子樹(shù)LB是是B(T11,T12, ,T1m) ，其中，其中T11,T12, ,T1m是是T1的子樹(shù)的子樹(shù)(轉(zhuǎn)換后轉(zhuǎn)換后)，而其右子樹(shù)，而其右子樹(shù)RB是從森是從森林林F=T2, T3, ,Tn轉(zhuǎn)換而成的二叉樹(shù)轉(zhuǎn)換而成的二叉樹(shù)。轉(zhuǎn)換步驟：轉(zhuǎn)換步驟： 將將F=T1, T2, ,Tn 中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)。 按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右子始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的

50、根結(jié)點(diǎn)的右子樹(shù)，依次類推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生樹(shù)，依次類推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹(shù)的根結(jié)點(diǎn)，成的二叉樹(shù)的根結(jié)點(diǎn)，如圖如圖6-21所示所示。ACBDGMLHK(a) 森林森林圖圖6-21 森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程(b) 森林中每棵樹(shù)森林中每棵樹(shù) 對(duì)應(yīng)的二叉樹(shù)對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM(c) 森林對(duì)應(yīng)的二叉樹(shù)森林對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM（四）（四）二叉樹(shù)轉(zhuǎn)換成森林二叉樹(shù)轉(zhuǎn)換成森林 若若B=(root，LB，RB)是一棵二叉樹(shù)，則可以將其是一棵二叉樹(shù)，則可以將其轉(zhuǎn)換成由若干棵樹(shù)構(gòu)成的森林：轉(zhuǎn)換成由若干棵樹(shù)構(gòu)成的森林：F=T1, T2, ,Tn

51、 。轉(zhuǎn)換算法：轉(zhuǎn)換算法： 若若B是空樹(shù)，則是空樹(shù)，則F為空為空。 若若B非空，則非空，則F中第一棵樹(shù)中第一棵樹(shù)T1的根的根root(T1)就是二就是二叉樹(shù)的根叉樹(shù)的根root， T1中根結(jié)點(diǎn)的子森林中根結(jié)點(diǎn)的子森林F1是由樹(shù)是由樹(shù)B的左的左子樹(shù)子樹(shù)LB轉(zhuǎn)換而成的森林轉(zhuǎn)換而成的森林；F中除中除T1外其余樹(shù)組成的外其余樹(shù)組成的的森林的森林F=T2, T3, ,Tn 是由是由B右子樹(shù)右子樹(shù)RB轉(zhuǎn)換得到的轉(zhuǎn)換得到的森林森林。 上述轉(zhuǎn)換規(guī)則是遞歸的上述轉(zhuǎn)換規(guī)則是遞歸的，可以寫出其遞歸算法。以可以寫出其遞歸算法。以下給出具體的還原步驟。下給出具體的還原步驟。 去連線。去連線。將二叉樹(shù)將二叉樹(shù)B的根結(jié)點(diǎn)與其

52、右子結(jié)點(diǎn)以及的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線全部去掉，沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線全部去掉，得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林F中的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)，中的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)，如圖如圖6-22(b)所示所示。 二叉樹(shù)的還原。二叉樹(shù)的還原。將各棵孤立的二叉樹(shù)按二叉樹(shù)將各棵孤立的二叉樹(shù)按二叉樹(shù)還原為樹(shù)的方法還原成一般的樹(shù)，還原為樹(shù)的方法還原成一般的樹(shù)，如圖如圖6- 22(c)所示所示。圖圖6-22 二叉樹(shù)還原成森林的過(guò)程二叉樹(shù)還原成森林的過(guò)程ACBDMGLHK(c) 還原成森林還原成森林(a) 二叉樹(shù)二叉樹(shù)ABC

53、DGLKHM(b) 去連線后去連線后ABCDMGLKH6.4.3 樹(shù)和森林的遍歷樹(shù)和森林的遍歷（一）（一） 樹(shù)的遍歷樹(shù)的遍歷 由樹(shù)結(jié)構(gòu)的定義可知，樹(shù)的遍歷有二種方法。由樹(shù)結(jié)構(gòu)的定義可知，樹(shù)的遍歷有二種方法。 先序遍歷先序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后：先訪問(wèn)根結(jié)點(diǎn)，然后依次先序遍歷依次先序遍歷完完每棵子樹(shù)。每棵子樹(shù)。如圖如圖6-23的樹(shù)，先序遍歷的次序是：的樹(shù)，先序遍歷的次序是：ABCDEFGIJHK 后序遍歷后序遍歷：先：先依次后序遍歷完依次后序遍歷完每棵子樹(shù)，然后每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。訪問(wèn)根結(jié)點(diǎn)。如圖如圖6-23的樹(shù)，后序遍歷的次序是：的樹(shù)，后序遍歷的次序是：CDBFIJGHEKA說(shuō)明說(shuō)明：

54、 樹(shù)的樹(shù)的先序遍歷先序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的樹(shù)后對(duì)二叉樹(shù)的先序遍歷先序遍歷相同。相同。 樹(shù)的樹(shù)的后序遍歷后序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的樹(shù)后對(duì)二叉樹(shù)的中序遍歷中序遍歷相同。相同。ABDCKGJIFHE圖圖6-23 樹(shù)樹(shù) （二）（二）森林的遍歷森林的遍歷 設(shè)設(shè)F=T1, T2, ,Tn是森林，對(duì)是森林，對(duì)F的遍歷有二種方法。的遍歷有二種方法。 先序遍歷先序遍歷：按：按先序遍歷先序遍歷樹(shù)的方式樹(shù)的方式依次依次遍歷遍歷F中的每棵樹(shù)。中的每棵樹(shù)。 中序遍歷中序遍歷：按：按后序遍歷后序遍歷樹(shù)的方式樹(shù)的方式依次依次遍歷遍歷F中的每棵

55、樹(shù)。中的每棵樹(shù)。6.5 哈夫曼樹(shù)及其應(yīng)用6.5.1 哈夫曼樹(shù)的定義n 在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑路徑。n 在路徑上的分支數(shù)目被稱為路徑長(zhǎng)度路徑長(zhǎng)度。G HD E FB CA權(quán)和帶權(quán)路徑長(zhǎng)度權(quán)和帶權(quán)路徑長(zhǎng)度nkkklwWPL1權(quán)：權(quán)：樹(shù)種結(jié)點(diǎn)賦予一個(gè)有意義的實(shí)數(shù)。結(jié)點(diǎn)的帶權(quán)長(zhǎng)度：結(jié)點(diǎn)的帶權(quán)長(zhǎng)度：該結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)種所有葉子結(jié)點(diǎn)的帶權(quán)長(zhǎng)度之和。 帶權(quán)的路徑長(zhǎng)度最小的二叉樹(shù)稱為哈夫曼二叉樹(shù)或最優(yōu)二叉樹(shù)。548圖5-27 葉子結(jié)點(diǎn)帶權(quán)值的二叉樹(shù) 下面我們討論一下權(quán)值、樹(shù)形與帶權(quán)的路徑長(zhǎng)度之間的關(guān)系。假設(shè)有

56、6個(gè)權(quán)值分別為3，6，9，10，7，11，以這6個(gè)權(quán)值作為葉子結(jié)點(diǎn)的權(quán)值可以構(gòu)造出下面三棵二叉樹(shù)。 3 6 7 910 11(a)1110976311103679(b)(c)這三棵二叉樹(shù)的帶權(quán)路徑長(zhǎng)度分別為：nWPL1=10*2+11*2+3*3+6*3+7*3+9*3=117nWPL2=3*1+6*2+7*3+9*4+10*5+11*5=177nWPL3=9*1+7*2+6*3+3*4+10*5+11*5=158一般情況下，最優(yōu)二叉樹(shù)，權(quán)值越大離根越近。一般情況下，最優(yōu)二叉樹(shù)，權(quán)值越大離根越近。 構(gòu)造哈夫曼樹(shù)的過(guò)程：構(gòu)造哈夫曼樹(shù)的過(guò)程： （1）將給定的n個(gè)權(quán)值w1,w2,.,wn作為n個(gè)根結(jié)

57、點(diǎn)的權(quán)值構(gòu)造一個(gè)具有n棵二叉樹(shù)的森林T1,T2, .,Tn，其中每棵二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； （2）在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)作為左右子樹(shù)構(gòu)造一棵新二叉樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)權(quán)值為這兩棵樹(shù)根的權(quán)值之和； （3）在森林中，將上面選擇的這兩棵根權(quán)值最小的二叉樹(shù)從森林中刪除，并將剛剛新構(gòu)造的二叉樹(shù)加入到森林中； （4）重復(fù)上面（2）和（3），直到森林中只有一棵二叉樹(shù)為止。這棵二叉樹(shù)就是哈夫曼樹(shù)。7 5 2 4舉例（舉例（P114 圖圖6.29） ：abcd構(gòu)造哈夫曼樹(shù)的過(guò)程構(gòu)造哈夫曼樹(shù)的過(guò)程(續(xù)續(xù))：哈夫曼樹(shù)算法實(shí)現(xiàn)(P114115)： # define n 7 # define m 2*n

58、-1 Typedef struct float weight; int lchirld, rchirld, parent; hufmtree Hufmtree tree m HUFFMAN (tree) Int i, j, p1, p2; Float small1, small2, f; For (i=0; im; i+) treei.parent = 0; treei.lchirld = 0; treei.rchirld = 0; treei.weight = 0 For(i=0; im; i+) scanf ( “%f”, &f ) ; treei.weight = f ; Cod

59、e(2) For(i=n; im; i+) p1=0; p2=0; Small1=small2=maxval; For(j=0; ji-1; j+) If (treej.parent=0) If (treej.weight small1) small2 = small1; small1=treej.weight; p2=p1; p1=j; else if ( treej.weight small2) small2 = treej.weight ; p2=j ; Treep1.parent = i+1; Treep2.parent = i+1; Treei.lchirld = p1+1; Tre

60、ei.rchirld = p2+1; Treei.weight = treep1.weight + treep2.weight ; 6.5.2 哈夫曼樹(shù)與編碼 在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （2）發(fā)送的二進(jìn)制編碼盡可能地短。下面我們介紹兩種編碼的方式。 1. 等長(zhǎng)編碼 這種編碼方式的特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度相同（編碼長(zhǎng)度就是每個(gè)編碼所含的二進(jìn)制位數(shù)）。假設(shè)字符集只含有4個(gè)字符A，B，C，D，用二進(jìn)制兩位表示的編碼分別為00，01，10，11。若現(xiàn)在有一段