數(shù)據(jù)結(jié)構(gòu)第6章2

1、6.6.1 樹(shù)的存儲(chǔ)樹(shù)的存儲(chǔ)6.6.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換6.6.3 樹(shù)和森林的遍歷樹(shù)和森林的遍歷6.6 6.6 樹(shù)和森林樹(shù)和森林6.6.1 6.6.1 樹(shù)的存儲(chǔ)樹(shù)的存儲(chǔ)樹(shù)的主要存儲(chǔ)方法有：樹(shù)的主要存儲(chǔ)方法有：一、雙親表示法一、雙親表示法二、孩子表示法二、孩子表示法三、孩子兄弟表示法三、孩子兄弟表示法一、一、 雙親表示法：雙親表示法： 用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下：點(diǎn)的結(jié)構(gòu)如下： 數(shù)據(jù)數(shù)據(jù) 雙親雙親DataPa

2、rent1245637樹(shù)的雙親表示法如下圖：樹(shù)的雙親表示法如下圖：1615140302-11ParentData543210結(jié)點(diǎn)結(jié)點(diǎn)序號(hào)序號(hào)673雙親表示法的優(yōu)點(diǎn)：雙親表示法的優(yōu)點(diǎn)： 利用了樹(shù)中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）利用了樹(shù)中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。 雙親表示法的缺點(diǎn)：雙親表示法的缺點(diǎn)： 求某個(gè)結(jié)點(diǎn)的孩子時(shí)，需要遍歷整求某個(gè)結(jié)點(diǎn)的孩子時(shí)，需要遍歷整個(gè)表。個(gè)表。 #define MAX 100typedef struct TNode DataType data; int pare

3、nt; TNode; 一棵樹(shù)可以定義為：一棵樹(shù)可以定義為：typedef struct TNode treeMAX; int root； int num; /*結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)*/ PTree; 雙親表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：雙親表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：二、二、 孩子表示法：孩子表示法： 通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n n個(gè)結(jié)點(diǎn)共有個(gè)結(jié)點(diǎn)共有n n個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表）。子鏈表為空表）。 n n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n n個(gè)孩子鏈表的頭個(gè)孩子鏈表的頭指針又組成

4、一個(gè)順序表。指針又組成一個(gè)順序表。 樹(shù)的孩子鏈表表示法見(jiàn)樹(shù)的孩子鏈表表示法見(jiàn)p142的圖的圖6.21孩子表示法示意圖孩子表示法示意圖:ABCDEFG1 A 2 B 3 C 4 D 5 E 6 F 7 Groot=1num=7 data fch75 6 2 3 4 0111335par帶雙親的孩子表示法帶雙親的孩子表示法:孩子表示法的結(jié)構(gòu)定義：孩子表示法的結(jié)構(gòu)定義：typedef struct ChildNode /* 孩子鏈表結(jié)點(diǎn)的定義孩子鏈表結(jié)點(diǎn)的定義 */int Child; struct ChildNode * next; ChildNode; typedef struct /* 樹(shù)的定

5、義樹(shù)的定義 */ DataNode nodesMAX; /* 順序表順序表 */ int root； int num; /* 根結(jié)點(diǎn)指示及結(jié)點(diǎn)個(gè)數(shù)根結(jié)點(diǎn)指示及結(jié)點(diǎn)個(gè)數(shù) */ CTree; CTree; typedef struct /* 順序表結(jié)點(diǎn)的結(jié)構(gòu)定義順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 */DataType data; ChildNode * FirstChild ; DataNode;三、三、 孩子兄弟表示法孩子兄弟表示法 孩子兄弟表示法孩子兄弟表示法又稱又稱二叉鏈表表示法二叉鏈表表示法，表，表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟

6、（右兄弟）結(jié)點(diǎn)。第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。 fch data nsib第一孩子第一孩子 下一兄弟下一兄弟結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):孩子兄弟表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：孩子兄弟表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：typedef struct CSNode DataType data; Struct CSNode *FirstChild； Struct CSNode *NextSibling; CSNode, CSNode, * *CSTree;CSTree; 孩子兄弟表示法示意圖：孩子兄弟表示法示意圖：ABCDEFGroot AB C E D F G優(yōu)點(diǎn)：優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹(shù)的各種操作；便于實(shí)現(xiàn)樹(shù)的各種操作；

7、可實(shí)現(xiàn)樹(shù)可實(shí)現(xiàn)樹(shù)( (森林森林) )與二叉樹(shù)的相互轉(zhuǎn)換。與二叉樹(shù)的相互轉(zhuǎn)換。ABCDEFGABCDEFG無(wú)兄弟無(wú)兄弟無(wú)右孩子無(wú)右孩子森林中森林中兄弟樹(shù)兄弟樹(shù)將轉(zhuǎn)為將轉(zhuǎn)為右子樹(shù)右子樹(shù)對(duì)應(yīng)的關(guān)系：對(duì)應(yīng)的關(guān)系： 樹(shù)樹(shù) 二叉樹(shù)二叉樹(shù) 根根 根根 第一孩子第一孩子 左孩子左孩子 下一兄弟下一兄弟 右孩子右孩子一、一、 樹(shù)轉(zhuǎn)換為二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù) 約定樹(shù)中每一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到約定樹(shù)中每一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的次序順序編號(hào)，即把樹(shù)看作為有序樹(shù)。右的次序順序編號(hào)，即把樹(shù)看作為有序樹(shù)。 6.6.2 6.6.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法：將一棵樹(shù)轉(zhuǎn)換為

8、二叉樹(shù)的方法： 加線：加線：樹(shù)中所有相鄰兄弟之間加一條連線。樹(shù)中所有相鄰兄弟之間加一條連線。 刪線：刪線：對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留其與第一對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。之間的連線。 旋轉(zhuǎn)調(diào)整旋轉(zhuǎn)調(diào)整：以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。 樹(shù)轉(zhuǎn)換為二叉樹(shù)示意圖樹(shù)轉(zhuǎn)換為二叉樹(shù)示意圖ABECDFGHABECDFGHABECDFGHABECDFGH森林轉(zhuǎn)換為二叉樹(shù)的方法為：森林轉(zhuǎn)換為二叉樹(shù)的方法為：（1

9、1）轉(zhuǎn)換：）轉(zhuǎn)換：將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。（2 2）加線：）加線：將相鄰的二叉樹(shù)的根結(jié)點(diǎn)之間加線將相鄰的二叉樹(shù)的根結(jié)點(diǎn)之間加線（3 3）旋轉(zhuǎn)調(diào)整：）旋轉(zhuǎn)調(diào)整：以第一棵二叉樹(shù)的根為軸心，以第一棵二叉樹(shù)的根為軸心，將整個(gè)樹(shù)順時(shí)鐘旋轉(zhuǎn)到一定角度，使之層次結(jié)構(gòu)將整個(gè)樹(shù)順時(shí)鐘旋轉(zhuǎn)到一定角度，使之層次結(jié)構(gòu)清晰，左右子樹(shù)分明。依次把后一棵二叉樹(shù)調(diào)整清晰，左右子樹(shù)分明。依次把后一棵二叉樹(shù)調(diào)整為前一棵二叉樹(shù)根節(jié)點(diǎn)的右孩子。為前一棵二叉樹(shù)根節(jié)點(diǎn)的右孩子。二、森林轉(zhuǎn)換為二叉樹(shù)二、森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù)示意圖森林轉(zhuǎn)換為二叉樹(shù)示意圖 B E CH D I F J

10、 G B C D E F GH I J森林轉(zhuǎn)換為二叉樹(shù)的實(shí)例另見(jiàn)森林轉(zhuǎn)換為二叉樹(shù)的實(shí)例另見(jiàn)p145的圖的圖6.27二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林的方法為：二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林的方法為：（1 1）加線：）加線：若某結(jié)點(diǎn)是其雙親的左孩子，則若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)。都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)。 （2 2）刪線：）刪線：刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。右孩子結(jié)點(diǎn)的連線。 （3 3）旋轉(zhuǎn)調(diào)整：）旋轉(zhuǎn)調(diào)整：整理由（整理由（1 1）、（）、（2 2）兩步所）兩步所得到的

11、樹(shù)或森林，使之結(jié)構(gòu)層次分明。得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。 三、二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林三、二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林 二叉樹(shù)轉(zhuǎn)換為森林的示意圖二叉樹(shù)轉(zhuǎn)換為森林的示意圖DABCEFGHIJDABCEFGHIJHIJGDABCEF四、遞歸方法描述森林轉(zhuǎn)換為二叉樹(shù)四、遞歸方法描述森林轉(zhuǎn)換為二叉樹(shù): : 將森林將森林F F看作樹(shù)的有序集看作樹(shù)的有序集F=TF=T1 1，T T2 2，,T,TN N ，它對(duì)應(yīng)的二叉樹(shù)為它對(duì)應(yīng)的二叉樹(shù)為B B（F F）：）： （1 1）若）若N N0 0，則，則B B（F F）為空。）為空。 （2 2）若）若N0N0，則：，則： 二叉樹(shù)二叉樹(shù)B B（F F）的根為森林中第一棵

12、樹(shù)）的根為森林中第一棵樹(shù)T T1 1的根；的根； B B（F F）的左子樹(shù)為）的左子樹(shù)為B B（TT1111，T T1m1m ），其），其中中TT1111，T T1m1m 是是T T1 1的子樹(shù)森林；的子樹(shù)森林； B B（F F）的右子樹(shù)是）的右子樹(shù)是B B（T2T2，T TN N ）。）。 若若B B是一棵二叉樹(shù)，是一棵二叉樹(shù)，T T是是B B的根結(jié)點(diǎn)，的根結(jié)點(diǎn)，L L是是B B的的左子樹(shù)，左子樹(shù)，R R為為B B的右子樹(shù)，設(shè)的右子樹(shù)，設(shè)B B對(duì)應(yīng)的森林對(duì)應(yīng)的森林F F（B B）中含有的中含有的n n棵樹(shù)為棵樹(shù)為T(mén) T1 1,T,T2 2, ,T, ,Tn n，則有：，則有： （1 1）B

13、B為空，則：為空，則：F F（B B）為空的森林（）為空的森林（n n0 0）。）。 （2 2）B B非空，則：非空，則： F F（B B）中第一棵樹(shù)）中第一棵樹(shù)T T1 1的根為二叉樹(shù)的根為二叉樹(shù)B B的根的根T T； T T1 1中根結(jié)點(diǎn)的子樹(shù)森林由中根結(jié)點(diǎn)的子樹(shù)森林由B B的左子樹(shù)的左子樹(shù)L L轉(zhuǎn)換而轉(zhuǎn)換而成，即成，即F F（L L）=T=T1111,T,T1m1m ； B B的右子樹(shù)的右子樹(shù)R R轉(zhuǎn)換為轉(zhuǎn)換為F F（B B）中其余樹(shù)組成的森）中其余樹(shù)組成的森林，即林，即F(R)F(R) T T2 2, T, T3 3, ,T, ,Tn n 。 五、用遞歸的方法描述其轉(zhuǎn)換五、用遞歸的方法

14、描述其轉(zhuǎn)換6.6.3 6.6.3 樹(shù)和森林的遍歷樹(shù)和森林的遍歷一、一、 樹(shù)的遍歷樹(shù)的遍歷樹(shù)的遍歷主要有以下兩種：樹(shù)的遍歷主要有以下兩種： 先根遍歷先根遍歷 后根遍歷后根遍歷1 1、先根遍歷、先根遍歷若樹(shù)非空，則遍歷過(guò)程為：若樹(shù)非空，則遍歷過(guò)程為：（1）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。（2）從左到右，依次）從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。 ABECDFGH如圖中樹(shù)的先根遍歷序列為：如圖中樹(shù)的先根遍歷序列為：ABECFHGD。若樹(shù)非空，則遍歷過(guò)程為：若樹(shù)非空，則遍歷過(guò)程為：（1 1）從左到右，依次后根遍歷根結(jié)點(diǎn)的每一）從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。棵子樹(shù)

15、。（2 2）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。ABECDFGH如圖樹(shù)的后根遍歷序列為：如圖樹(shù)的后根遍歷序列為： EBHFGCDA。2 2、后根遍歷、后根遍歷 A B E CH D I F J G A B C D E F GH I J樹(shù)的后根遍歷：樹(shù)的后根遍歷：H I J E B C F G D A樹(shù)的先根遍歷：樹(shù)的先根遍歷：A B E H I J C D F G對(duì)應(yīng)二叉樹(shù)的先序遍歷對(duì)應(yīng)二叉樹(shù)的先序遍歷 對(duì)應(yīng)二叉樹(shù)的中序遍歷對(duì)應(yīng)二叉樹(shù)的中序遍歷 二、樹(shù)的遍歷算法二、樹(shù)的遍歷算法 先根遍歷方法一先根遍歷方法一void RootFirst(CSTree root) if (root!=NULL) Visit

16、(root -data); /* 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) */ p= root- FirstChild; while (p!=NULL) RootFirst( p ); /* 訪問(wèn)以訪問(wèn)以p為根的子樹(shù)為根的子樹(shù) */ p = p - NextSibling; 先根遍歷方法二先根遍歷方法二 void RootFirst(CSTree root) if (root!=NULL) Visit (root -data); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ RootFirst (root- FirstChild); /*先根遍歷首子樹(shù)先根遍歷首子樹(shù)*/ RootFirst (root- NextSibling

17、); /*先根遍歷兄弟先根遍歷兄弟樹(shù)樹(shù)*/ 三、森林的遍歷三、森林的遍歷森林的遍歷方法主要有以下三種：森林的遍歷方法主要有以下三種：先序遍歷先序遍歷 中序遍歷中序遍歷 * *后序遍歷后序遍歷1 1、先序遍歷、先序遍歷若森林非空，則遍歷方法為：若森林非空，則遍歷方法為：（1 1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)。）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)。（2 2）先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。）先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 （3 3）先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成）先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。的森林。 即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn) 行

18、行先根遍歷先根遍歷。若森林非空，則遍歷方法為：若森林非空，則遍歷方法為：（1 1）中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的）中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的 子樹(shù)森林。子樹(shù)森林。 （2 2）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。 （3 3）中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)）中序遍歷除去第一棵樹(shù)之后剩余的樹(shù) 構(gòu)成的森林。構(gòu)成的森林。 2 2、中序遍歷、中序遍歷即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行 后根遍歷后根遍歷。 先序遍歷先序遍歷森林時(shí)頂點(diǎn)時(shí)頂點(diǎn)的訪問(wèn)次序：的訪問(wèn)次序：A B C D E F G H I J 中序遍歷中序遍歷森林時(shí)頂點(diǎn)時(shí)頂點(diǎn)的訪問(wèn)次序：的

19、訪問(wèn)次序：B C D A F E I H J G A E GB C D F H J I AB E C F G D H I J 樹(shù)和森林的遍歷和二叉樹(shù)和森林的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系樹(shù)遍歷的對(duì)應(yīng)關(guān)系 ？先根遍歷先根遍歷后根遍歷后根遍歷樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷3 3、森林的后序遍歷、森林的后序遍歷* *若森林非空，則遍歷方法為：若森林非空，則遍歷方法為：（1 1）后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子）后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。樹(shù)森林。 （2 2）后序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)）后序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的

20、森林。成的森林。 （3 3）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。 6.7 6.7 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用6.7.1 6.7.1 哈夫曼樹(shù)哈夫曼樹(shù) 哈夫曼樹(shù)最典型、最廣泛的應(yīng)用是在哈夫曼樹(shù)最典型、最廣泛的應(yīng)用是在編碼技術(shù)上，利用哈夫曼樹(shù)，可以得到編碼技術(shù)上，利用哈夫曼樹(shù)，可以得到平均長(zhǎng)度最短的編碼。這在通訊領(lǐng)域是平均長(zhǎng)度最短的編碼。這在通訊領(lǐng)域是極其有價(jià)值的。極其有價(jià)值的。 計(jì)算機(jī)程序操作碼的優(yōu)化也可以利用計(jì)算機(jī)程序操作碼的優(yōu)化也可以利用哈夫曼樹(shù)實(shí)現(xiàn)。哈夫曼樹(shù)實(shí)現(xiàn)。路徑：路徑：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支 序列。序列。路徑長(zhǎng)度：路徑長(zhǎng)度：從

21、一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò) 的分支條數(shù)。的分支條數(shù)。樹(shù)的路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度：樹(shù)中每個(gè)結(jié)點(diǎn)與根之間的路徑樹(shù)中每個(gè)結(jié)點(diǎn)與根之間的路徑 長(zhǎng)度之和長(zhǎng)度之和（PL）。a例：例：PL(a)=1+1+2+2+2+2=10 bPL(b)=1+1+2+2+3+3=12一、基本概念：一、基本概念：帶權(quán)路徑長(zhǎng)度：帶權(quán)路徑長(zhǎng)度：在樹(shù)形結(jié)構(gòu)中，我們把從樹(shù)根在樹(shù)形結(jié)構(gòu)中，我們把從樹(shù)根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積，稱到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積，稱做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路

22、徑長(zhǎng)度之和，稱為樹(shù)的帶權(quán)路徑長(zhǎng)度，通常路徑長(zhǎng)度之和，稱為樹(shù)的帶權(quán)路徑長(zhǎng)度，通常記為記為WPL：WPL= wilii=1n其中：其中：n n為葉子結(jié)點(diǎn)的個(gè)數(shù)；為葉子結(jié)點(diǎn)的個(gè)數(shù)；w wi i為第為第i i個(gè)葉子的權(quán)值；個(gè)葉子的權(quán)值； l li i為第為第i i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。結(jié)點(diǎn)的權(quán)：結(jié)點(diǎn)的權(quán)：給樹(shù)中每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種給樹(shù)中每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種 實(shí)際意義的數(shù)值，我們稱該數(shù)值為這個(gè)結(jié)點(diǎn)的權(quán)。實(shí)際意義的數(shù)值，我們稱該數(shù)值為這個(gè)結(jié)點(diǎn)的權(quán)。例如下圖所示的三棵二叉樹(shù)例如下圖所示的三棵二叉樹(shù)WPL(a)=7252224236其帶權(quán)路徑長(zhǎng)度分別為：其帶權(quán)路徑長(zhǎng)度分別為：24

23、57a75 4b25 42c7WPL(b)=4273532146WPL(c)=7152234335 問(wèn)題問(wèn)題1 1：什么樣的二叉樹(shù)的路徑長(zhǎng)度什么樣的二叉樹(shù)的路徑長(zhǎng)度PLPL最?。孔钚?？分析：分析：二叉樹(shù)中路徑長(zhǎng)度為二叉樹(shù)中路徑長(zhǎng)度為0 0的結(jié)點(diǎn)只有的結(jié)點(diǎn)只有1 1個(gè)；個(gè)； 路徑長(zhǎng)度路徑長(zhǎng)度 0 0 ，1 1，1 1，2 2，2 2，2 2，2 2，3 3，3 3，33，4 4，4 4，. .結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)n n=1 n=2,3 n=4, 5 ,6 , 7 n=8. n=15 n=16可知：結(jié)點(diǎn)可知：結(jié)點(diǎn)n對(duì)應(yīng)的路徑長(zhǎng)度為對(duì)應(yīng)的路徑長(zhǎng)度為 log2n 路徑長(zhǎng)度為路徑長(zhǎng)度為1 1的結(jié)點(diǎn)至多只有的結(jié)點(diǎn)

24、至多只有2 2個(gè)；個(gè)；路徑長(zhǎng)度為路徑長(zhǎng)度為2 2的結(jié)點(diǎn)至多只有的結(jié)點(diǎn)至多只有4 4個(gè)；個(gè)；路徑長(zhǎng)度為路徑長(zhǎng)度為K K的結(jié)點(diǎn)至多只有的結(jié)點(diǎn)至多只有2 2k k個(gè)個(gè); ; 所以所以n n個(gè)結(jié)點(diǎn)的二叉樹(shù)其路徑長(zhǎng)度至少等于個(gè)結(jié)點(diǎn)的二叉樹(shù)其路徑長(zhǎng)度至少等于如下序列的前如下序列的前n n項(xiàng)之和。項(xiàng)之和。nk=1 log2k 所以所以n個(gè)結(jié)點(diǎn)二叉樹(shù)的個(gè)結(jié)點(diǎn)二叉樹(shù)的PL至少為至少為前前n項(xiàng)之和項(xiàng)之和:因?yàn)樯疃葹橐驗(yàn)樯疃葹閔 h的完全二叉樹(shù)的路徑長(zhǎng)度為：的完全二叉樹(shù)的路徑長(zhǎng)度為：200+21 1+22 2+ 2h h = hk=1 log2k 所以所以完全二叉樹(shù)完全二叉樹(shù)具有樹(shù)的路徑長(zhǎng)度為最小具有樹(shù)的路徑長(zhǎng)度為

25、最小的性質(zhì)，但不具有唯一性。的性質(zhì)，但不具有唯一性。例如：下列不同形狀的二叉樹(shù)均具有最小的路徑長(zhǎng)度例如：下列不同形狀的二叉樹(shù)均具有最小的路徑長(zhǎng)度ABCDEPL=0+1+1+2+2=6ABDCEPL=0+1+1+2+2=6ABCDEPL=0+1+1+2+2=6 故：故：深度為深度為h h的二叉樹(shù)若前的二叉樹(shù)若前h-1h-1層為滿二叉樹(shù)，層為滿二叉樹(shù)， 則則具有最小的路徑長(zhǎng)度。具有最小的路徑長(zhǎng)度。什么樣的樹(shù)的帶權(quán)路徑長(zhǎng)度什么樣的樹(shù)的帶權(quán)路徑長(zhǎng)度WPL最小？最小？ 例如：給定一個(gè)權(quán)值序列例如：給定一個(gè)權(quán)值序列2, 4, 5, 7，可構(gòu)造，可構(gòu)造多種二叉樹(shù)的形態(tài)多種二叉樹(shù)的形態(tài):問(wèn)題問(wèn)題2 2：245

26、7a75 4b25 42c7 WPL(a) 36 WPL(b) 46 WPL(c)35 其帶權(quán)路徑長(zhǎng)度分別為：其帶權(quán)路徑長(zhǎng)度分別為： 在各種形態(tài)的含有在各種形態(tài)的含有 n個(gè)葉子結(jié)點(diǎn)的個(gè)葉子結(jié)點(diǎn)的 二二 叉樹(shù)中叉樹(shù)中, 必存在一棵必存在一棵(幾棵幾棵)其其帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度值值WPL 最小最小的樹(shù)，被稱為的樹(shù)，被稱為“最優(yōu)二叉最優(yōu)二叉樹(shù)樹(shù)” 。 特征：特征：在最優(yōu)二叉樹(shù)中沒(méi)有度數(shù)為在最優(yōu)二叉樹(shù)中沒(méi)有度數(shù)為 1 的結(jié)的結(jié)點(diǎn)點(diǎn)(可用反證法證明可用反證法證明); 含含 n個(gè)葉子結(jié)點(diǎn)的最優(yōu)二個(gè)葉子結(jié)點(diǎn)的最優(yōu)二叉樹(shù)的總結(jié)點(diǎn)數(shù)為叉樹(shù)的總結(jié)點(diǎn)數(shù)為 2* *n- -1 (依據(jù)二叉樹(shù)性質(zhì)三依據(jù)二叉樹(shù)性質(zhì)三)

27、。 最優(yōu)二叉樹(shù)的構(gòu)造方法最早由哈夫曼最優(yōu)二叉樹(shù)的構(gòu)造方法最早由哈夫曼研究，所以又稱為研究，所以又稱為“哈夫曼樹(shù)哈夫曼樹(shù)”。二、哈夫曼樹(shù)的構(gòu)造二、哈夫曼樹(shù)的構(gòu)造 (1) 初始化：初始化：根據(jù)給定的根據(jù)給定的 n 個(gè)權(quán)值個(gè)權(quán)值 w1, w2, , wn ,構(gòu)造構(gòu)造 n 棵二叉樹(shù)的集合棵二叉樹(shù)的集合 F = T1, T2, , Tn， 其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；構(gòu)造哈夫曼樹(shù)的方法：構(gòu)造哈夫曼樹(shù)的方法： 找最小樹(shù)并構(gòu)造新樹(shù)：在找最小樹(shù)并構(gòu)造新樹(shù)：在 F 中選取其根結(jié)中選取其根結(jié)點(diǎn)的權(quán)值為最小的

28、兩棵二叉樹(shù)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù), 分別作為左、分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)右子樹(shù)構(gòu)造一棵新的二叉樹(shù), 并置這棵新的二并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；權(quán)值之和；(2)刪除與插入：從刪除與插入：從F中刪去這兩棵樹(shù)中刪去這兩棵樹(shù),并加入剛并加入剛生成的新樹(shù)；生成的新樹(shù)； 重復(fù)重復(fù) (2) 和和 (3) ,直至直至 F 中只含一棵樹(shù)為止。中只含一棵樹(shù)為止。(3)(4) 由此得到二叉樹(shù)就是由此得到二叉樹(shù)就是“最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)” ” 即即“哈夫曼樹(shù)哈夫曼樹(shù)” ” 。 例如例如: : 已知權(quán)值已知權(quán)值 W= 5, 6, 2

29、, 9, 7 9562752769767139527構(gòu)造哈夫曼樹(shù)如下：構(gòu)造哈夫曼樹(shù)如下：952716671329三、哈夫曼算法的實(shí)現(xiàn)三、哈夫曼算法的實(shí)現(xiàn) n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),因此可用有因此可用有2n-1個(gè)元素的個(gè)元素的數(shù)組數(shù)組來(lái)存儲(chǔ)哈夫曼樹(shù)來(lái)存儲(chǔ)哈夫曼樹(shù), 結(jié)點(diǎn)間的結(jié)點(diǎn)間的關(guān)系用游標(biāo)表示關(guān)系用游標(biāo)表示，即采用，即采用靜態(tài)鏈表靜態(tài)鏈表來(lái)來(lái)存儲(chǔ)哈夫曼樹(shù)。存儲(chǔ)哈夫曼樹(shù)。 1、存儲(chǔ)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu) 每個(gè)結(jié)點(diǎn)需包含其雙親結(jié)點(diǎn)信息和孩子結(jié)每個(gè)結(jié)點(diǎn)需包含其雙親結(jié)點(diǎn)信息和孩子結(jié)點(diǎn)信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。點(diǎn)信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。 weight

30、parent Lchild Rchild 權(quán)值權(quán)值 雙親序號(hào)雙親序號(hào) 左孩子序號(hào)左孩子序號(hào) 右孩子序號(hào)右孩子序號(hào) 靜態(tài)三叉鏈表結(jié)構(gòu)定義靜態(tài)三叉鏈表結(jié)構(gòu)定義#define N 30#define M 2*N-1 typedef struct int weight ; int parent，Lchild，Rchild ; HTNode, HuffmanTreeM+1; /*0號(hào)單元不用號(hào)單元不用*/ 靜態(tài)三叉鏈表靜態(tài)三叉鏈表數(shù)組中數(shù)組中前前 n 個(gè)元素存儲(chǔ)葉子結(jié)點(diǎn)，個(gè)元素存儲(chǔ)葉子結(jié)點(diǎn)，后后n-1個(gè)元素存儲(chǔ)分支結(jié)點(diǎn)即不斷生成的新結(jié)點(diǎn)，個(gè)元素存儲(chǔ)分支結(jié)點(diǎn)即不斷生成的新結(jié)點(diǎn)，最后一個(gè)元素存儲(chǔ)哈夫曼樹(shù)的根

31、結(jié)點(diǎn)。最后一個(gè)元素存儲(chǔ)哈夫曼樹(shù)的根結(jié)點(diǎn)。 2、哈夫曼算法、哈夫曼算法 初始化：先將初始化：先將n個(gè)元素都視為根結(jié)點(diǎn)，個(gè)元素都視為根結(jié)點(diǎn)，即孩子和雙親指針全置即孩子和雙親指針全置0。 建哈夫曼樹(shù)的過(guò)程是：反復(fù)在數(shù)組中建哈夫曼樹(shù)的過(guò)程是：反復(fù)在數(shù)組中選雙親為選雙親為0(表示它們當(dāng)前是樹(shù)根表示它們當(dāng)前是樹(shù)根)且權(quán)值最且權(quán)值最小的兩結(jié)點(diǎn)小的兩結(jié)點(diǎn), 將它們作為左右孩子掛在新將它們作為左右孩子掛在新的結(jié)點(diǎn)之下的結(jié)點(diǎn)之下, 新結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值新結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和。之和。 void CrtHuffmanTree(HuffmanTree ht , int w, int n) /* w存放已知的存

32、放已知的n個(gè)權(quán)值，構(gòu)造哈夫曼樹(shù)個(gè)權(quán)值，構(gòu)造哈夫曼樹(shù)ht */ m=2*n-1; for(i=1;i=n;i+) hti=wi,0,0,0; for(i=n+1;i=m;i+) hti=0,0,0,0;for(i=n+1;i=m;i+) select(ht,i-1,&s1,&s2); / /* *htht前前i-1i-1項(xiàng)選雙親為零且權(quán)最小的兩結(jié)點(diǎn)項(xiàng)選雙親為零且權(quán)最小的兩結(jié)點(diǎn)* */ / ht i.weight=hts1.weight+hts2.weight; hti.Lchild=s1;ht i.Rchild=s2; hts1.parent=i;hts2.parent=i; 例

33、給定權(quán)值例給定權(quán)值: 9,14 ,10 ,10, 12, 13, 9 ,11 i wt par Lch Rch1 5 0 0 02 29 0 0 03 7 0 0 04 8 0 0 05 14 0 0 06 23 0 0 07 3 0 0 08 11 0 0 09 0 0 0 010 0 0 0 011 0 0 0 012 0 0 0 013 0 0 0 014 0 0 0 015 0 0 0 08 0 1 79915 0 3 4101019 0 8 9111129 0 5 10121242 0 6 11131358 0 2 121414100 0 13 141515for(i=1;i=n;i

34、+) hti=wi,0,0,0;for(i=n+1;i=m;i+) hti=0,0,0,0;for(i=n+1;i=m;i+) select(ht,i-1,&s1,&s2); hts1.parent=i; hts2.parent=i; hti.Lchild=s1; hti.Rchild=s2; hti.weight=hts1.weight +hts2.weight; 哈夫曼樹(shù)最典型的應(yīng)用是在編碼，利用哈哈夫曼樹(shù)最典型的應(yīng)用是在編碼，利用哈夫曼樹(shù)，可以得到平均長(zhǎng)度最短的編碼。夫曼樹(shù)，可以得到平均長(zhǎng)度最短的編碼。6.7.2 6.7.2 哈夫曼編碼哈夫曼編碼 平均長(zhǎng)度最短的編碼一般為

35、不等長(zhǎng)編碼，平均長(zhǎng)度最短的編碼一般為不等長(zhǎng)編碼，為使各編碼間無(wú)需加分界符即可識(shí)別，其編碼為使各編碼間無(wú)需加分界符即可識(shí)別，其編碼應(yīng)是應(yīng)是前綴碼。前綴碼。前綴碼：前綴碼：同一字符集中任何一個(gè)字符的編碼都同一字符集中任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴（最左子串）不是另一個(gè)字符編碼的前綴（最左子串）。一、概念一、概念 利用哈夫曼樹(shù)可以構(gòu)造不等長(zhǎng)的二進(jìn)制編利用哈夫曼樹(shù)可以構(gòu)造不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的編碼是一種碼，并且構(gòu)造所得的編碼是一種最優(yōu)前綴編碼最優(yōu)前綴編碼，即可以使所傳信息的總長(zhǎng)度最短。即可以使所傳信息的總長(zhǎng)度最短。二、哈夫曼編碼二、哈夫曼編碼: : 對(duì)對(duì)哈夫曼樹(shù)哈夫曼樹(shù)中每個(gè)

36、左分支賦予中每個(gè)左分支賦予0 0，右分支，右分支賦予賦予1 1，則從根到每個(gè)葉子的路徑上，各分支，則從根到每個(gè)葉子的路徑上，各分支的值構(gòu)成該葉子的的值構(gòu)成該葉子的哈夫曼編碼。哈夫曼編碼。例：若要傳輸如下單詞例：若要傳輸如下單詞 state, seat, act, tea, cat, set, a, eat如何使所傳送的信息編碼長(zhǎng)度最短？如何使所傳送的信息編碼長(zhǎng)度最短？ 為保證信息編碼長(zhǎng)度最短，先統(tǒng)計(jì)各字為保證信息編碼長(zhǎng)度最短，先統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)，然后以此作為權(quán)值符出現(xiàn)的次數(shù)，然后以此作為權(quán)值, , 構(gòu)造哈構(gòu)造哈夫曼樹(shù)。夫曼樹(shù)。723515851025000011110010010011編碼

37、編碼:左分支左分支:0右分支右分支:1；根到葉子路徑上的值構(gòu)根到葉子路徑上的值構(gòu)成葉子的編碼。成葉子的編碼。11需傳輸信息：需傳輸信息：state, seat, act, tea, cat, set, a, eat25783ceats各字符權(quán)值：各字符權(quán)值：010001011011ceats各字符編碼：各字符編碼： 構(gòu)造哈夫曼樹(shù)：構(gòu)造哈夫曼樹(shù)：結(jié)論一：結(jié)論一：哈夫曼編碼是前綴碼。哈夫曼編碼是前綴碼。結(jié)論二結(jié)論二: :哈夫曼編碼是最優(yōu)前綴碼。哈夫曼編碼是最優(yōu)前綴碼。 若若d di iddj j( (字符不同字符不同) )，則對(duì)應(yīng)的樹(shù)葉不同，則對(duì)應(yīng)的樹(shù)葉不同，因?yàn)閺母矫總€(gè)葉子的路徑是不同的，所以

38、一因?yàn)閺母矫總€(gè)葉子的路徑是不同的，所以一條路徑不可能是另一條路徑的前部（前綴），條路徑不可能是另一條路徑的前部（前綴），因此哈夫曼編碼是前綴碼。因此哈夫曼編碼是前綴碼。 用字符出現(xiàn)的頻率用字符出現(xiàn)的頻率( (Pi) )為權(quán)值構(gòu)造哈夫曼為權(quán)值構(gòu)造哈夫曼樹(shù)樹(shù), ,并以此來(lái)構(gòu)造字符的哈夫曼編碼，由于哈并以此來(lái)構(gòu)造字符的哈夫曼編碼，由于哈夫曼樹(shù)的夫曼樹(shù)的WPLWPL最小：最?。核詡鬏?shù)膱?bào)文長(zhǎng)度：所以傳輸?shù)膱?bào)文長(zhǎng)度： 必定最小。必定最小。 WPL= wilii=1n報(bào)文長(zhǎng)報(bào)文長(zhǎng)= Pilii=1n三、哈夫曼編碼應(yīng)用舉例三、哈夫曼編碼應(yīng)用舉例例：例：設(shè)有一臺(tái)模型機(jī)，共有設(shè)有一臺(tái)模型機(jī)，共有7 7種不同

39、的指令，種不同的指令，各指令的使用頻率各指令的使用頻率Pi為：為：指指 令令I(lǐng)1I2I3I4I5I6I7 使用頻率使用頻率pi0.400.300.150.050.040.030.03 哈夫曼樹(shù)最典型、最廣泛的應(yīng)用是在編碼哈夫曼樹(shù)最典型、最廣泛的應(yīng)用是在編碼技術(shù)上，而操作碼的優(yōu)化也是其應(yīng)用之一。技術(shù)上，而操作碼的優(yōu)化也是其應(yīng)用之一。 以指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹(shù)，以指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹(shù)，并求各指令的哈夫曼編碼。并求各指令的哈夫曼編碼。則指令的平均碼長(zhǎng)為：則指令的平均碼長(zhǎng)為：pili =0.4*7+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5

40、 = 2.20ni=1若用等長(zhǎng)編碼，其平均碼長(zhǎng)為若用等長(zhǎng)編碼，其平均碼長(zhǎng)為3。 指令指令I(lǐng)1I2I3I4I5I6I7編碼編碼10100100011000100000100000各指令的哈夫曼編碼為：各指令的哈夫曼編碼為： 四、哈夫曼編碼算法四、哈夫曼編碼算法 利用哈夫曼樹(shù)求編碼時(shí)，編碼是利用哈夫曼樹(shù)求編碼時(shí)，編碼是由后向前生成的，需要走一條從葉子由后向前生成的，需要走一條從葉子到根的路徑：到根的路徑： 當(dāng)前結(jié)點(diǎn)若是其雙親的左子樹(shù)時(shí)，當(dāng)前結(jié)點(diǎn)若是其雙親的左子樹(shù)時(shí)，則置當(dāng)前編碼位為則置當(dāng)前編碼位為0，否則置為，否則置為1。 當(dāng)由葉子走到根結(jié)點(diǎn)時(shí)，完成一當(dāng)由葉子走到根結(jié)點(diǎn)時(shí)，完成一個(gè)葉子結(jié)點(diǎn)編碼的求

41、取。個(gè)葉子結(jié)點(diǎn)編碼的求取。 由哈夫曼樹(shù)生成編碼時(shí)由哈夫曼樹(shù)生成編碼時(shí), 編碼存儲(chǔ)在多個(gè)字編碼存儲(chǔ)在多個(gè)字符數(shù)組中符數(shù)組中, 每個(gè)數(shù)組表示一個(gè)葉子結(jié)點(diǎn)的編碼。每個(gè)數(shù)組表示一個(gè)葉子結(jié)點(diǎn)的編碼。存儲(chǔ)定義：存儲(chǔ)定義：typedef char * Huffmancoden+1;char * cd;int start;例：例： 0 4 5 6 7 8 start cd: 0 1 1 0 0 4 hc 1 0 1 1 0 0 2 1 0 0 3 1 1 1 0 0 4 1 1 1 1 0 5 1 1 0 0 6 0 0 0 7 0 1 1 1 0 8 0 1 0 0 CrtHuffmanCode(Huffm

42、anTree ht,HuffmanCode hc,int n) /*從葉子到根，逆向求每個(gè)葉子對(duì)應(yīng)的哈夫曼編碼從葉子到根，逆向求每個(gè)葉子對(duì)應(yīng)的哈夫曼編碼*/ for(i=1;i=n;i+) /*求求每個(gè)每個(gè)葉子的哈夫曼編碼葉子的哈夫曼編碼*/ start=n-1; c=i ; p=hti.parent; while ( p!=0) -start; if(ht)p.Lchild = c) cdstart=0; /*左分支標(biāo)左分支標(biāo)0*/ else cdstart=1; /*右分支標(biāo)右分支標(biāo)1*/ c=p; p=htp.parent; hci=(char *)malloc(n-start)*sizeof(char); st