《哈夫曼樹(shù)總結(jié)習(xí)題(2學(xué)時(shí)).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《哈夫曼樹(shù)總結(jié)習(xí)題(2學(xué)時(shí)).ppt（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

6 6Huffman樹(shù)基本概念 構(gòu)造 編碼 1 基本概念路徑 從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支 路徑長(zhǎng)度 路徑上分支數(shù)目 結(jié)點(diǎn)的路徑長(zhǎng)度 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度 樹(shù)的路徑長(zhǎng)度 樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 完全二叉樹(shù)這種長(zhǎng)度最短的二叉樹(shù) 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 該結(jié)點(diǎn)的路徑長(zhǎng)度 結(jié)點(diǎn)的權(quán)值樹(shù)的帶權(quán)路徑長(zhǎng)度 樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 記作 WPL wklk例如最優(yōu)二叉樹(shù) 在所有含n個(gè)葉子結(jié)點(diǎn) 并帶相同權(quán)值的二叉樹(shù)中 必存在WPL最小的二叉樹(shù) 又叫Huffman樹(shù) W 7 2 4 5 9 A E D B C B C D A E 7 2 4 9 5 7 2 4 5 9 WPL1 wklk 7 2 5 2 2 3 4 3 9 2 60 WPL2 wklk 7 4 9 4 5 3 4 2 2 1 89 在解決某些判定問(wèn)題時(shí) 利用Huffman樹(shù)可得到最佳判定算法例如 某廠(chǎng)生產(chǎn)螺釘 要求直徑為d 誤差 現(xiàn)測(cè)量某螺釘直徑 方法與標(biāo)準(zhǔn)的比較 判定樹(shù) d d d d 5 10 50 25 10 WPL 5 3 10 3 50 2 25 2 10 2 概率最大的最靠近根判斷 2 Huffman樹(shù)的構(gòu)造 自底向上 A 7 D 5 E 9 F2 F3 W 7 2 4 5 9 接上頁(yè) F4 F5 根的權(quán)值為27WPL 7 2 2 3 4 3 5 2 9 2 60 Huffman樹(shù)形態(tài)不唯一 構(gòu)造過(guò)程 Huffman算法 1 n個(gè)權(quán)值構(gòu)成n棵獨(dú)立二叉樹(shù)的森林F T1 Tn 2 在森林中選出兩棵根權(quán)值最小的二叉樹(shù)作為左右子樹(shù) 構(gòu)造二叉樹(shù) 根權(quán)值為左右子樹(shù)的和 3 在F中刪除這兩棵 新構(gòu)成的添加到F中 4 重復(fù) 2 和 3 直到F中含一棵二叉樹(shù)為止 兩個(gè)結(jié)論 1 在Huffman樹(shù)中沒(méi)有度為1的結(jié)點(diǎn) 2 一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)共有2n 1個(gè)結(jié)點(diǎn) 證明 設(shè)總結(jié)點(diǎn)數(shù)為m個(gè) 葉子n個(gè) 度為1的n1個(gè) 度為2的n2個(gè)m n n1 n2由性質(zhì)3n n2 1所以n2 n 1m n n1 n2 n n1 n 1 2n n1 1有 1 得n1 0所以m 2n 0 1 2n 1 3 Huffman編碼 1 等長(zhǎng)編碼 2 不等長(zhǎng)編碼 出現(xiàn)多的字符采用短碼 總長(zhǎng)短了 但出現(xiàn)二義性 3 前綴編碼 一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴 ABCD00011011 兩位一分進(jìn)行譯碼 ABCD000111 用二叉樹(shù)實(shí)現(xiàn) 左分支0 右分支1 A 00B 01C 1 4 Huffman編碼 設(shè)計(jì)Huffman樹(shù)而得到的編碼 例如 有8種字符 概率如下 0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 解 同時(shí)擴(kuò)大100倍 得權(quán)值集合 5 29 7 8 14 23 3 11 設(shè)計(jì)Huffman編碼 WPL 0 23 2 0 11 3 Huffman編碼0 05 01100 29 100 07 11100 08 11110 14 1100 23 000 03 01110 11 010 作業(yè) 本章小結(jié)1 掌握樹(shù)的定義 表示形式和術(shù)語(yǔ) 二叉樹(shù)通用 掌握樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子 兄弟表示 掌握樹(shù)與二叉樹(shù)的轉(zhuǎn)換了解樹(shù)的ADT定義與樹(shù)和森林遍歷2 掌握二叉樹(shù)的ADT定義 特點(diǎn) 結(jié)點(diǎn)的形態(tài) 性質(zhì) 存儲(chǔ)結(jié)構(gòu) 二叉鏈表 掌握二叉樹(shù)的遍歷 線(xiàn)索的方法掌握遍歷算法的應(yīng)用掌握二叉樹(shù)與樹(shù)和森林的轉(zhuǎn)換掌握Huffman樹(shù)概念 構(gòu)造和編碼