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

1、6.6.1 樹的存儲(chǔ)樹的存儲(chǔ)6.6.2 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換6.6.3 樹和森林的遍歷樹和森林的遍歷6.6 6.6 樹和森林樹和森林6.6.1 6.6.1 樹的存儲(chǔ)樹的存儲(chǔ)樹的主要存儲(chǔ)方法有：樹的主要存儲(chǔ)方法有：一、雙親表示法一、雙親表示法二、孩子表示法二、孩子表示法三、孩子兄弟表示法三、孩子兄弟表示法一、一、 雙親表示法：雙親表示法： 用一組連續(xù)的空間來存儲(chǔ)樹中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)用一組連續(xù)的空間來存儲(chǔ)樹中的結(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樹的雙親表示法如下圖：樹的雙親表示法如下圖：1615140302-11ParentData543210結(jié)點(diǎn)結(jié)點(diǎn)序號(hào)序號(hào)673雙親表示法的優(yōu)點(diǎn)：雙親表示法的優(yōu)點(diǎn)： 利用了樹中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）利用了樹中每個(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; 一棵樹可以定義為：一棵樹可以定義為：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)排列起來，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。起來，構(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è)順序表。 樹的孩子鏈表表示法見樹的孩子鏈表表示法見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 /* 樹的定

5、義樹的定義 */ 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í)現(xiàn)樹的各種操作；

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

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

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

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

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

12、樹）的根為森林中第一棵樹T T1 1的根；的根； B B（F F）的左子樹為）的左子樹為B B（TT1111，T T1m1m ），其），其中中TT1111，T T1m1m 是是T T1 1的子樹森林；的子樹森林； B B（F F）的右子樹是）的右子樹是B B（T2T2，T TN N ）。）。 若若B B是一棵二叉樹，是一棵二叉樹，T T是是B B的根結(jié)點(diǎn)，的根結(jié)點(diǎn)，L L是是B B的的左子樹，左子樹，R R為為B B的右子樹，設(shè)的右子樹，設(shè)B B對(duì)應(yīng)的森林對(duì)應(yīng)的森林F F（B B）中含有的中含有的n n棵樹為棵樹為T 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）中第一棵樹）中第一棵樹T T1 1的根為二叉樹的根為二叉樹B B的根的根T T； T T1 1中根結(jié)點(diǎn)的子樹森林由中根結(jié)點(diǎn)的子樹森林由B B的左子樹的左子樹L L轉(zhuǎn)換而轉(zhuǎn)換而成，即成，即F F（L L）=T=T1111,T,T1m1m ； B B的右子樹的右子樹R R轉(zhuǎn)換為轉(zhuǎn)換為F F（B B）中其余樹組成的森）中其余樹組成的森林，即林，即F(R)F(R) T T2 2, T, T3 3, ,T, ,Tn n 。 五、用遞歸的方法描述其轉(zhuǎn)換五、用遞歸的方法

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

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

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

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

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

19、訪問次序：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 樹和森林的遍歷和二叉樹和森林的遍歷和二叉樹遍歷的對(duì)應(yīng)關(guān)系樹遍歷的對(duì)應(yīng)關(guān)系 ？先根遍歷先根遍歷后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷3 3、森林的后序遍歷、森林的后序遍歷* *若森林非空，則遍歷方法為：若森林非空，則遍歷方法為：（1 1）后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子）后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。樹森林。 （2 2）后序遍歷除去第一棵樹之后剩余的樹構(gòu)）后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的

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

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

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

23、57a75 4b25 42c7WPL(b)=4273532146WPL(c)=7152234335 問題問題1 1：什么樣的二叉樹的路徑長度什么樣的二叉樹的路徑長度PLPL最小？最??？分析：分析：二叉樹中路徑長度為二叉樹中路徑長度為0 0的結(jié)點(diǎn)只有的結(jié)點(diǎn)只有1 1個(gè)；個(gè)； 路徑長度路徑長度 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)的路徑長度為對(duì)應(yīng)的路徑長度為 log2n 路徑長度為路徑長度為1 1的結(jié)點(diǎn)至多只有的結(jié)點(diǎn)

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

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

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

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

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

29、, 9, 7 9562752769767139527構(gòu)造哈夫曼樹如下：構(gòu)造哈夫曼樹如下：952716671329三、哈夫曼算法的實(shí)現(xiàn)三、哈夫曼算法的實(shí)現(xiàn) n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),因此可用有因此可用有2n-1個(gè)元素的個(gè)元素的數(shù)組數(shù)組來存儲(chǔ)哈夫曼樹來存儲(chǔ)哈夫曼樹, 結(jié)點(diǎn)間的結(jié)點(diǎn)間的關(guān)系用游標(biāo)表示關(guān)系用游標(biāo)表示，即采用，即采用靜態(tài)鏈表靜態(tài)鏈表來來存儲(chǔ)哈夫曼樹。存儲(chǔ)哈夫曼樹。 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ǔ)哈夫曼樹的根

31、結(jié)點(diǎn)。最后一個(gè)元素存儲(chǔ)哈夫曼樹的根結(jié)點(diǎn)。 2、哈夫曼算法、哈夫曼算法 初始化：先將初始化：先將n個(gè)元素都視為根結(jié)點(diǎn)，個(gè)元素都視為根結(jié)點(diǎn)，即孩子和雙親指針全置即孩子和雙親指針全置0。 建哈夫曼樹的過程是：反復(fù)在數(shù)組中建哈夫曼樹的過程是：反復(fù)在數(shù)組中選雙親為選雙親為0(表示它們當(dāng)前是樹根表示它們當(dāng)前是樹根)且權(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)造哈夫曼樹個(gè)權(quán)值，構(gòu)造哈夫曼樹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; 例給定權(quán)值例給定權(quán)

33、值: 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+) hti=w

34、i,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; 哈夫曼樹最典型的應(yīng)用是在編碼，利用哈哈夫曼樹最典型的應(yīng)用是在編碼，利用哈夫曼樹，可以得到平均長度最短的編碼。夫曼樹，可以得到平均長度最短的編碼。6.7.2 6.7.2 哈夫曼編碼哈夫曼編碼 平均長度最短的編碼一般為不等長編碼，平均長度最短的編碼一

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

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

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

38、的，所以一條路徑不可能是另一條路徑的前部（前綴），條路徑不可能是另一條路徑的前部（前綴），因此哈夫曼編碼是前綴碼。因此哈夫曼編碼是前綴碼。 用字符出現(xiàn)的頻率用字符出現(xiàn)的頻率( (Pi) )為權(quán)值構(gòu)造哈夫曼為權(quán)值構(gòu)造哈夫曼樹樹, ,并以此來構(gòu)造字符的哈夫曼編碼，由于哈并以此來構(gòu)造字符的哈夫曼編碼，由于哈夫曼樹的夫曼樹的WPLWPL最?。鹤钚。核詡鬏?shù)膱?bào)文長度：所以傳輸?shù)膱?bào)文長度： 必定最小。必定最小。 WPL= wilii=1n報(bào)文長報(bào)文長= 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 哈夫曼樹最典型、最廣泛的應(yīng)用是在編碼哈夫曼樹最典型、最廣泛的應(yīng)用是在編碼技術(shù)上，而操作碼的優(yōu)化也是其應(yīng)用之一。技術(shù)上，而操作碼的優(yōu)化也是其應(yīng)用之一。 以指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹，以指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹，并求各指令的哈夫曼編碼。并求各指令的哈夫曼編碼。則指令的平均碼長為：則指令的平均碼長為：pili =0.4*7+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5 = 2.20ni=1若用等長編

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

41、夫曼樹生成編碼時(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(HuffmanTree 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