《數(shù)據(jù)結(jié)構(gòu)(牛小飛)5哈夫曼樹和哈夫曼編碼》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(牛小飛)5哈夫曼樹和哈夫曼編碼（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、哈 夫 曼 樹 與 哈 夫 曼 編 碼 1. 編 碼 與 前 綴 編 碼 2. 哈 夫 曼 樹 與 哈 夫 曼 編 碼 3. 章 末 復(fù) 習(xí) 哈 夫 曼 樹 與 哈 夫 曼 編 碼 1.最 優(yōu) 二 叉 樹 的 定 義 2.如 何 構(gòu) 造 最 優(yōu) 二 叉 樹 3.哈 夫 曼 編 碼 編 碼假 設(shè) 要 將 一 段 文 字 “ ABAADBCACB” 由 甲 方 傳 給 乙 方A B C D00 01 10 11 ABAADBCACB 00010000110110001001總 的 編 碼 長(zhǎng) 度 是 20位編 碼 ： 用 二 進(jìn) 制 數(shù) 表 示 字 符特 點(diǎn) ： 等 長(zhǎng) 編 碼 前 綴 編 碼每
2、個(gè) 字 符 出 現(xiàn) 的 頻 率 不 一 樣 ， 采 用 變 長(zhǎng) 編 碼 ，使 得 出 現(xiàn) 頻 率 多 的 編 碼 短 ， 頻 率 低 的 編 碼 長(zhǎng) ，會(huì) 使 總 的 編 碼 長(zhǎng) 度 最 短 。 A 4 B 3 C 2 D 1A B C D0 1 00 010100011000001 接 收 方 如 何 譯 碼 ？ABAADBCACB 0100011000001ABAADBCACB 前 綴 編 碼 任 何 一 個(gè) 字 符 的 編 碼 都 不 是 同 一 字 符 集中 另 一 個(gè) 字 符 的 編 碼 的 前 綴 。 利 用 哈 夫 曼 樹 可 以 構(gòu) 造 一 種 不 等 長(zhǎng) 的 二進(jìn) 制 編 碼
3、 ， 并 且 構(gòu) 造 所 得 的 哈 夫 曼 編 碼 是 一種 最 優(yōu) 前 綴 編 碼 ， 即 使 所 傳 電 文 的 總 長(zhǎng) 度 最短 。 樹 的 路 徑 長(zhǎng) 度 定 義 為 ：最 優(yōu) 二 叉 樹 的 定 義從 根 結(jié) 點(diǎn) 到 該 結(jié) 點(diǎn) 的 路 徑 上 分 支 的 數(shù) 目 。 結(jié) 點(diǎn) 的 路 徑 長(zhǎng) 度 定 義 為 ：樹 中 每 個(gè) 結(jié) 點(diǎn) 的 路 徑 長(zhǎng) 度 之 和 。 ACB ED樹 的 路 徑 長(zhǎng) 度 為 5 最 優(yōu) 二 叉 樹 的 定 義 樹 的 帶 權(quán) 路 徑 長(zhǎng) 度 定 義 為 ：樹 中 所 有 葉 子 結(jié) 點(diǎn) 的 帶 權(quán) 路 徑 長(zhǎng) 度 之 和 WPL(T) = wklk (
4、對(duì) 所 有 葉 子 結(jié) 點(diǎn) )nk=1 最 優(yōu) 二 叉 樹 的 定 義AB CH ID E F G7 5 2 4 9 WPL(T)= 7 2+5 2+2 3+4 3+9 2 =60 最 優(yōu) 二 叉 樹 的 定 義AB CH ID EF G7 49 5 2 WPL(T)= 7 4+9 4+5 3+4 2+2 1=89 最 優(yōu) 二 叉 樹 的 定 義 最 優(yōu) 二 叉 樹 定 義 為 ：帶 權(quán) 路 徑 長(zhǎng) 度 WPL最 小 的 二 叉 樹 ， 又 稱 為 哈夫 曼 樹 。 哈 夫 曼 樹(哈 夫 曼 算 法 )以 二 叉 樹 為 例 : 1.根 據(jù) 給 定 的 n 個(gè) 權(quán) 值 w1, w2, , w
5、n， 構(gòu)造 n 棵 二 叉 樹 的 集 合 F = T1, T2, , Tn， 其 中 每 棵 二 叉 樹 中 均 只 含 一 個(gè) 帶 權(quán) 值 為 wi 的 根 結(jié) 點(diǎn) ,其 左 、 右 子 樹 為 空 樹 ; 2.在 F 中 選 取 其 根 結(jié) 點(diǎn) 的 權(quán) 值 為 最 小 的 兩棵 二 叉 樹 ， 分 別 作 為 左 、 右 子 樹 構(gòu) 造 一 棵 新 的二 叉 樹 ， 并 置 這 棵 新 的 二 叉 樹 根 結(jié) 點(diǎn) 的 權(quán) 值 為其 左 、 右 子 樹 根 結(jié) 點(diǎn) 的 權(quán) 值 之 和 ;哈 夫 曼 樹 3.從 F中 刪 去 這 兩 棵 樹 ， 同 時(shí) 將 剛 生 成 的新 樹 加 入 到
6、F中 ; 4.重 復(fù) (2) 和 (3) 兩 步 ， 直 至 F 中 只 含一 棵 樹 為 止 。 哈 夫 曼 樹 例 如 : 已 知 權(quán) 值 W= 5, 6, 2, 9, 7 95 6 2 776 9 7139 25 7 61)2)3) 257哈 夫 曼 樹 4) 5)6 713 9 25 7166 713 299 25 716 WPL=2 3 + 5 3 +6 2 + 7 2 + 9 2=65哈 夫 曼 樹 例 如 : 已 知 權(quán) 值 W= 5, 6, 2, 9, 7 95 6 2 776 97 139 52 761)2)3) 527哈 夫 曼 樹 4) 5)7 916 2913 52 7
7、6 7 91613 52 76WPL=6 2 + 7 2 +9 2 + 2 3 + 5 3=65哈 夫 曼 樹 哈 夫 曼 樹特 點(diǎn) ：1、 有 n個(gè) 葉 子 結(jié) 點(diǎn)2、 沒(méi) 有 度 為 1的 結(jié) 點(diǎn)3、 總 的 結(jié) 點(diǎn) 數(shù) 為 2n-14、 形 態(tài) 不 唯 一 哈 夫 曼 編 碼A B C D E6 7 2 5 9假 設(shè) 有 5個(gè) 符 號(hào) 以 及 它 們 的 頻 率 ：求 前 綴 編 碼 952 7 166 713 290 10 1001 100 01 100 101 11哈 夫 曼 編 碼1、 建 立 哈 夫 曼 樹2、 對(duì) 邊 編 號(hào)3、 求 出 葉 子 結(jié) 點(diǎn) 的 路 徑4、 得 到
8、字 符 編 碼A B C D E6 7 2 5 900 01 100 101 11 EDC 7 16A B13 290 10 1 00 11哈 夫 曼 編 碼如 何 譯 碼 ？001011110001 ？ ？ ？ADECB A B C D E00 01 100 101 11A D E C B 課 堂 練 習(xí) 設(shè) 電 文 中 出 現(xiàn) 的 字 母 為 A、 B、 C、 D和 E，每 個(gè) 字 母 在 電 文 中 出 現(xiàn) 的 次 數(shù) 分 別 9、27、 3、 5、 和 11。 按 哈 夫 曼 編 碼 ， 則 C的 編碼 為 : A、 10 B、 110 C、 1110 D、 1111 1. 熟 悉 樹
9、 的 各 種 存 儲(chǔ) 結(jié) 構(gòu) 及 其 特 點(diǎn) 。 建 立 存 儲(chǔ) 結(jié)構(gòu) 是 進(jìn) 行 其 它 操 作 的 前 提 ， 因 此 應(yīng) 掌 握 1 至 2 種建 立 樹 的 存 儲(chǔ) 結(jié) 構(gòu) 的 方 法 。章 末 復(fù) 習(xí)2. 熟 練 掌 握 二 叉 樹 的 結(jié) 構(gòu) 特 性 ， 理 解 相 應(yīng) 的 證 明方 法 。3. 熟 悉 二 叉 樹 的 各 種 存 儲(chǔ) 結(jié) 構(gòu) 的 特 點(diǎn) 及 適 用 范 圍 。 章 末 復(fù) 習(xí)4. 遍 歷 二 叉 樹 是 二 叉 樹 各 種 操 作 的 基 礎(chǔ) 。 實(shí) 現(xiàn) 二叉 樹 遍 歷 的 具 體 算 法 與 所 采 用 的 存 儲(chǔ) 結(jié) 構(gòu) 有 關(guān) 。掌 握 各 種 遍 歷 策
10、 略 的 遞 歸 算 法 ， 靈 活 運(yùn) 用 遍 歷 算法 實(shí) 現(xiàn) 二 叉 樹 的 其 它 操 作 。 層 次 遍 歷 是 按 另 一 種搜 索 策 略 進(jìn) 行 的 遍 歷 。5. 掌 握 樹 和 森 林 與 二 叉 樹 的 轉(zhuǎn) 換 方 法 。 章 末 復(fù) 習(xí)7. 熟 練 掌 握 二 叉 查 找 樹 的 結(jié) 構(gòu) 特 性 ， 熟 練 掌 握 通過(guò) 二 叉 查 找 樹 各 種 方 法 的 實(shí) 現(xiàn) ， 對(duì) 查 找 性 能 能 夠進(jìn) 行 正 確 分 析 。6. 了 解 AVL樹 的 結(jié) 構(gòu) 特 性 。8.了 解 哈 夫 曼 樹 (最 優(yōu) 二 叉 樹 )的 特 性 ， 掌 握 建 立 最優(yōu) 樹 和 哈 夫 曼 編 碼 的 方 法 。
數(shù)據(jù)結(jié)構(gòu)(牛小飛)5哈夫曼樹和哈夫曼編碼
