方案一二叉樹(shù)的建立和遍歷

1、1具體內(nèi)容：先生成一棵二叉樹(shù)，再用中序遍歷方式打印每個(gè)具體內(nèi)容：先生成一棵二叉樹(shù)，再用中序遍歷方式打印每個(gè)結(jié)點(diǎn)值，并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個(gè)數(shù)結(jié)點(diǎn)值，并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個(gè)數(shù)。具體內(nèi)容：先生成一棵哈夫曼樹(shù)，再打印各字符對(duì)應(yīng)的哈夫具體內(nèi)容：先生成一棵哈夫曼樹(shù)，再打印各字符對(duì)應(yīng)的哈夫曼編碼。曼編碼。具體內(nèi)容：參見(jiàn)嚴(yán)題集具體內(nèi)容：參見(jiàn)嚴(yán)題集P149 實(shí)習(xí)實(shí)習(xí)5.2要求，或參見(jiàn)自測(cè)卷要求，或參見(jiàn)自測(cè)卷（三個(gè)方案由易到難，可自選，參見(jiàn)自測(cè)題集（三個(gè)方案由易到難，可自選，參見(jiàn)自測(cè)題集實(shí)驗(yàn)二實(shí)驗(yàn)二資料）資料）2喻信課堂網(wǎng)址：喻信課堂網(wǎng)址：8:8000/海豚之家網(wǎng)址：海豚之家網(wǎng)址：

2、3第第6 6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)（Tree & Binary Tree）6.1 樹(shù)的基本概念樹(shù)的基本概念6.2 二叉樹(shù)二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林6.5 Huffman樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用4先介紹二叉樹(shù)的典型應(yīng)用先介紹二叉樹(shù)的典型應(yīng)用平衡樹(shù)平衡樹(shù)排序樹(shù)排序樹(shù)字典樹(shù)字典樹(shù)判定樹(shù)判定樹(shù)帶權(quán)樹(shù)帶權(quán)樹(shù)最優(yōu)樹(shù)最優(yōu)樹(shù)由字符串構(gòu)成的二叉排序樹(shù)由字符串構(gòu)成的二叉排序樹(shù)特點(diǎn)特點(diǎn)：分支查找樹(shù)（例如：分支查找樹(shù)（例如1212個(gè)球如何只稱個(gè)球如何只稱3 3次次便分出輕重）便分出輕重）特點(diǎn)特點(diǎn)：路徑帶權(quán)值（例如長(zhǎng)度）：路徑帶權(quán)值（例如長(zhǎng)度）是帶權(quán)路徑長(zhǎng)

3、度最短的樹(shù)，又稱是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，又稱 HuffmanHuffman樹(shù)，樹(shù)，用途之一是通信中的壓縮編碼。用途之一是通信中的壓縮編碼。特點(diǎn)特點(diǎn)：所有結(jié)點(diǎn)左右子樹(shù)深度差：所有結(jié)點(diǎn)左右子樹(shù)深度差11特點(diǎn)特點(diǎn)：所有結(jié)點(diǎn)：所有結(jié)點(diǎn)“左小右大左小右大”5什么是平衡二叉樹(shù)什么是平衡二叉樹(shù)（ 又稱又稱AVL AVL 樹(shù)）樹(shù)）？性質(zhì)：性質(zhì)： 所有所有結(jié)點(diǎn)左、右子樹(shù)深度之差的絕對(duì)值結(jié)點(diǎn)左、右子樹(shù)深度之差的絕對(duì)值 1若定義結(jié)點(diǎn)的若定義結(jié)點(diǎn)的“平衡因子平衡因子” BF = 左子樹(shù)深度左子樹(shù)深度 右子樹(shù)深度右子樹(shù)深度則：平衡二叉樹(shù)中所有結(jié)點(diǎn)的則：平衡二叉樹(shù)中所有結(jié)點(diǎn)的BF -1, 0, 1 (a) (a) 平衡樹(shù)

4、平衡樹(shù) (b) (b) 不平衡樹(shù)不平衡樹(shù)例：判斷下列二叉樹(shù)是否例：判斷下列二叉樹(shù)是否AVL樹(shù)？樹(shù)？0001 11 1-1-10001-16什么是二叉排序樹(shù)？什么是二叉排序樹(shù)？（a）（b）例：例：下列下列2種圖形中，哪個(gè)不是二叉排序樹(shù)種圖形中，哪個(gè)不是二叉排序樹(shù) ？-或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)：或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)： （1 1）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值；）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值； （2 2）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值；）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值； （3 3）它的左右子樹(shù)也分別為二叉排序樹(shù)。）它的左右子樹(shù)也分別為二叉排序樹(shù)。想一想：對(duì)它中序

5、遍歷之后是什么效果？想一想：對(duì)它中序遍歷之后是什么效果？74110102 26539810216473987什么是判定樹(shù)？什么是判定樹(shù)？ 舉例：舉例： 1212個(gè)球如何用天平只稱個(gè)球如何用天平只稱3 3次便分出輕重？次便分出輕重？分析：分析：1212個(gè)球中必有一個(gè)非輕即重，即共有個(gè)球中必有一個(gè)非輕即重，即共有2424種種“次品次品”的可能性。的可能性。每次天平稱重的結(jié)果有每次天平稱重的結(jié)果有3 3種，連稱種，連稱3 3次應(yīng)該得到的結(jié)果有次應(yīng)該得到的結(jié)果有3 33 3=27=27種。種。說(shuō)明僅用說(shuō)明僅用3 3次就能找出次品的可能性是存在的。次就能找出次品的可能性是存在的。思路：思路：首先，將首先

6、，將1212個(gè)球分三組，每組個(gè)球分三組，每組4 4個(gè)，任意取兩組稱。會(huì)有兩種情個(gè)，任意取兩組稱。會(huì)有兩種情況：平衡，或不平衡。況：平衡，或不平衡。 其次，一定要利用已經(jīng)稱過(guò)的那些結(jié)論；即充分利用其次，一定要利用已經(jīng)稱過(guò)的那些結(jié)論；即充分利用“舊球舊球”的的標(biāo)準(zhǔn)性作為參考。標(biāo)準(zhǔn)性作為參考。8第第1 1次次: :等分等分3 3組組 第第2 2次次: :3 3舊舊3 3新新第第3 3次次: :1 1舊舊1 1新新 相等相等= =小于小于 (11)(11) 大于大于 相等相等= =小于小于 小于小于 小于小于 相等相等= =(12)(12)小于小于 (12)(12)輕輕大于大于 小于小于 小于小于 小

7、于小于 相等相等= =重重重重重重9什么是帶權(quán)樹(shù)？什么是帶權(quán)樹(shù)？abdc7524即路徑帶有權(quán)值。例如：即路徑帶有權(quán)值。例如：106.5 Huffman6.5 Huffman樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用一、一、HuffmanHuffman樹(shù)樹(shù)二、二、HuffmanHuffman編碼編碼最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)HuffmanHuffman樹(shù)樹(shù)HuffmanHuffman編碼編碼帶權(quán)路徑帶權(quán)路徑長(zhǎng)度最短長(zhǎng)度最短的樹(shù)的樹(shù)不等長(zhǎng)編碼不等長(zhǎng)編碼是通信是通信中最經(jīng)中最經(jīng)典的壓典的壓縮編碼縮編碼11一、一、 HuffmanHuffman樹(shù)樹(shù)（最優(yōu)二叉樹(shù)）（最優(yōu)二叉樹(shù)）路路 徑徑：路徑長(zhǎng)度路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度

8、：帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度：HuffmanHuffman樹(shù)樹(shù)：由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。路徑上的分支數(shù)目。從樹(shù)根到從樹(shù)根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。的路徑長(zhǎng)度之和。結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積（結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積（WPLWPL）若干術(shù)語(yǔ)：若干術(shù)語(yǔ)：debacf g即樹(shù)中所有即樹(shù)中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和的帶權(quán)路徑長(zhǎng)度之和帶權(quán)路徑長(zhǎng)度最小的樹(shù)。帶權(quán)路徑長(zhǎng)度最小的樹(shù)。例如：例如：aeae的路徑長(zhǎng)度的路徑長(zhǎng)度樹(shù)長(zhǎng)度樹(shù)長(zhǎng)度2 21010HuffmanHuffman常譯

9、為常譯為赫夫曼、霍夫曼、哈夫曼等赫夫曼、霍夫曼、哈夫曼等Weighted Path LengthWeighted Path Length12樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？如何計(jì)算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：經(jīng)典之例：WPL=WPL=WPL=Huffman樹(shù)是樹(shù)是WPL WPL 最小的樹(shù)最小的樹(shù)樹(shù)中所有葉子結(jié)樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和度之和364635131. 1. 構(gòu)造構(gòu)造HuffmanHuffman樹(shù)的基本思想：樹(shù)的基本思想：設(shè)有設(shè)有4 4個(gè)字

10、符個(gè)字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4， 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長(zhǎng)編碼等長(zhǎng)編碼（如二進(jìn)制編碼）（如二進(jìn)制編碼）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，則：，則：WPLWPL1 12bit2bit(7(75 52 24 4）3636法法2 2：不等長(zhǎng)編碼不等長(zhǎng)編碼（如（如HuffmanHuffman編碼）編碼）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，則：，則：明確：要實(shí)

11、現(xiàn)明確：要實(shí)現(xiàn)HuffmanHuffman編碼，就要先構(gòu)造編碼，就要先構(gòu)造HuffmanHuffman樹(shù)樹(shù)討論：討論：HuffmanHuffman樹(shù)有什么用？樹(shù)有什么用？權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。WPLWPL最小的樹(shù)最小的樹(shù)頻度高的信息頻度高的信息用短碼，反之用短碼，反之用長(zhǎng)碼，傳輸用長(zhǎng)碼，傳輸效率肯定高！效率肯定高！WPLWPL2 2= =1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535最小冗余編碼、信息高效傳輸最小冗余編碼、信息高效傳輸142. 2. 構(gòu)造構(gòu)造HuffmanHuffm

12、an樹(shù)的步驟（即樹(shù)的步驟（即HuffmanHuffman算法）：算法）：怎樣證明它就是怎樣證明它就是WPL最小的最優(yōu)二叉樹(shù)？最小的最優(yōu)二叉樹(shù)？參考參考信源編碼信源編碼Huffman樹(shù)的特點(diǎn)：沒(méi)有度為樹(shù)的特點(diǎn)：沒(méi)有度為1的結(jié)點(diǎn)。的結(jié)點(diǎn)。15step1step1：在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是合并中，總是合并當(dāng)前值最小當(dāng)前值最小的兩個(gè)權(quán)的兩個(gè)權(quán)具體操作步驟：具體操作步驟：a. 初始初始方框表示外結(jié)點(diǎn)（葉子，字符）方框表示外結(jié)點(diǎn)（葉子，字符）圓框表示內(nèi)結(jié)點(diǎn)圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）（合并后的權(quán)值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 1116step

13、2step2：d da ai in n1 11 11 10 00 00 0HuffmanHuffman編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=WPL=1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535（小于等長(zhǎng)碼的（小于等長(zhǎng)碼的WPL=36WPL=36）HuffmanHuffman編碼也稱為編碼也稱為HuffmanHuffman樹(shù)樹(shù) 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤17二、二、HuffmanHuffman編碼編碼（1 1）由于由于Huffman樹(shù)的樹(shù)

14、的WPLWPL最小，最小，說(shuō)明編碼所說(shuō)明編碼所需要的需要的比特?cái)?shù)最少比特?cái)?shù)最少。（4） Huffman編碼時(shí)是從葉子走到根；而譯碼時(shí)又要從根走編碼時(shí)是從葉子走到根；而譯碼時(shí)又要從根走到葉子，因此每個(gè)結(jié)點(diǎn)需要增開(kāi)到葉子，因此每個(gè)結(jié)點(diǎn)需要增開(kāi)雙親雙親指針?lè)至浚ㄟB同結(jié)點(diǎn)指針?lè)至浚ㄟB同結(jié)點(diǎn)權(quán)值權(quán)值共要開(kāi)共要開(kāi)5個(gè)分量）個(gè)分量）（5）用計(jì)算機(jī)實(shí)現(xiàn)時(shí)，順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)都要用到。用計(jì)算機(jī)實(shí)現(xiàn)時(shí)，順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)都要用到。分析分析Huffman樹(shù)和編碼的特點(diǎn)：樹(shù)和編碼的特點(diǎn)：霍夫曼霍夫曼編碼的基本思想是編碼的基本思想是出現(xiàn)概率大的信息用短碼，概率小的用長(zhǎng)碼出現(xiàn)概率大的信息用短碼，概率小的用長(zhǎng)碼,

15、,最小冗余最小冗余這種編碼已廣泛應(yīng)這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。用于網(wǎng)絡(luò)通信中。（2） Huffman樹(shù)樹(shù)肯定沒(méi)有度為肯定沒(méi)有度為1的結(jié)點(diǎn)；的結(jié)點(diǎn)；（3）一棵有一棵有n 0個(gè)葉子結(jié)點(diǎn)的個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)，共有樹(shù)，共有2n0-1個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)；（因?yàn)椋ㄒ驗(yàn)閚=n0+n1+n2=2n0-1)18如何編程實(shí)現(xiàn)如何編程實(shí)現(xiàn)HuffmanHuffman編碼？編碼？建議建議1 1：HuffmanHuffman樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)可設(shè)計(jì)成5 5分量形式：分量形式：charweightparentlchildrchild將整個(gè)將整個(gè)HuffmanHuffman樹(shù)的樹(shù)的結(jié)點(diǎn)結(jié)點(diǎn)存儲(chǔ)在

16、一個(gè)數(shù)組存儲(chǔ)在一個(gè)數(shù)組HTHT1.n.m1.n.m中中; ; 各葉子結(jié)點(diǎn)的各葉子結(jié)點(diǎn)的編碼編碼存儲(chǔ)在另一存儲(chǔ)在另一“復(fù)合復(fù)合”數(shù)組數(shù)組HCHC1.n1.n中。中。 請(qǐng)參見(jiàn)教材請(qǐng)參見(jiàn)教材P149P149圖圖6.276.27的（的（a)a)和（和（c)c)建議建議2 2： HuffmanHuffman樹(shù)的樹(shù)的存儲(chǔ)結(jié)構(gòu)可采用存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)：結(jié)構(gòu)：(1)(1)教材教材P147P147149149內(nèi)容；內(nèi)容；(2)(2)嚴(yán)蔚敏嚴(yán)蔚敏“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”演示程序演示程序；(3)(3)習(xí)題集習(xí)題集P149 P149 實(shí)習(xí)實(shí)習(xí)5.25.2要求；要求；(4)(4)自測(cè)卷第自測(cè)卷第6 6章上機(jī)

17、方案二的源程序。章上機(jī)方案二的源程序。19typedef structunsigned int weight；/權(quán)值分量（可放大取整）權(quán)值分量（可放大取整）unsigned int parent，lchild，rchild； /雙親和孩子分量雙親和孩子分量HTNode，*HuffmanTree；/用動(dòng)態(tài)數(shù)組存儲(chǔ)用動(dòng)態(tài)數(shù)組存儲(chǔ)Huffman樹(shù)樹(shù)typedef char*HuffmanCode； /動(dòng)態(tài)數(shù)組存儲(chǔ)動(dòng)態(tài)數(shù)組存儲(chǔ)Huffman編碼表編碼表Huffman樹(shù)和樹(shù)和Huffman樹(shù)編碼的存儲(chǔ)表示：樹(shù)編碼的存儲(chǔ)表示：000r0920019007lpw321雙親雙親* *HuffmanTreeHu

18、ffmanTree或或 HTHT向量向量HT3.parent=9HT3.parent=9指針型指針指針型指針20如何編程實(shí)現(xiàn)如何編程實(shí)現(xiàn)HuffmanHuffman編碼？編碼？參見(jiàn)教材參見(jiàn)教材P147先構(gòu)造先構(gòu)造Huffman樹(shù)樹(shù)HT， 再求出再求出N個(gè)字符的個(gè)字符的Huffman編碼編碼HC。Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)if (n=1)return;m=2*n-1; /n 0個(gè)葉子的個(gè)葉子的HuffmanTree共有共有2n0-1個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)；HT=(HuffmanTr

19、ee)malloc(m+1)*sizeof(HTNode); /0單元未用單元未用*w存放存放n個(gè)字符的權(quán)值個(gè)字符的權(quán)值for(p=HT,i=1; i=n; +i,+p,+w)*p=*w,0,0,0; /給前給前n0個(gè)單元個(gè)單元初始化初始化for(；i=m; +i,+p)*p =0,0,0,0; /對(duì)葉子之后的存儲(chǔ)單元清零對(duì)葉子之后的存儲(chǔ)單元清零for(i=n+1;i=m; +i) /建建Huffman樹(shù)樹(shù)(從從葉子后開(kāi)始存內(nèi)結(jié)點(diǎn)葉子后開(kāi)始存內(nèi)結(jié)點(diǎn)) Select(HT, i-1, s1, s2); /在在HT1i-1選擇選擇parent為為0且且weight最小最小的的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為

20、兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為S1和和s2（教材未給出此函數(shù)源碼）教材未給出此函數(shù)源碼）HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+ HTs2.weight;21(續(xù)前續(xù)前)再求出再求出n個(gè)字符的個(gè)字符的Huffman編碼編碼HCHC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配分配n個(gè)字符個(gè)字符編碼的頭指針向量（一維數(shù)組）編碼的頭指針向量（一維數(shù)組）cd=(char*) malloc(n*sizeof(char); /分配求編碼的工作空間

21、分配求編碼的工作空間(n) cdn-1=“0”; /編碼結(jié)束符（從編碼結(jié)束符（從cd0cdn-1為合法空間）為合法空間）for(i=1;i=n;+i) /逐個(gè)字符求逐個(gè)字符求Huffman編碼編碼 start=n-1; /編碼結(jié)束符位置編碼結(jié)束符位置 for(c=i,f=HTi.parent; f!=0; c=f, f=HTf.parent)/從葉子到從葉子到根逆向求編碼根逆向求編碼if(HTf.lchild=c) cd-start=“0”;else cd-start=“1”;HCi=(char*)malloc(n-start)*sizeof(char);/為第為第i個(gè)字個(gè)字符編碼分配空間符編

22、碼分配空間strcpy(HCi,&cdstart); /從從cd復(fù)制編碼串到復(fù)制編碼串到HCfree(cd); /釋放工作空間釋放工作空間/HuffmanCoding22HuffmanHuffman編碼舉例編碼舉例解：解：先將概率先將概率放大放大100100倍倍，以方便構(gòu)造哈夫曼樹(shù)。，以方便構(gòu)造哈夫曼樹(shù)。放大后的權(quán)值集合放大后的權(quán)值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 ，按哈夫曼樹(shù)構(gòu)造規(guī)則按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除、替換）（合并、刪除、替換），可得到哈夫曼樹(shù)。，可得到哈夫曼樹(shù)。例例1【嚴(yán)題集【嚴(yán)

23、題集6.26】：假設(shè)用于通信的電文僅由：假設(shè)用于通信的電文僅由8個(gè)字母?jìng)€(gè)字母 a, b, c, d, e, f, g, h 構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，試為這，試為這8個(gè)字母設(shè)計(jì)哈夫曼個(gè)字母設(shè)計(jì)哈夫曼編編碼。如果用碼。如果用07的二進(jìn)制編碼方案又如何？的二進(jìn)制編碼方案又如何？ 【類同【類同P148例例2】2310107 71717000000000000000-00000000r0010002100300320060020019007lpw131210119

24、8765432111116 6w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 在機(jī)內(nèi)存儲(chǔ)形式為在機(jī)內(nèi)存儲(chǔ)形式為: :2 23 35 5282821211919404032326060100100b bc ca ad de eg gf fh h請(qǐng)注意：哈夫曼請(qǐng)注意：哈夫曼樹(shù)樣式不惟一！樹(shù)樣式不惟一！5991110104917284060100雙親雙親左右孩子左右孩子362410107 7171711116 62 23 35 5282821211919404032326060100100b bc ca ad de eg gf

25、fh h對(duì)應(yīng)的哈夫曼編碼：對(duì)應(yīng)的哈夫曼編碼：符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.100000010100111001011101110 00 00 00 00 00 00 01 11 11 11 11 11 11 1Huffman碼的碼的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二進(jìn)制等長(zhǎng)碼的二進(jìn)制等長(zhǎng)碼的WPL按左按左0右右1標(biāo)注標(biāo)注25另另一一種種表表示示：26