算法及數(shù)據(jù)結(jié)構(gòu)第6章3

1、1第第6章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用2上堂課例題討論上堂課例題討論問問: : 設(shè)一棵完全二叉樹具有設(shè)一棵完全二叉樹具有10001000個結(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)只有非空左子樹，有樹，有 個結(jié)點(diǎn)只有非空右子樹。個結(jié)點(diǎn)只有非空右子樹。法法1 1：先先求全部葉子數(shù)。求全部葉子數(shù)。n n0 048

2、9489( (末層末層) )1111(k-1(k-1層層) )= =500500個；個；法法2 2：先求先求2 2度結(jié)點(diǎn)數(shù)。度結(jié)點(diǎn)數(shù)。n n2 2=255=255( (k-2層層) )244244( (k-1層層) )= =499499個；個； 這兩種方法的缺點(diǎn)：都要先計算樹的深度這兩種方法的缺點(diǎn)：都要先計算樹的深度 k=k= log2n 1 =10; =10; 法法3 3：無需求樹深無需求樹深k k，便可快捷求出，便可快捷求出 取大于取大于n/2n/2的最小整數(shù)值的最小整數(shù)值 可由二叉樹性質(zhì)可由二叉樹性質(zhì)5 5輕松證明！輕松證明！( (編號為編號為i i的結(jié)點(diǎn)，其孩子編號必為的結(jié)點(diǎn)，其孩子編

3、號必為2i2i和和2i+1)2i+1) nn已知最后一個結(jié)點(diǎn)編號為已知最后一個結(jié)點(diǎn)編號為n n，則其雙親（，則其雙親（n/2n/2或或(n-1)/2)(n-1)/2)肯定是最后一個非葉子結(jié)點(diǎn)。其編號之后的全部結(jié)點(diǎn)都肯定是最后一個非葉子結(jié)點(diǎn)。其編號之后的全部結(jié)點(diǎn)都是葉子了！是葉子了！故，故，n0=n-n/2n0=n-n/2或或n-(n-1)/2= n-(n-1)/2= 3問：問：用二叉鏈表法（用二叉鏈表法（l_child, r_childl_child, r_child）存儲包含）存儲包含n n個結(jié)點(diǎn)個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中必有的二叉樹，結(jié)點(diǎn)的指針區(qū)域中必有 個空指針。個空指針。思考：思

4、考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？所以，所以， 空指針個數(shù)空指針個數(shù)2n(n-1)=n+1個個。n+1分析：分析：n n個結(jié)點(diǎn)必有個結(jié)點(diǎn)必有2n個鏈域；個鏈域； （見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）除根結(jié)點(diǎn)外，二叉樹中每一個結(jié)點(diǎn)除根結(jié)點(diǎn)外，二叉樹中每一個結(jié)點(diǎn)有且僅有一個雙親有且僅有一個雙親（直接（直接前驅(qū)），所以只會有前驅(qū)），所以只會有n n1 1個結(jié)點(diǎn)的鏈域存放指針，指向非空子個結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。女結(jié)點(diǎn)（即直接后繼）。4二、線索二叉樹線索二叉樹（

5、Threaded Binary Tree）普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存預(yù)存起來，則從起來，則從第第一個結(jié)點(diǎn)一個結(jié)點(diǎn)開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法：兩種解決方法：增加兩個域：增加兩個域：fwd和和bwd；存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預(yù)存這類信息？如何預(yù)存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D

6、C E A F H GB D C E A F H G，實際上，實際上已將二叉已將二叉樹轉(zhuǎn)為樹轉(zhuǎn)為線性排列線性排列，顯然具有唯一前驅(qū)和唯一后繼。，顯然具有唯一前驅(qū)和唯一后繼。1. 1. 定義定義 2. 2. 生成生成 3. 3. 遍歷遍歷利用空鏈域（利用空鏈域（n+1個空鏈域）個空鏈域）5規(guī)定：規(guī)定：1）若結(jié)點(diǎn)有左子樹，則）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點(diǎn)有右子樹，則）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線

7、索即線索) 。為區(qū)別兩種不同情況，特增加兩個標(biāo)志域（各為區(qū)別兩種不同情況，特增加兩個標(biāo)志域（各1bit)lchilddatarchild約定約定:當(dāng)當(dāng)Tag域為域為0時時,表示表示正常正常情況情況;當(dāng)當(dāng)Tag域為域為1時時,表示表示線索線索情況情況.右孩子或后繼右孩子或后繼左孩子或前驅(qū)左孩子或前驅(qū)LTagRTag6附：有關(guān)線索二叉樹的幾個術(shù)語：附：有關(guān)線索二叉樹的幾個術(shù)語： 線索鏈表：線索鏈表：用用含含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表 線線 索：索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹 線線 索索 化

8、：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程叉樹的過程討論：討論：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧也能遍歷整個樹。堆棧也能遍歷整個樹。7dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例：例：某某先序遍歷先序遍歷結(jié)果如下表所示，請畫出對應(yīng)的結(jié)果如下表所示，請畫出對應(yīng)的二叉樹。二叉樹。（多帶了兩個標(biāo)志！）（多帶了兩個標(biāo)志！）82. 2. 線索二叉樹的生成線索二叉樹的生成線索化過程就是線索

9、化過程就是在遍歷過程中修改空指針在遍歷過程中修改空指針的過程：的過程：將空的將空的l lchildchild改為結(jié)點(diǎn)的直接前驅(qū)；改為結(jié)點(diǎn)的直接前驅(qū)；將空的將空的r rchildchild改為結(jié)點(diǎn)的直接后繼。改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況正常情況”）9ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個頭結(jié)點(diǎn)一個頭結(jié)

10、點(diǎn)例例1 1：畫出以下二叉樹對應(yīng)的畫出以下二叉樹對應(yīng)的中序中序線索二叉樹。線索二叉樹。1000A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：11例例2 2：【 2000年計算機(jī)系考研題】年計算機(jī)系考研題】給定如圖所示給定如圖所示二叉樹二叉樹T T，請畫出與其對應(yīng)的中序線索二叉樹。，請畫出與其對應(yīng)的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：555

11、5 40 25 60 40 25 60 2828 08 33 08 33 5454對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL12線索二叉樹的生成算法線索二叉樹的生成算法（算法算法6.6, 見教材見教材P134）目的：目的：在在依某種順序遍歷依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后繼。二叉樹時修改空指針，添加前驅(qū)或后繼。注解：注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個指針：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個指針： p指針指針當(dāng)前結(jié)點(diǎn)之指針；當(dāng)前結(jié)點(diǎn)之指針； pre指針指針前驅(qū)結(jié)點(diǎn)之指針。前驅(qū)結(jié)點(diǎn)

12、之指針。技巧：技巧：當(dāng)結(jié)點(diǎn)當(dāng)結(jié)點(diǎn)p的左的左/右域為空右域為空時，只改寫它的左域（裝入前驅(qū)時，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。，而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。 或者說，當(dāng)前結(jié)點(diǎn)的指針或者說，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若若p-lchildNULL, ,則則p-Ltag=1;p-Ltag=1;p-lp-lchildchildprepre; ; /p/p的前驅(qū)結(jié)點(diǎn)指針的前驅(qū)結(jié)點(diǎn)指針prepre存入左空域存入左空域若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;1;pre-rpre-rc

13、hildchild= =p p; / /p p存入其前驅(qū)結(jié)點(diǎn)存入其前驅(qū)結(jié)點(diǎn)prepre的右空域的右空域133. 3. 線索二叉樹的遍歷線索二叉樹的遍歷理論上，只要找到序列中的理論上，只要找到序列中的第一個結(jié)點(diǎn)第一個結(jié)點(diǎn)，然后，然后依次訪依次訪問結(jié)點(diǎn)的后繼問結(jié)點(diǎn)的后繼直到后繼為空時結(jié)束。直到后繼為空時結(jié)束。在線索化二叉樹中，并不是每個結(jié)點(diǎn)都能直接找到其在線索化二叉樹中，并不是每個結(jié)點(diǎn)都能直接找到其后繼的，后繼的，當(dāng)標(biāo)志為當(dāng)標(biāo)志為0 0時，時，R_child=R_child=右孩子地址指針，并非后繼！右孩子地址指針，并非后繼！需要通過一定運(yùn)算才能找到它的后繼。需要通過一定運(yùn)算才能找到它的后繼。以以

14、中序線索二叉樹中序線索二叉樹為例：為例：對葉子結(jié)點(diǎn)（對葉子結(jié)點(diǎn)（RTag=1），直接后繼指針就在其），直接后繼指針就在其rchild域內(nèi)；域內(nèi)；對其他結(jié)點(diǎn)（對其他結(jié)點(diǎn)（RTag=0），直接后繼是其），直接后繼是其右子樹最左下的結(jié)點(diǎn)右子樹最左下的結(jié)點(diǎn)；（因為中序遍歷規(guī)則是（因為中序遍歷規(guī)則是LDR，）14程序注解程序注解 (非遞歸，且不用棧非遞歸，且不用棧）：）：P=T-lchild; /從頭結(jié)點(diǎn)進(jìn)入到根結(jié)點(diǎn)；從頭結(jié)點(diǎn)進(jìn)入到根結(jié)點(diǎn)；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍歷起點(diǎn)先找到中序遍歷起點(diǎn) if(!visit(p-data) re

15、turn ERROR; /若起點(diǎn)值為空則出錯告警若起點(diǎn)值為空則出錯告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標(biāo)志，則直接提取若有后繼標(biāo)志，則直接提取p-rchild中線索并中線索并訪問后繼結(jié)點(diǎn)；訪問后繼結(jié)點(diǎn)；p=p-rchild; /當(dāng)前結(jié)點(diǎn)右域不空當(dāng)前結(jié)點(diǎn)右域不空或或已經(jīng)找好了后繼已經(jīng)找好了后繼，則一律從，則一律從結(jié)點(diǎn)的右子樹開始重復(fù)結(jié)點(diǎn)的右子樹開始重復(fù) 的全部過程。的全部過程。Return OK;線索二叉樹的線索二叉樹的中序中序遍歷算法遍歷算法（算法算法6.5, 參見教材參見教材P134）LTag=0RTag=115算

16、法流程：算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演演示示程程序序16提前介紹：二叉樹的應(yīng)用提前介紹：二叉樹的應(yīng)用平衡樹平衡樹排序樹排序樹字典樹字典樹判定樹判定樹帶權(quán)樹帶權(quán)樹最優(yōu)樹最優(yōu)樹特點(diǎn)：左右子樹深度差特點(diǎn)：左右子樹深度差 1特點(diǎn)：特點(diǎn)：“左小右大左小右大”（見實驗二的方案（見實驗二的方案1）由字符串構(gòu)成的二叉樹排序樹由字符串構(gòu)成的二叉樹排序樹例如，例如，12個球只稱個球只稱3次分出輕重

17、次分出輕重特點(diǎn)：路徑長度帶權(quán)值特點(diǎn)：路徑長度帶權(quán)值 帶權(quán)路徑長度最短的樹，又稱帶權(quán)路徑長度最短的樹，又稱 Huffman樹，用途之一是通信中的壓縮編碼。樹，用途之一是通信中的壓縮編碼。17路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權(quán)路徑長度帶權(quán)路徑長度：樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：霍霍 夫夫 曼曼 樹樹：6.5 Huffman6.5 Huffman樹及其應(yīng)用樹及其應(yīng)用一、最優(yōu)二叉樹（一、最優(yōu)二叉樹（霍夫曼霍夫曼樹）樹）由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑上的分支數(shù)目路徑上的分支數(shù)目從樹根到從樹根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長度之和。的路徑長度之

18、和。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積預(yù)備知識：若干術(shù)語預(yù)備知識：若干術(shù)語debacf g樹中所有樹中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。帶權(quán)路徑長度最小的樹。aeae的路徑長度的路徑長度樹長度樹長度2 2101018HuffmanHuffman樹簡介：樹簡介：樹的帶權(quán)路徑長度如何計算？樹的帶權(quán)路徑長度如何計算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 35哈夫曼哈夫曼樹樹則則是是：WPL WPL

19、 最小的樹。最小的樹。Huffman樹樹Weighted Path LengthWeighted Path Length19構(gòu)造霍夫曼樹的基本思想：構(gòu)造霍夫曼樹的基本思想：構(gòu)造構(gòu)造HuffmanHuffman樹的步驟（即樹的步驟（即HuffmanHuffman算法）：算法）：20設(shè)有設(shè)有4 4個字符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2, 7,5,2, 4 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長編碼等長編碼。例如用二進(jìn)制編碼來實現(xiàn)。例如用二進(jìn)制編碼來實現(xiàn)。 取取 d=d=000

20、0，i=i=0101，a=a=1010，n=n=1111怎樣實現(xiàn)怎樣實現(xiàn)HuffmanHuffman編碼？編碼？法法2 2：不等長編碼不等長編碼，例如用哈夫曼編碼來實現(xiàn)。，例如用哈夫曼編碼來實現(xiàn)。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=, n=111111最快的編碼是哪個？最快的編碼是哪個？是非等長的是非等長的HuffmanHuffman碼！碼！先要構(gòu)造先要構(gòu)造HuffmanHuffman樹！樹！21操作要點(diǎn)操作要點(diǎn)1 1：對權(quán)值的合并、刪除與替換對權(quán)值的合并、刪除與替換在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是合并中，總是合并當(dāng)前值最小

21、當(dāng)前值最小的兩個權(quán)的兩個權(quán)構(gòu)造構(gòu)造HuffmanHuffman樹的步驟：樹的步驟：注：方框表示外結(jié)點(diǎn)（葉子，字符對應(yīng)的權(quán)值），注：方框表示外結(jié)點(diǎn)（葉子，字符對應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。22操作要點(diǎn)操作要點(diǎn)2 2：按左按左0 0右右1 1對對HuffmanHuffman樹的所有分支編號！樹的所有分支編號！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=1bitWPL=1bit7 72b

22、it2bit5+3bit(2+4)=5+3bit(2+4)=3535特點(diǎn)：每一碼都不是另一碼的前綴，絕不會錯譯特點(diǎn)：每一碼都不是另一碼的前綴，絕不會錯譯! ! 稱為前綴碼稱為前綴碼HuffmanHuffman樹樹 與與 HuffmanHuffman編碼編碼 掛鉤掛鉤23例例2 2（嚴(yán)題集（嚴(yán)題集6.266.26）：假設(shè)用于通信的電文僅由假設(shè)用于通信的電文僅由8 8個字母個字母 a, a, b, c, d, e, f, g, hb, c, d, e, f, g, h 構(gòu)成，它們在電文中出現(xiàn)的概率分別構(gòu)成，它們在電文中出現(xiàn)的概率分別為為 0.07, 0.19, 0.02, 0.06, 0.32,

23、0.03, 0.21, 0.10 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這試為這8 8個字母設(shè)計哈夫曼編碼。個字母設(shè)計哈夫曼編碼。如果用如果用0 07 7的二進(jìn)制編碼方案的二進(jìn)制編碼方案又如何？又如何？霍夫曼霍夫曼編碼的基本思想是：編碼的基本思想是：概率大的字符用短碼，概率小的用概率大的字符用短碼，概率小的用長碼長碼。由于。由于霍夫曼樹的霍夫曼樹的WPLWPL最小，說明編碼所需要的比特數(shù)最最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。解：解：先將概率放大先將概率放大100100倍

24、，以方便構(gòu)造哈夫曼樹。倍，以方便構(gòu)造哈夫曼樹。權(quán)值集合權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。24w4=19, 21, w4=19, 21, 28,28, 32 32為清晰起見，重新排序為為清晰起見，重新排序為: :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 2

25、1, 32 6, 7, 10, 19, 21, 32w2=7, 10, w2=7, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼樹哈夫曼樹25對應(yīng)的哈夫曼編碼（左對應(yīng)的哈夫曼編碼（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的碼的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