樹與二叉樹的關(guān)系

1、6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換樹、森林與二叉樹的相互轉(zhuǎn)換6.4.3 樹與森林的轉(zhuǎn)換樹與森林的轉(zhuǎn)換6.4 6.4 樹、森林和二叉樹的關(guān)系樹、森林和二叉樹的關(guān)系6.4.1 6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)樹的主要存儲方法有：樹的主要存儲方法有：一、雙親表示法一、雙親表示法二、孩子表示法二、孩子表示法三、孩子兄弟表示法三、孩子兄弟表示法一、一、 雙親表示法：雙親表示法： 用一組連續(xù)的空間來存儲樹中的結(jié)點(diǎn)，每個結(jié)點(diǎn)用一組連續(xù)的空間來存儲樹中的結(jié)點(diǎn)，每個結(jié)點(diǎn)附設(shè)一個指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)附設(shè)一個指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)

2、如下：點(diǎn)的結(jié)構(gòu)如下： 數(shù)據(jù)數(shù)據(jù) 雙親雙親dataparent1245637樹的雙親表示法如下圖：樹的雙親表示法如下圖：1615140302-11parentdata543210結(jié)點(diǎn)結(jié)點(diǎn)序號序號672雙親表示法的優(yōu)點(diǎn)：雙親表示法的優(yōu)點(diǎn)： 利用了樹中每個結(jié)點(diǎn)（根結(jié)點(diǎn)除外）利用了樹中每個結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個雙親結(jié)點(diǎn)的性質(zhì)，使得查找某只有一個雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。個結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。 雙親表示法的缺點(diǎn)：雙親表示法的缺點(diǎn)： 求某個結(jié)點(diǎn)的孩子時(shí)，需要遍歷整求某個結(jié)點(diǎn)的孩子時(shí)，需要遍歷整個表。個表。 #define max 100typedef struct tno

3、de datatype data; int parent; tnode; 一棵樹可以定義為：一棵樹可以定義為：typedef struct tnode treemax; int nodenum; /*結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)*/ parenttree; 雙親表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：雙親表示法的結(jié)點(diǎn)結(jié)構(gòu)定義：二、二、 孩子表示法：孩子表示法： 通常是把每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列通常是把每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個單鏈表，稱為孩子鏈表。起來，構(gòu)成一個單鏈表，稱為孩子鏈表。n n個結(jié)點(diǎn)共有個結(jié)點(diǎn)共有n n個孩子鏈表（葉結(jié)點(diǎn)的孩個孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表）。子鏈表為空表）。 n n個結(jié)點(diǎn)的數(shù)據(jù)和個結(jié)點(diǎn)的

4、數(shù)據(jù)和n n個孩子鏈表的頭個孩子鏈表的頭指針又組成一個順序表。指針又組成一個順序表。 樹的孩子鏈表表示法見樹的孩子鏈表表示法見p175的圖的圖6.26孩子表示法示意圖孩子表示法示意圖: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; childno

5、de; typedef struct /* 樹的定義樹的定義 */ datanode nodesmax; /* 順序表順序表 */ int root, num; /* 根結(jié)點(diǎn)指示及結(jié)點(diǎn)個數(shù)根結(jié)點(diǎn)指示及結(jié)點(diǎn)個數(shù) */ childtree; childtree; typedef struct /* 順序表結(jié)點(diǎn)的結(jié)構(gòu)定義順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 */datatype data; childnode * firstchild ; datanode;三、三、 孩子兄弟表示法孩子兄弟表示法 孩子兄弟表示法孩子兄弟表示法又稱又稱二叉鏈表表示法二叉鏈表表示法，表，表中每個結(jié)點(diǎn)設(shè)有兩個鏈域，分別指向該結(jié)點(diǎn)的中每個結(jié)

6、點(diǎn)設(shè)有兩個鏈域，分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和下一個兄弟（右兄弟）結(jié)點(diǎn)。第一個孩子結(jié)點(diǎn)和下一個兄弟（右兄弟）結(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 *fch, *nsib; 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)為右子樹右子樹對應(yīng)的關(guān)系：對應(yīng)的關(guān)系： 樹樹 二叉樹二叉樹 根根 根根 第一孩子第一孩子 左孩子左孩子 下一兄弟下一兄弟 右孩子右孩子一、一、 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹 約定樹中每一個結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到約定樹中每一個結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的次序順序編號，即把樹看作為有序樹。右的次序順序編號，即把樹看作為有序樹。 6.4.2 6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換樹、森林與二叉樹的相互轉(zhuǎn)換將一棵樹轉(zhuǎn)換為二叉樹的方法：將一

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

9、叉樹。）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2 2）第一棵二叉樹不動，從第二棵二叉樹開）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。得到的二叉樹。 二、森林轉(zhuǎn)換為二叉樹二、森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹示意圖森林轉(zhuǎn)換為二叉樹示意圖 b e ch d i f j g b c d e f gh i j森林轉(zhuǎn)換為二叉樹的實(shí)例另見森林轉(zhuǎn)換為二叉樹的實(shí)例另見p179的圖的

10、圖6.31遞歸方法描述森林轉(zhuǎn)換為二叉樹遞歸方法描述森林轉(zhuǎn)換為二叉樹: : 將森林將森林f f看作樹的有序集看作樹的有序集f=tf=t1 1，t t2 2，,t,tn n ，它對應(yīng)的二叉樹為它對應(yīng)的二叉樹為b b（f f）：）： （1 1）若）若n n0 0，則，則b b（f f）為空。）為空。 （2 2）若）若n0n0，則：，則： 二叉樹二叉樹b b（f f）的根為森林中第一棵樹）的根為森林中第一棵樹t t1 1的根；的根； b b（f f）的左子樹為）的左子樹為b b（tt1111，t t1m1m ），其），其中中tt1111，t t1m1m 是是t t1 1的子樹森林；的子樹森林； b b

11、（f f）的右子樹是）的右子樹是b b（t2t2，t tn n ）。）。 二叉樹轉(zhuǎn)換為樹或森林的方法為：二叉樹轉(zhuǎn)換為樹或森林的方法為：（1 1）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、點(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）整理由（）整理由（1 1）、（）、（2 2）兩步所得到的樹或）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。森林，使之結(jié)構(gòu)層次分明。 三、二叉樹轉(zhuǎn)換為樹或

12、森林三、二叉樹轉(zhuǎn)換為樹或森林 二叉樹轉(zhuǎn)換為森林的示意圖二叉樹轉(zhuǎn)換為森林的示意圖dabcefghijdabcefghijhijgdabcef 若若b b是一棵二叉樹，是一棵二叉樹，t t是是b b的根結(jié)點(diǎn)，的根結(jié)點(diǎn)，l l是是b b的的左子樹，左子樹，r r為為b b的右子樹，設(shè)的右子樹，設(shè)b b對應(yīng)的森林對應(yīng)的森林f f（b b）中含有的中含有的n n棵樹為棵樹為t t1 1,t,t2 2, , ,t,tn n，則有：，則有： （1 1）b b為空，則：為空，則：f f（b b）為空的森林（）為空的森林（n n0 0）。）。 （2 2）b b非空，則：非空，則： f f（b b）中第一棵樹）中

13、第一棵樹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)換用遞歸的方法描述其轉(zhuǎn)換6.4.3 6.4.3 樹與森林的遍歷樹與森林的遍歷一、一、 樹的遍歷樹的遍歷樹的遍歷主要有以下兩種：樹的遍歷主要有以下兩種： 先根遍歷先根遍歷 后

14、根遍歷后根遍歷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)的每一棵子樹?？米訕?。（2 2）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。abecdfgh如圖樹的后根遍歷序列為：如圖樹的后根遍歷序列為： ebhfgcda。2 2、后根遍歷、后根遍歷 a b

15、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對應(yīng)二叉樹的先序遍歷對應(yīng)二叉樹的先序遍歷 對應(yīng)二叉樹的中序遍歷對應(yīng)二叉樹的中序遍歷 二、樹的遍歷算法二、樹的遍歷算法 先根遍歷方法一先根遍歷方法一void rootfirst(cstree root) if (root!=null) visit(root -data); /* 訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) */ p= root- fch; while (p!=null) rootfirst( p ); /*

16、 訪問以訪問以p為根的子樹為根的子樹 */ p = p - nsib; 先根遍歷方法二先根遍歷方法二 void rootfirst(cstree root) if (root!=null) visit (root -data); /*訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)*/ rootfirst (root-fch); /*先根遍歷首子樹先根遍歷首子樹*/ rootfirst (root-nsib); /*先根遍歷兄弟樹先根遍歷兄弟樹*/ 三、森林的遍歷三、森林的遍歷森林的遍歷方法主要有以下三種：森林的遍歷方法主要有以下三種：先序遍歷先序遍歷 中序遍歷中序遍歷 * *后序遍歷后序遍歷1 1、先序遍歷、先序遍歷若

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

18、的根結(jié)點(diǎn)。 （3 3）中序遍歷除去第一棵樹之后剩余的樹）中序遍歷除去第一棵樹之后剩余的樹 構(gòu)成的森林。構(gòu)成的森林。 2 2、中序遍歷、中序遍歷即：依次從左至右對森林中的每一棵樹進(jìn)行即：依次從左至右對森林中的每一棵樹進(jìn)行 后根遍歷后根遍歷。 先序遍歷先序遍歷森林時(shí)頂點(diǎn)時(shí)頂點(diǎn)的訪問次序：的訪問次序：a b c d e f g h i j 中序遍歷中序遍歷森林時(shí)頂點(diǎn)時(shí)頂點(diǎ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 樹和森林的遍歷和二叉樹和森林的遍歷和二叉樹遍歷的對應(yīng)關(guān)系樹遍歷的對應(yīng)關(guān)系 ？先根遍歷先根遍歷

19、后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷3 3、森林的后序遍歷、森林的后序遍歷* *若森林非空，則遍歷方法為：若森林非空，則遍歷方法為：（1 1）后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子）后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。樹森林。 （2 2）后序遍歷除去第一棵樹之后剩余的樹構(gòu)）后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。成的森林。 （3 3）訪問第一棵樹的根結(jié)點(diǎn)。）訪問第一棵樹的根結(jié)點(diǎn)。 6.5 6.5 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用6.5.1 6.5.1 哈夫曼樹哈夫曼樹 哈夫曼樹最典型、最廣泛的應(yīng)用是在哈夫曼樹最典型、最廣

20、泛的應(yīng)用是在編碼技術(shù)上，利用哈夫曼樹，可以得到編碼技術(shù)上，利用哈夫曼樹，可以得到平均長度最短的編碼。這在通訊領(lǐng)域是平均長度最短的編碼。這在通訊領(lǐng)域是極其有價(jià)值的。極其有價(jià)值的。 計(jì)算機(jī)程序操作碼的優(yōu)化也可以利用計(jì)算機(jī)程序操作碼的優(yōu)化也可以利用哈夫曼樹實(shí)現(xiàn)。哈夫曼樹實(shí)現(xiàn)。路徑：路徑：從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支 序列。序列。路徑長度：路徑長度：從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)所經(jīng)過從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)所經(jīng)過 的分支條數(shù)。的分支條數(shù)。樹的路徑長度：樹的路徑長度：樹中每個結(jié)點(diǎn)與根之間的路徑樹中每個結(jié)點(diǎn)與根之間的路徑 長度之和長度之和（pl）。a例：例：pl(a)=1+1+

21、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)路徑長度之和，稱為樹的帶權(quán)路徑長度，通常路徑長度之和，稱為樹的帶權(quán)路徑長度，通常記為記為wpl：wpl= wilii=1n其中：其中：n n為葉子結(jié)點(diǎn)的個數(shù)；為葉子結(jié)點(diǎn)的個數(shù)；w wi i為第為第i i個葉子的權(quán)值；個葉

22、子的權(quán)值； l li i為第為第i i個葉子結(jié)點(diǎn)的路徑長度。個葉子結(jié)點(diǎn)的路徑長度。結(jié)點(diǎn)的權(quán)：結(jié)點(diǎn)的權(quán)：給樹中每個結(jié)點(diǎn)賦予一個具有實(shí)際意給樹中每個結(jié)點(diǎn)賦予一個具有實(shí)際意義的數(shù)值，我們稱該數(shù)值為這個結(jié)點(diǎn)的權(quán)。義的數(shù)值，我們稱該數(shù)值為這個結(jié)點(diǎn)的權(quán)。例如下圖所示的三棵二叉樹例如下圖所示的三棵二叉樹wpl(a)=7252224236其帶權(quán)路徑長度分別為：其帶權(quán)路徑長度分別為：2457a75 4b25 42c7wpl(b)=4273532146wpl(c)=7152234335 什么樣的樹的帶權(quán)路徑長度什么樣的樹的帶權(quán)路徑長度wpl最??？最小？ 例如：給定一個權(quán)值序列例如：給定一個權(quán)值序列2, 4, 5,

23、 7，可構(gòu)造，可構(gòu)造多種二叉樹的形態(tài)多種二叉樹的形態(tài):問題問題2 2：2457a75 4b25 42c7 wpl(a) 36 wpl(b) 46 wpl(c)35 其帶權(quán)路徑長度分別為：其帶權(quán)路徑長度分別為： 在各種形態(tài)的含有在各種形態(tài)的含有 n個葉子結(jié)點(diǎn)的個葉子結(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個葉子結(jié)點(diǎn)的最優(yōu)二個葉子結(jié)點(diǎn)的最優(yōu)二叉樹的總結(jié)點(diǎn)數(shù)

24、為叉樹的總結(jié)點(diǎn)數(shù)為 2* *n- -1 (依據(jù)二叉樹性質(zhì)三依據(jù)二叉樹性質(zhì)三)。 最優(yōu)二叉樹的構(gòu)造方法最早由哈夫曼最優(yōu)二叉樹的構(gòu)造方法最早由哈夫曼研究，所以又稱為研究，所以又稱為“哈夫曼樹哈夫曼樹”。二、哈夫曼樹的構(gòu)造二、哈夫曼樹的構(gòu)造 (1) 根據(jù)給定的根據(jù)給定的 n 個權(quán)值個權(quán)值 w1, w2, , wn ,構(gòu)造構(gòu)造 n 棵二叉樹的集合棵二叉樹的集合 f = t1, t2, , tn， 其中每棵二叉樹中均只含一個帶權(quán)值為其中每棵二叉樹中均只含一個帶權(quán)值為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹；的根結(jié)點(diǎn)，其左、右子樹為空樹；構(gòu)造哈夫曼樹的方法：構(gòu)造哈夫曼樹的方法： 在在 f 中選取其根結(jié)點(diǎn)的權(quán)值

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

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

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

28、個元素存儲哈夫曼樹的根結(jié)點(diǎn)。 2、哈夫曼算法、哈夫曼算法 初始化：先將初始化：先將n個元素都視為根結(jié)點(diǎn)，個元素都視為根結(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存放已知的存放已知的n個

29、權(quán)值，構(gòu)造哈夫曼樹個權(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)* */ / hts1.parent=i;hts2.parent=i; hti.lchild=s1;ht i.rchild=s2; ht i.weight=ht s1.weight+ht s2.weight; 例給定權(quán)值

30、例給定權(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+) h

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

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

33、予中每個左分支賦予0 0，右分支，右分支賦予賦予1 1，則從根到每個葉子的路徑上，各分支，則從根到每個葉子的路徑上，各分支的值構(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編碼編碼:左

34、分支左分支:0右分支右分支: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( (字符不同字符不同) )，則對應(yīng)的樹葉不同，則對應(yīng)的樹葉不同，因?yàn)閺母矫總€葉子的路徑是不同的，所以一因

35、為從根到每個葉子的路徑是不同的，所以一條路徑不可能是另一條路徑的前部（前綴），條路徑不可能是另一條路徑的前部（前綴），因此哈夫曼編碼是前綴碼。因此哈夫曼編碼是前綴碼。 用字符出現(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è)有一臺模型機(jī)，共有設(shè)有一臺模型機(jī)，共有7 7種不同的指

36、令，種不同的指令，各指令的使用頻率各指令的使用頻率pi為：為：指指 令令i1i2i3i4i5i6i7 使用頻率使用頻率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 =

37、 2.20ni=1若用等長編碼，其平均碼長為若用等長編碼，其平均碼長為3。 指令指令i1i2i3i4i5i6i7編碼編碼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í)，完成一個葉子結(jié)點(diǎn)編碼的求取。

38、個葉子結(jié)點(diǎn)編碼的求取。 由哈夫曼樹生成編碼時(shí)由哈夫曼樹生成編碼時(shí), 編碼存儲在多個字編碼存儲在多個字符數(shù)組中符數(shù)組中, 每個數(shù)組表示一個葉子結(jié)點(diǎn)的編碼。每個數(shù)組表示一個葉子結(jié)點(diǎn)的編碼。存儲定義：存儲定義：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) /*從葉子到根，逆向求每個葉子對應(yīng)的哈夫曼編碼從葉子到根，逆向求每個葉子對應(yīng)的哈夫曼編碼*/ for(i=1;ilchild, b2-lchild); like2=like(b1-rchild, b2-rchild); return (like1 & like2); 1、二叉