哈夫曼樹(shù)及其應(yīng)用.ppt

《哈夫曼樹(shù)及其應(yīng)用.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼樹(shù)及其應(yīng)用.ppt（112頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第6章 樹(shù)和二叉樹(shù),6.1 樹(shù)的概念與定義 6.2 二叉樹(shù) 6.3 二叉樹(shù)的遍歷與線索化 6.4 樹(shù)、森林和二叉樹(shù)的關(guān)系 6.5 哈夫曼樹(shù)及其應(yīng)用 6.6 樹(shù)的計(jì)數(shù),整理發(fā)布,6.1 樹(shù)的概念與定義,樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹(shù)；當(dāng)n0時(shí)，該集合滿足如下條件：,(1) 其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。,(2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，，Tm，其中Ti又是一棵樹(shù)，稱為根root的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。,例如：,其中：A是根；其余

2、結(jié)點(diǎn)分成三個(gè)互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子樹(shù)，且本身也是一棵樹(shù),1. 樹(shù)型表示法 2. 嵌套集合表示法,3. 廣義表表示法 (A(B(D),C)),3. 凹入表示法,樹(shù)的表示法,,,,,,,,,,,樹(shù)的基本術(shù)語(yǔ),,,,,,,,,,,,,,,,,,1層,2層,4層,3層,height = 4,,,,,A,C,G,B,D,E,F,K,L,H,M,I,J,結(jié)點(diǎn) 結(jié)點(diǎn)的度 葉結(jié)點(diǎn) 分支結(jié)點(diǎn),子女 雙親 兄弟,祖先 子孫 結(jié)點(diǎn)層次,樹(shù)的深度 樹(shù)的度 森林,有關(guān)樹(shù)的一些術(shù)語(yǔ)：,結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的

3、分支信息。,結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)稱為此結(jié)點(diǎn)的度。,葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。,分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。,孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。如上圖的B、C、D是A的孩子。,雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。上圖中A是B、C、D的雙親。,兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。上圖中的結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。,祖先結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。如結(jié)點(diǎn)K的祖先結(jié)點(diǎn)是A、B、E。,子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼和間接后繼稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。如結(jié)點(diǎn)D的子孫是H、I、J、

4、M。,樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。,堂兄弟結(jié)點(diǎn)：其雙親在同一層的結(jié)點(diǎn)。如結(jié)點(diǎn)G與結(jié)點(diǎn)E、F、H、I、J互為堂兄弟。,結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類(lèi)推。,樹(shù)的高度（深度）：樹(shù)中所有結(jié)點(diǎn)的層次的最大值。,有序樹(shù)：在樹(shù)T中，如果各子樹(shù)Ti之間是有先后次序的，則稱為有序樹(shù)。,森林：m（m0）棵互不相交的樹(shù)的集合。將一棵非空樹(shù)的根結(jié)點(diǎn)刪去，樹(shù)就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹(shù)。,樹(shù)的抽象數(shù)據(jù)類(lèi)型定義：,數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性。,數(shù)據(jù)關(guān)系R：若D為空集，則為空樹(shù)。若D中僅含有一個(gè)數(shù)據(jù)元素，

5、則R為空集，否則R=H，H是如下的二元關(guān)系：,(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒(méi)有前驅(qū)。,(2) 除root以外，D中每個(gè)結(jié)點(diǎn)在關(guān)系H下都有且僅有一個(gè)前驅(qū)。,基本操作：,InitTree（Tree）： 將Tree初始化為一棵空樹(shù)。 (2) DestoryTree（Tree）： 銷(xiāo)毀樹(shù)Tree。 (3) CreateTree（Tree）： 創(chuàng)建樹(shù)Tree。 (4) TreeEmpty（Tree）： 若Tree為空，則返回TRUE，否則返回FALSE。 (5) Root（Tree）： 返回樹(shù)Tree的根。 (6) Parent（Tree，x）： 樹(shù)Tree存在，x是T

6、ree中的某個(gè)結(jié)點(diǎn)。若x為非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。,(7) FirstChild（Tree，x）： 樹(shù)Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非葉子結(jié)點(diǎn)，則返回它的第一個(gè)孩子結(jié)點(diǎn)，否則返回“空”。 (8) NextSibling（Tree，x）： 樹(shù)Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn)，則返回x后面的下一個(gè)兄弟結(jié)點(diǎn)，否則返回“空”。 (9) InsertChild（Tree，p，Child）： 樹(shù)Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，非空樹(shù)Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點(diǎn)的子樹(shù)。,基本操作:,基

7、本操作:,(10) DeleteChild（Tree，p，i）： 樹(shù)Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，1id，d為p所指向結(jié)點(diǎn)的度。刪除Tree中p所指向結(jié)點(diǎn)的第i棵子樹(shù)。 (11) TraverseTree（Tree，Visit（））： 樹(shù)Tree存在，Visit（）是對(duì)結(jié)點(diǎn)進(jìn)行訪問(wèn)的函數(shù)。按照某種次序?qū)?shù)Tree的每個(gè)結(jié)點(diǎn)調(diào)用Visit（）函數(shù)訪問(wèn)一次且最多一次。若Visit（）失敗，則操作失敗。,6.2 二叉數(shù),6.2.1 二叉樹(shù)的定義與基本操作,6.2.2 二叉樹(shù)的性質(zhì),6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),6.2.1 二叉樹(shù)的定義與基本操作,定義：我們把滿足以下兩個(gè)條件的樹(shù)型結(jié)構(gòu)叫做二

8、叉樹(shù)（Binary Tree）： （1）每個(gè)結(jié)點(diǎn)的度都不大于2； （2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。,下面給出二叉樹(shù)的五種基本形態(tài)：,二叉樹(shù)的基本操作：,Initiate（bt）：將bt初始化為空二叉樹(shù)。 (2) Create(bt)：創(chuàng)建一棵非空二叉樹(shù)bt。 (3) Destory（bt）： 銷(xiāo)毀二叉樹(shù)bt。 (4) Empty（bt）： 若bt為空，則返回TRUE，否則返回FALSE。 (5) Root(bt)： 求二叉樹(shù)bt的根結(jié)點(diǎn)。若bt為空二叉樹(shù)，則函數(shù)返回“空”。 (6) Parent（bt，x）：求雙親函數(shù)。求二叉樹(shù)bt中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是二叉樹(shù)的根結(jié)點(diǎn)或二叉樹(shù)

9、bt中無(wú)結(jié)點(diǎn)x，則返回“空”。,基本操作：,(7) LeftChild（bt，x）：求左孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。 (8) RightChild（bt，x）：求右孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。 (9) Traverse（bt）: 遍歷操作。按某個(gè)次序依次訪問(wèn)二叉樹(shù)中每個(gè)結(jié)點(diǎn)一次且僅一次。 (10) Clear（bt）：清除操作。將二叉樹(shù)bt置為空樹(shù)。,6.2.2 二叉樹(shù)的性質(zhì),性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。,當(dāng)i=1時(shí)，整個(gè)二叉樹(shù)只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。,證明：,假設(shè)i=k時(shí)結(jié)論成立，即第k層

10、上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。,現(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：,因?yàn)槎鏄?shù)中每個(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。,性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k1）。,證明：,由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為,故結(jié)論成立。,性質(zhì)3：對(duì)任意一棵二叉樹(shù)T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0= n2+1 。,證明：設(shè)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹(shù)中度為1的結(jié)點(diǎn)總數(shù)。因?yàn)槎鏄?shù)中所有結(jié)點(diǎn)的度小于等于2，所以有 n= n0+ n1+n2 設(shè)二叉樹(shù)中分支數(shù)目為B，因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)

11、點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有：n=B+1。 又因?yàn)槎鏄?shù)中的分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出，所以分支數(shù)目為：B=n1+2n2 整理上述兩式可得到：n=B+1=n1+2n2+1 將n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故結(jié)論成立。,兩種特殊的二叉樹(shù)：,定義1：滿二叉樹(shù)(Full Binary Tree) 深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。在滿二叉樹(shù)中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。,滿二叉樹(shù),定義2：完全二叉樹(shù)：,關(guān)系：滿二叉樹(shù)必為完全二叉樹(shù)，而完全二叉樹(shù)不一定是滿二叉樹(shù)。,若設(shè)二叉樹(shù)的高度為h，則共有h層。

12、除第 h 層外，其它各層 (0 h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。,非完全二叉樹(shù),性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為2n+1。,證明：設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為： 2k-1-1 k層滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為： 2k-1 顯然有： 2k-1 - 1 < n 2k- 1 2k- 1 n < 2k 取對(duì)數(shù)有：k -1 log2n < k 因?yàn)閗是整數(shù)，所以k -1 =log2n ， k= 2n+1 結(jié)論成立。,性質(zhì)5：對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上到下和從左到右的順序?qū)Χ鏄?shù)中的

13、所有結(jié)點(diǎn)從1開(kāi)始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有：,(1)若i = 1, 則 i 無(wú)雙親結(jié)點(diǎn) 若i 1, 則 i 的雙親結(jié)點(diǎn)為i /2 (2)若2*i n, 則 i 無(wú)左孩子 若2*in, 則 i 結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為2*i (3)若 2*i+1 n ,則i 無(wú)右孩子 若 2*i+1n, 則i的右孩子結(jié)點(diǎn)為2* i+1,用歸納法證明其中的(2)和(3)。,6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),二叉樹(shù)的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。,二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,完全二叉樹(shù) 一般二叉樹(shù) 的順序表示 的順序表示,二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),,,1 2 3 4 5

14、 6 7 8 910,,,,,,,,,,,,,,,,,,,,,,,,,,,9,,,1 2 3 4 0 5 6 7 8 0 0 910,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,,,6,5,,4,,7,,8,順序表示,9,,10,,對(duì)于一般的二叉樹(shù)，我們必須按照完全二叉樹(shù)的形式來(lái)存儲(chǔ)，就會(huì)造成空間的浪費(fèi)。單支樹(shù)就是一個(gè)極端情況。,單支樹(shù),鏈表表示,二叉鏈表,含兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu),,lChild data parent rChild,,,,,,,含三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu),三叉鏈表,二叉樹(shù)鏈表表示的示例,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,A,A,A,B,B,B,C,C,C,D,D,D,F,F,F,E,E,E,,root,,root,,root,二叉樹(shù) 二叉鏈表 三叉鏈表,,有時(shí)，為了找到父結(jié)點(diǎn)，可以增加一個(gè)Parent域，Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。該結(jié)點(diǎn)結(jié)構(gòu)如下：,typedef struct Node DataType data; strct Node * LChild; struct Node * RChild; BiTNode, *BiTree;,二叉樹(shù)的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)用C語(yǔ)言描述為 ：,結(jié)論：若一個(gè)二叉樹(shù)含有n個(gè)

16、結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n1個(gè)空的鏈域。,證明結(jié)論：,分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。,6.3 二叉樹(shù)的遍歷與線索化,二叉樹(shù)的遍歷：指按一定規(guī)律對(duì)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問(wèn)且僅訪問(wèn)一次。,二叉樹(shù)的基本結(jié)構(gòu)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成,如圖示,用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，那么對(duì)二叉樹(shù)的遍歷順序就可以有：,訪問(wèn)根，遍歷左子樹(shù)，遍歷右子樹(shù)(記做DLR)。 訪問(wèn)根，遍歷右子樹(shù)，遍歷左子樹(shù)(記做DRL)。 遍歷左子樹(shù)，訪問(wèn)根，遍歷右子樹(shù)(記做LDR)。 遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)根 (記做LRD)。

17、 遍歷右子樹(shù)，訪問(wèn)根，遍歷左子樹(shù) (記做RDL)。 遍歷右子樹(shù)，遍歷左子樹(shù)，訪問(wèn)根 (記做RLD)。,在以上六種遍歷方式中，如果我們規(guī)定按先左后右的順序，那么就只剩有 DLR 、LDR 和LRD三種。根據(jù)對(duì)根的訪問(wèn)先后順序不同，分別稱DLR為先序遍歷或先根遍歷；LDR為中序遍歷（對(duì)稱遍歷）；LRD為后序遍歷。,注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹(shù)中亦按上述規(guī)律進(jìn)行遍歷。,三種遍歷方法的遞歸定義：,先序遍歷（DLR）操作過(guò)程：,若二叉樹(shù)為空，則空操作，否則依次執(zhí)行如下操作： （1）訪問(wèn)根結(jié)點(diǎn)； （2）按先序遍歷左子樹(shù)； （3）按先序遍歷右子樹(shù)。,若二叉樹(shù)為空，則空操作，否則依次執(zhí)行

18、如下操作： （1）按中序遍歷左子樹(shù)； （2）訪問(wèn)根結(jié)點(diǎn)； （3）按中序遍歷右子樹(shù)。,中序遍歷（LDR）操作過(guò)程,后序遍歷（LRD）操作過(guò)程：,若二叉樹(shù)為空，則空操作，否則依次執(zhí)行如下操作： （1）按后序遍歷左子樹(shù)； （2）按后序遍歷右子樹(shù)； （3）訪問(wèn)根結(jié)點(diǎn)。,,對(duì)于如下圖的二叉樹(shù)，其先序、中序、后序遍歷的序列為： 先序遍歷： A、B、D、F、G、C、E、H 。 中序遍歷： B、F、D、G、A、C、E、H 。 后序遍歷： F、G、D、B、H、E、C、A 。,以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，討論二叉樹(shù)的遍歷算法,1) 先序遍歷,void PreOrder(BiTree root) /*先序遍歷二叉樹(shù),

19、root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針*/ if (root!=NULL) Visit(root -data); /*訪問(wèn)根結(jié)點(diǎn)*/ PreOrder(root -LChild); /*先序遍歷左子樹(shù)*/ PreOrder(root -RChild); /*先序遍歷右子樹(shù)*/ ,2) 中序遍歷,void InOrder(BiTree root) /*中序遍歷二叉樹(shù), root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹(shù)*/ Visit(root -data); /*訪問(wèn)根結(jié)點(diǎn)*/

20、InOrder(root -RChild); /*中序遍歷右子樹(shù)*/ ,3) 后序遍歷,void PostOrder(BiTree root) /* 后序遍歷二叉樹(shù)，root為指向二叉樹(shù)(或某一子樹(shù))根結(jié)點(diǎn)的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹(shù)*/ PostOrder(root -RChild); /*后序遍歷右子樹(shù)* Visit(root -data); /*訪問(wèn)根結(jié)點(diǎn)*/ ,以中序遍歷為例來(lái)說(shuō)明中序遍歷二叉樹(shù)的遞歸過(guò)程,A,B,D,C,E,,,,,,,,,,,第一次經(jīng)過(guò),第二次經(jīng)過(guò),第三次經(jīng)過(guò),6.3.2

21、基于棧的遞歸消除,1) 中序遍歷二叉樹(shù)的非遞歸算法,首先應(yīng)用遞歸進(jìn)層的三件事與遞歸退層的三件事的原則,直接先給出中序遍歷二叉樹(shù)的非遞歸算法基本實(shí)現(xiàn)思路。,中序遍歷二叉樹(shù)的非遞歸算法初步如下：,在大量復(fù)雜的情況下，遞歸的問(wèn)題無(wú)法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸算法進(jìn)層時(shí)需要將信息保留；當(dāng)遞歸算法出層時(shí)需要從棧區(qū)退出信息。,中序遍歷二叉樹(shù)的非遞歸算法（直接實(shí)現(xiàn)棧操作）,/*sm表示棧，top表示棧頂指針*/ Void inorder(BiTree root) /*中序遍歷二叉樹(shù)，bt為二叉樹(shù)的根結(jié)點(diǎn)*/ top=0;p=bt do while(p!

22、=NULL) if (topm) return(overflow); top=top+1; stop=p; p=p-Lchild; /*遍歷左子樹(shù)*/ if(top!=0), p=stop; top=top-1; Visit(p-data); /*訪問(wèn)根結(jié)點(diǎn)*/ p=p-Rchild; /*遍歷右子樹(shù)*/ while(p!=NULL||top!=0) ,中序遍歷二叉樹(shù)的非遞歸算法（調(diào)用棧操作的函數(shù)）,void InOrder（BiTree root）/* 中序遍歷二叉樹(shù)的非遞歸算法 */ InitStack ( ,2) 后序遍歷的二叉樹(shù)的

23、非遞歸算法,void PostOrder（BiTree root） BiTNode * p,*q； BiTNode **S； int top=0; q=NULL; p=root; S=（BiTNode**）malloc（sizeof（BiTNode*）*NUM）; /* NUM為預(yù)定義的常數(shù) */ while(p!=NULL || top!=0) while(p!=NULL) top=++; stop=p; p=p-LChild; /* 左子樹(shù)遍歷 */ if(top0), p=stop; if((p-RChild==NULL) ||(p-RChild==q)) /* 無(wú)右孩子，或

24、右孩子已遍歷過(guò) */ visit(p-data); /* 訪問(wèn)根結(jié)點(diǎn)* / q=p; /* 保存到q，為下一次已處理結(jié)點(diǎn)前驅(qū) */ top--; p=NULL; else p=p-RChild; free(s); ,6.3.3 遍歷算法應(yīng)用,二叉樹(shù)的遍歷運(yùn)算是一個(gè)重要的基礎(chǔ)。在實(shí)際應(yīng)用中，一是重點(diǎn)理解訪問(wèn)根結(jié)點(diǎn)操作的含義，二是注意對(duì)具體的實(shí)現(xiàn)問(wèn)題是否需要考慮遍歷的次序問(wèn)題。,1. 輸出二叉樹(shù)中的結(jié)點(diǎn),遍歷算法將走遍二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹(shù)中結(jié)點(diǎn)并無(wú)次序要求，因此可用任一種算法來(lái)完成。,先序遍歷輸出二叉樹(shù)中的結(jié)點(diǎn),void PreOrder(BiTree root) /

25、* 先序遍歷輸出二叉樹(shù)結(jié)點(diǎn), root為指向二叉樹(shù)根結(jié)點(diǎn)的指針 */ if (root!=NULL) printf (root -data); /* 輸出根結(jié)點(diǎn) */ PreOrder(root -LChild); /* 先序遍歷左子樹(shù) */ PreOrder(root -RChild); /* 先序遍歷右子樹(shù) */ ,問(wèn)題思考：若要求統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)應(yīng)如何去實(shí)現(xiàn)？,2. 輸出二叉樹(shù)中的葉子結(jié)點(diǎn),條件：判斷結(jié)點(diǎn)既沒(méi)有左孩子，又沒(méi)有右孩子時(shí)，則輸出該結(jié)點(diǎn)。,void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹(shù)中葉結(jié)點(diǎn) , root為指向二叉樹(shù)根結(jié)

26、點(diǎn)的指針 */ if (root!=NULL) if (root -LChild==NULL /* 先序遍歷右子樹(shù) */ ,3. 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目,/* LeafCount保存葉子結(jié)點(diǎn)數(shù)目的全局變量,調(diào)用之前初始化值為0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild==NULL ,方法一：,int leaf(BiTree root) int LeafCount; if(root==NULL) LeafCount =0;

27、 else if((root-LChild==NULL) ,方法二,/* 采用遞歸算法，如果是空樹(shù)，返回0；如果只有一個(gè)結(jié)點(diǎn)， 返回1；否則為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和 */,4. 建立二叉鏈表方式存儲(chǔ)的二叉樹(shù),給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說(shuō)的遍歷序列是一種“擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹(shù)。例如：,右圖中的二叉樹(shù)的“擴(kuò)展的遍歷序列”為：,AB.DF..G..C.E.H..,其中用小圓點(diǎn)表示空子樹(shù),利用“擴(kuò)展先序遍歷序列”創(chuàng)建二叉鏈表的算法為：,void CreateBiTree(BiTree *bt) char

28、ch; ch=getchar(); if(ch==.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)-data=ch; CreateBiTree( ,5. 求二叉樹(shù)的高度,設(shè)函數(shù)表示二叉樹(shù)bt的高度，則遞歸定義如下: 若bt為空，則高度為0 若bt非空，其高度應(yīng)為其左右子樹(shù)高度的最大值加1,,左 子 樹(shù),右 子 樹(shù),bt,,,,,hl,hr,,High=max(hl+hr)+1,后序遍歷求二叉樹(shù)的高度遞歸算法：,int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹(shù)的高度遞歸算法 */ int

29、 hl,hr,max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹(shù)的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹(shù)的深度 */ max=hlhr?hl:hr; /* 得到左、右子樹(shù)深度較大者*/ return(max+1); /* 返回樹(shù)的深度 */ else return(0); /* 如果是空樹(shù)，則返回0 */ ,問(wèn)題思考： 求二叉樹(shù)的深度是否可用先序遍歷的方式實(shí)現(xiàn)？若能，請(qǐng)寫(xiě)出實(shí)現(xiàn)算法，若不能，請(qǐng)說(shuō)明原因。,6. 按樹(shù)狀打印的二叉樹(shù),假設(shè)以二叉

30、鏈表存儲(chǔ)的二叉樹(shù)中，每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，要求實(shí)現(xiàn)如下圖的打印結(jié)果。,分析：這是二叉樹(shù)的橫向顯示問(wèn)題，橫向顯示應(yīng)是豎向顯示的900旋轉(zhuǎn)，又由于二叉樹(shù)的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹(shù)算法改為RDL結(jié)構(gòu)，實(shí)現(xiàn)算法為：,void PrintTree(TreeNode Root,int nLayer) /* 豎向樹(shù)狀打印的二叉樹(shù) */ if(Root= =NULL) return; PrintTree(Root-RChild,nLayer+1); for(int i=0;ich); PrintTree(Root-LChild,nLayer+1); ,6.3.4 線索

31、二叉樹(shù),1. 基本概念,二叉樹(shù)的遍歷運(yùn)算是將二叉樹(shù)中結(jié)點(diǎn)按一定規(guī)律線性化的過(guò)程。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹(shù)遍歷一遍，在遍歷過(guò)程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問(wèn)浪費(fèi)時(shí)間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來(lái)。,,在有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)鏈域，但只有n-1個(gè)有用非空鏈域，其余n+1個(gè)鏈域是空的。我們可以利用剩下的n+1個(gè)空鏈域來(lái)存放遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)和后繼信息。 現(xiàn)作如下規(guī)定：,若結(jié)點(diǎn)有左子樹(shù)，則其LChild域指向其

32、左孩子，否則LChild域指向其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)有右子樹(shù)，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點(diǎn)。,為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下圖所示：,其中：,,線索：在這種存儲(chǔ)結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。,線索鏈表：以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。,線索化：對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷并且加上線索的過(guò)程叫做線索化。,線索二叉樹(shù)：線索化了的二叉樹(shù)稱為線索二叉樹(shù)。,2. 二叉樹(shù)的線索化,線索化實(shí)質(zhì)上是將二叉鏈表中的空指針域填上相應(yīng)結(jié)點(diǎn)的遍歷前驅(qū)或后繼結(jié)點(diǎn)的地址，而前驅(qū)和后繼的地址只能在動(dòng)態(tài)的遍歷過(guò)程中才能得到

33、。因此線索化的過(guò)程是在遍歷過(guò)程中修改空指針域的過(guò)程。 對(duì)二叉樹(shù)按照不同的遍歷次序進(jìn)行線索化，可以得到不同的線索二叉樹(shù) （先序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)）。,中序線索化算法：,void Inthread(BiTree root) /* 對(duì)root所指的二叉樹(shù)進(jìn)行中序線索化，其中pre始終指向剛訪問(wèn)過(guò)的結(jié)點(diǎn)，其初值為NULL* / if (root!=NULL) Inthread(root-LChild); /* 線索化左子樹(shù) */ if (root-LChild==NULL) root-Ltag=1; root-LChile=pre; / *置前驅(qū)線索 */ if (p

34、re!=NULL /*線索化右子樹(shù)*/ ,下面是對(duì)同一棵二叉樹(shù)的遍歷方法不同得到的不同線索樹(shù)。,,NULL,3. 在線索二叉樹(shù)中找前驅(qū)、后繼結(jié)點(diǎn),1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn),根據(jù)線索二叉樹(shù)的基本概念和存儲(chǔ)結(jié)構(gòu)可知，對(duì)于結(jié)點(diǎn)p，當(dāng)p-Ltag=1時(shí)，p-LChild指向p的前驅(qū)。,當(dāng)p-Ltag=0時(shí)，p-LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點(diǎn)，它是中序遍歷p的左子樹(shù)時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，即左子樹(shù)的“最右下端”結(jié)點(diǎn)。其查找算法如下：,在中序線索樹(shù)中找結(jié)點(diǎn)前驅(qū)算法：,void InPre(BiTNode * p, BiTNode * pre) /* 在中序線索二叉

35、樹(shù)中查找p的中序前驅(qū), 并用pre指針?lè)祷亟Y(jié)果 */ if(p-Ltag==1) pre= p-LChild; /*直接利用線索*/ else /* 在p的左子樹(shù)中查找“最右下端”結(jié)點(diǎn) */ for(q= p-LChild;q-Rtag==0;q=q-RChild); pre=q; ,2）在中序線索樹(shù)中找結(jié)點(diǎn)后繼,對(duì)于結(jié)點(diǎn)p，若要找其后繼結(jié)點(diǎn)，當(dāng)p-Rtag=1時(shí)，p-RChild即為p的后繼結(jié)點(diǎn)；當(dāng)p-Rtag=0時(shí)，說(shuō)明p有右子樹(shù)，此時(shí)p的中序后繼結(jié)點(diǎn)即為其右子樹(shù)的“最左下端”的結(jié)點(diǎn)。其查找算法如下：,void InSucc(BiTNode * p, BiTNode * succ) /*

36、在中序線索二叉樹(shù)中查找p的后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/ if (p-Rtag==1) succ= p- RChild; /*直接利用線索*/ else /*在p的右子樹(shù)中查找“最左下端”結(jié)點(diǎn)*/ for(q= p-RChild; q-Ltag==0 ;q=q-LChild ); succ=q; ,6.4 樹(shù)、森林和二叉樹(shù)的關(guān)系,討論的重點(diǎn)： 樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換關(guān)系,6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu),樹(shù)的主要存儲(chǔ)方法有： 1.雙親表示法 2.孩子表示法 3.孩子兄弟表示法,1. 雙親表示法：用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來(lái)指示其

37、雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下：,,,,,,,,,,,,,,,,,樹(shù)的雙親表示法如下圖：,雙親表示法的優(yōu)點(diǎn)： 利用了樹(shù)中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。,雙親表示法的缺點(diǎn)： 在求某個(gè)結(jié)點(diǎn)的孩子時(shí)，需要遍歷整個(gè)向量。,雙親表示法的形式說(shuō)明如下：,#define MAX 100 typedef struct TNode DataType data; int parent; TNode;,一棵樹(shù)可以定義為：,typedef struct TNode treeMAX; int nodenum; /*結(jié)點(diǎn)數(shù)*/ ParentTree;,

38、2. 孩子表示法：通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表），而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。,樹(shù)的孩子鏈表表示法見(jiàn)p137的圖6.14,孩子表示法的形式說(shuō)明如下：,typedef struct ChildNode /* 孩子鏈表結(jié)點(diǎn)的定義 */ int Child; /* 該孩子結(jié)點(diǎn)在線性表中的位置 */ struct ChildNode * next; /*指向下一個(gè)孩子結(jié)點(diǎn)的指針 */ ChildNode; typedef struct /* 順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 */ D

39、ataType data; /* 結(jié)點(diǎn)的信息 */ ChildNode * FirstChild ; /* 指向孩子鏈表的頭指針 */ DataNode;,返回主目錄,typedef struct /* 樹(shù)的定義 */ DataNode nodesMAX; /* 順序表 */ int root,num; /* 該樹(shù)的根結(jié)點(diǎn)在線性表中的位置和該樹(shù)的結(jié)點(diǎn)個(gè)數(shù) */ ChildTree;,返回主目錄,3. 孩子兄弟表示法（二叉鏈表表示法）：鏈表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。,樹(shù)的孩子兄弟表示法見(jiàn)p137的圖6.15,孩子兄

40、弟表示法的類(lèi)型定義如下：,typedef struct CSNode DataType data; /*結(jié)點(diǎn)信息*/ Struct CSNode *FirstChild, *Nextsibling; /*第一個(gè)孩子,下一個(gè)兄弟*/ CSNode, *CSTree;,優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹(shù)的各種操作。,6.4.2 樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換,1. 樹(shù)轉(zhuǎn)換為二叉樹(shù),我們約定樹(shù)中每一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的次序順序編號(hào)，也就是說(shuō)，把樹(shù)作為有序樹(shù)看待。,例如：右圖的樹(shù),將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法：, 樹(shù)中所有相鄰兄弟之間加一條連線。 對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它

41、孩子結(jié)點(diǎn)之間的連線。 以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。,樹(shù)轉(zhuǎn)換為二叉樹(shù)的轉(zhuǎn)換過(guò)程示意見(jiàn)p137圖6.16,結(jié)論：從轉(zhuǎn)換過(guò)程可看出：樹(shù)中的任意一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)于二叉樹(shù)中的一個(gè)結(jié)點(diǎn)。樹(shù)中某結(jié)點(diǎn)的第一個(gè)孩子在二叉樹(shù)中是相應(yīng)結(jié)點(diǎn)的左孩子，樹(shù)中某結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)在二叉樹(shù)中是相應(yīng)結(jié)點(diǎn)的右孩子。也就是說(shuō)，在二叉樹(shù)中，左分支上的各結(jié)點(diǎn)在原來(lái)的樹(shù)中是父子關(guān)系，而右分支上的各結(jié)點(diǎn)在原來(lái)的樹(shù)中是兄弟關(guān)系。由于樹(shù)的根結(jié)點(diǎn)沒(méi)有兄弟，所以變換后的二叉樹(shù)的根結(jié)點(diǎn)的右孩子必然為空。,樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系及轉(zhuǎn)換方法,見(jiàn)p137的圖6.16所示,2. 森林轉(zhuǎn)換為二叉樹(shù),森林轉(zhuǎn)換為二叉樹(shù)的方法為

42、：,（1）將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。,（2）第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。,森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程見(jiàn)p138的圖6.17,用遞歸的方法描述森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程為：,將森林F看作樹(shù)的有序集F=T1，T2，,TN，它對(duì)應(yīng)的二叉樹(shù)為B（F）：,（1）若N0，則B（F）為空。,（2）若N0，二叉樹(shù)B（F）的根為森林中第一棵樹(shù)T1的根； B（F）的左子樹(shù)為B（T11，，T1m），其中T11，，T1m是T1的子樹(shù)森林；B（F）的右子樹(shù)是B（T2，，TN）。,3.

43、二叉樹(shù)還原為樹(shù)或森林,一棵二叉樹(shù)還原為樹(shù)或森林，具體方法為：,（1）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)。 （2）刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。 （3）整理由（1）、（2）兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。,一棵二叉樹(shù)還原為森林的過(guò)程示意:,用遞歸的方法描述其轉(zhuǎn)換過(guò)程為：,若B是一棵二叉樹(shù)，T是B的根結(jié)點(diǎn)，L是B的左子樹(shù)，R為B的右子樹(shù)，且B對(duì)應(yīng)的森林F（B）中含有的n棵樹(shù)為T(mén)1,T2, ,Tn，則有：,（1）B為空，則F（B）為空的森林（n0）。,（2）B非空，則F（B）中第一棵樹(shù)T1的根為二叉樹(shù)B的根T；T1中根

44、結(jié)點(diǎn)的子樹(shù)森林由B的左子樹(shù)L轉(zhuǎn)換而成，即F（L）=T11,,T1m；B的右子樹(shù)R轉(zhuǎn)換為F（B）中其余樹(shù)組成的森林，即F(R) T2, T3, ,Tn。,6.4.3 樹(shù)與森林的遍歷,1. 樹(shù)的遍歷,樹(shù)的遍歷方法主要有以下兩種：,1）先根遍歷,若樹(shù)非空，則遍歷方法為： （1）訪問(wèn)根結(jié)點(diǎn)。 （2）從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。,如圖中樹(shù)的先根遍歷序列為：ABECFHGD。,2）后根遍歷,若樹(shù)非空，則遍歷方法為：,（1）從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。 （2）訪問(wèn)根結(jié)點(diǎn)。,如圖中樹(shù)的后根遍歷序列為：EBHFGCDA。,2. 森林的遍歷,森林的遍歷方法主要有以下三種：,1）先序遍歷

45、,若森林非空，則遍歷方法為：,（1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)。 （2）先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 （3）先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。,2）中序遍歷,若森林非空，則遍歷方法為：,（1）中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 （2）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。 （3）中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。,3）后序遍歷,若森林非空，則遍歷方法為：,（1）后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 （2）后序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。 （3）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。,6.5 哈夫曼樹(shù)及其應(yīng)用,6.5.1 哈夫曼樹(shù),基本概念：,路徑：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)

46、之間的分支序列。 路徑長(zhǎng)度：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)的分支數(shù)目。 結(jié)點(diǎn)的權(quán)：給樹(shù)的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。,帶權(quán)路徑長(zhǎng)度：在樹(shù)形結(jié)構(gòu)中，我們把從樹(shù)根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。,樹(shù)的帶權(quán)路徑長(zhǎng)度：為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：,其中n為葉子結(jié)點(diǎn)的個(gè)數(shù)， wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。,例如下圖所示的具有不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù),WPL(a)=7252224236 WPL(b)=4273532146 WPL(c)=7152234335,圖例見(jiàn)p144的圖6.22

47、所示,問(wèn)題1：什么樣的二叉樹(shù)的路徑長(zhǎng)度WPL最?。?一棵樹(shù)的路徑長(zhǎng)度為0結(jié)點(diǎn)至多只有1個(gè)（根）；路徑長(zhǎng)度為1結(jié)點(diǎn)至多只有2個(gè)（兩個(gè)孩子）；路徑長(zhǎng)度為2結(jié)點(diǎn)至多只有4個(gè)；以此類(lèi)推：路徑長(zhǎng)度為K結(jié)點(diǎn)至多只有2k個(gè)，所以n個(gè)結(jié)點(diǎn)二叉樹(shù)其路徑長(zhǎng)度至少等于如下序列的前n項(xiàng)之和。,路徑長(zhǎng)度 0 ，1 ， 1 ，2， 2， 2， 2，3， 3，3，3，3，3，3，3，4，4，... 結(jié)點(diǎn)數(shù)n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 ... K=15,由此可知，結(jié)點(diǎn)n對(duì)應(yīng)的路徑長(zhǎng)度為 log2n ，所以前n項(xiàng)之和為:,完全二叉樹(shù)的路徑長(zhǎng)度為：,h為樹(shù)的深度，其路徑長(zhǎng)度可

48、達(dá)到最小，所以完全二叉樹(shù)具有最小路徑長(zhǎng)度的性質(zhì)，但不具有唯一性。,例如：下列不同形狀的二叉樹(shù)具有最小的路徑長(zhǎng)度,問(wèn)題2：什么樣的樹(shù)的帶權(quán)路徑長(zhǎng)度最??？,例如：給定一個(gè)權(quán)值序列2,3,4,7，可構(gòu)造的多種二叉樹(shù)的形態(tài)。,4. 哈夫曼樹(shù),哈夫曼樹(shù)又叫最優(yōu)二叉樹(shù)，它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹(shù)。,構(gòu)造哈夫曼算法的步驟如下：,（1）用給定的n個(gè)權(quán)值w1,w2, ,wn對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹(shù)的森林F=T1,T2, ,Tn，其中每一棵二叉樹(shù)Ti (1in)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)為空。,（2）在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)，作為一棵

49、新二叉樹(shù)的左、右子樹(shù)，標(biāo)記新二叉樹(shù)的根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)的根結(jié)點(diǎn)權(quán)值之和。,（3）從F中刪除被選中的那兩棵二叉樹(shù)，同時(shí)把新構(gòu)成的二叉樹(shù)加入到森林F中。,（4）重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹(shù)為止，此時(shí)得到的這棵二叉樹(shù)就是哈夫曼樹(shù)。,直觀地看，在哈夫曼樹(shù)中權(quán)越大的葉子離根越近，則其具有最小帶權(quán)路徑長(zhǎng)度。,哈夫曼樹(shù)的手工構(gòu)造的方法也非常簡(jiǎn)單：,給定數(shù)列W1....Wn，以n個(gè)權(quán)值構(gòu)成n棵樹(shù)的森林F；將F=T1....Tn按權(quán)從小到大排列； 取T1和T2合并組成一棵樹(shù)，使其根結(jié)點(diǎn)的權(quán)值T=T1+T2，再按大小插入F，反復(fù)此過(guò)程直到只有一棵樹(shù)為止。,6.5.2 哈夫曼編碼,哈夫曼樹(shù)

50、最典型的應(yīng)用是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹(shù)，我們可以得到平均長(zhǎng)度最短的編碼。,例如：設(shè)有一臺(tái)模型機(jī)，共有7種不同的指令，其使用頻率為：,變長(zhǎng)編碼為：,使用變長(zhǎng)編碼雖然可以使得程序的總位數(shù)達(dá)到最小，但機(jī)器卻無(wú)法解碼。如對(duì)編碼串0010110該怎樣識(shí)別呢？因此，若要設(shè)計(jì)變長(zhǎng)的編碼，則這種編碼必須滿足這樣一個(gè)條件：任意一個(gè)編碼不能成為其它任意編碼的前綴。我們把滿足這個(gè)條件的編碼叫做前綴編碼。,利用哈夫曼算法，我們可以設(shè)計(jì)出最優(yōu)的前綴編碼。見(jiàn)P148圖6.26。,對(duì)于該二叉樹(shù)，我們可以規(guī)定向左的分支標(biāo)記為1，向右的分支標(biāo)記為0。這樣，從根結(jié)點(diǎn)開(kāi)始，沿線到達(dá)各頻度指令對(duì)應(yīng)的葉結(jié)點(diǎn)，所經(jīng)過(guò)的分支代碼序

51、列就構(gòu)成了相應(yīng)頻度指令的哈夫曼編碼 。,指令的哈夫曼編碼,例如：傳送數(shù)據(jù)state,seat,act,tea,cat,set,a,eat，如何使傳送的長(zhǎng)度最短？,為了保證長(zhǎng)度最短，先看字符出現(xiàn)的次數(shù)，然后將出現(xiàn)次數(shù)當(dāng)作權(quán)。,按權(quán)構(gòu)造哈夫曼樹(shù)的過(guò)程見(jiàn)p144的圖6.33,規(guī)定二叉樹(shù)的構(gòu)造為左走0，右走1。,按規(guī)定：0左1右，則有,000 001 01 10 11 2 3 5 7 8 c s e a t,所以state的編碼為00111101101 stat的編碼為001111011。,構(gòu)造滿足哈夫曼編碼的最短最優(yōu)性質(zhì)：,（1）若didj（字母不同），則對(duì)應(yīng)的樹(shù)葉不同。因此

52、前綴碼（任一字符的編碼都不是另一個(gè)字符編碼 ）不同，一個(gè)路徑不可能是其他路徑的一部分，所以字母之間可以完全區(qū)別。,（2）將所有字符變成二進(jìn)制的哈夫曼編碼，使帶權(quán)路徑長(zhǎng)度最短，相當(dāng)總的通路長(zhǎng)度最短。,6.5.3 哈夫曼編碼算法的實(shí)現(xiàn),由于哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，則一棵有n個(gè)葉子的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)，可用一個(gè)大小為2n-1的一維數(shù)組來(lái)存放各個(gè)結(jié)點(diǎn)。,因?yàn)槊總€(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。,靜態(tài)三叉鏈表的描述如下：,typedef struct unsigned int weight ; /* 用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值*/ unsigned int parent, LChild,RChild ; /*指向雙親、孩子結(jié)點(diǎn)的指針*/ HTNode, * HuffmanTree; /*動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹(shù)*/ typedef char * *HuffmanCode ; /*動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼*/,創(chuàng)建哈夫曼樹(shù)并求哈夫曼編碼的算法 見(jiàn)p147的算法6.12,數(shù)組ht的前n個(gè)分量表示葉子結(jié)點(diǎn)，最后一個(gè)分量表示根結(jié)點(diǎn)。每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的編碼長(zhǎng)度不等，但最長(zhǎng)不超過(guò)n。,