非線性數(shù)據(jù)結(jié)構(gòu)--圖-資料下載頁
2025-08-01 14:45本頁面
【正文】 Lb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 √ ? 按哈夫曼樹構(gòu)造二叉樹，應(yīng)用于實(shí)際問題，可提高處理效率。 28/32 二 . 構(gòu)造 Huffman樹 ? 算法 : – 1）將 n個(gè)帶權(quán)值 wi（ i≤n）的結(jié)點(diǎn)構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個(gè)根結(jié)點(diǎn)。 – 2）在 T中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹，構(gòu)成一個(gè)新的二叉樹，其根結(jié)點(diǎn)的權(quán)值取左右子樹權(quán)值之和； – 3）在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； – 4）重復(fù) 2）、 3）步，直到 T中只含一棵樹為止，該樹就是 Huffman樹。 29/32 構(gòu)造 Huffman樹舉例 ? 以權(quán)值分別為 7， 5， 2， 4的結(jié)點(diǎn) a、 b、 c、d構(gòu)造 Huffman樹。 （ 1） T= { a b c d } （ 2） T= { a b T3 } （ 3） T= { a T2 } （ 4） T={ T1 } c d T3 b T1 T2 2 4 6 6 5 11 b T2 6 5 11 c d 2 4 18 a T2 7 11 T1 18 a 7 T1 b T1 T2 6 5 11 18 a 7 T1 b 5 11 c d 2 6 4 30/32 三 . Huffman編碼 ? 編碼：用二進(jìn)制數(shù)的不同組合來表示字符。 ? 前綴編碼：一種非等長編碼。任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。 a 0 b 0 1 c d 0 1 1 編碼： A（ 0） B（ 10） C（ 110） D（ 111） 方法約定： 1）左分支為‘ 0’ 2）右分支為‘ 1’ 3）由根到葉路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼 。 ? Huffman編碼：一種前綴編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造 Huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼 例：設(shè)要傳送的電文是： abaccda ， 有 4個(gè)字符 abcd， 可分別編碼為 00、 0 11，則電文是： 00010010101100，共 14位，可采用哈夫曼編碼縮短長度： 字母 abcd出現(xiàn)頻率分別為： 1。 W={3 1 2 1} 3 1 2 1 W={3 2 2} 1 1 2 W= {3 2 2} 1 1 2 2 4 W={3 4} 1 1 2 2 4 1 1 2 2 4 3 a c b d 0 1 0 0 1 1 a b c d 0 110 10 111 abaccda 0110010101110 前綴編碼 32/32 作業(yè)、思考題 思考題： 18 第 2章作業(yè) 1 20
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1