并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個(gè)數(shù)方案二：哈夫曼樹(shù)的建立和編-全文預(yù)覽
【正文】 也稱(chēng)為 前綴碼 —— 將 Huffman樹(shù) 與 Huffman編碼 掛鉤 17 二、 Huffman編碼 （ 1） 由于 Huffman樹(shù)的 WPL最小， 說(shuō)明編碼所需要的 比特?cái)?shù)最少 。 (3) 在 F 中刪去這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入 F中 。 例如： a→e 的路徑長(zhǎng)度＝ 樹(shù)長(zhǎng)度＝ 2 10 Huffman常譯為 赫夫曼、霍夫曼、哈夫曼等 Weighted Path Length 12 樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？ WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 經(jīng)典之例： WPL= WPL= WPL= Huffman樹(shù)是 WPL 最小的樹(shù) 樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 36 46 35 13 1. 構(gòu)造 Huffman樹(shù)的基本思想： 例： 設(shè)有 4個(gè)字符 d,i,a,n，出現(xiàn)的頻度分別為 7,5,2,4， 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？ 法 1： 等長(zhǎng)編碼 （如二進(jìn)制編碼） 令 d=00， i=01， a=10， n=11，則： WPL1＝ 2bit (7＋ 5＋ 2＋ 4）＝ 36 法 2： 不等長(zhǎng)編碼 （如 Huffman編碼） 令 d=0。例如： 10 Huffman樹(shù)及其應(yīng)用 一、 Huffman樹(shù) 二、 Huffman編碼 最優(yōu)二叉樹(shù) Huffman樹(shù) Huffman編碼 帶權(quán)路徑長(zhǎng)度最短的樹(shù) 不等長(zhǎng)編碼 是通信中最經(jīng)典的壓縮編碼 11 一、 Huffman樹(shù) （最優(yōu)二叉樹(shù)） 路 徑 ： 路徑長(zhǎng)度 ： 樹(shù)的路徑長(zhǎng)度 ： 帶權(quán)路徑長(zhǎng)度 ： 樹(shù)的帶權(quán)路徑長(zhǎng)度 ： Huffman樹(shù) ： 由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。 思路： 首先，將 12個(gè)球分三組，每組 4個(gè)，任意取兩組稱(chēng)。 特點(diǎn) ：所有結(jié)點(diǎn)左右子樹(shù)深度差 ≤ 1 特點(diǎn) ：所有結(jié)點(diǎn) “ 左小右大 ” 5 什么是平衡二叉樹(shù) （ 又稱(chēng) AVL 樹(shù)） ？ 性質(zhì)： 所有 結(jié)點(diǎn)左、右子樹(shù)深度之差的絕對(duì)值 ≤ 1 若定義結(jié)點(diǎn)的“ 平衡因子 ” BF = 左子樹(shù)深度 – 右子樹(shù)深度 則：平衡二叉樹(shù)中所有結(jié)點(diǎn)的 BF ∈ [ 1, 0, 1 ] (a) 平衡樹(shù) (b) 不平衡樹(shù) 例：判斷下列二叉樹(shù)是否 AVL樹(shù)？ 0 0 0 1 1 1 1 2 0 0 0 1 1 6 什么是二叉排序樹(shù)？ （ a） （ b） 例： 下列 2種圖形中，哪個(gè)不是二叉排序樹(shù) ？ 或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)： （ 1）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值； （ 2）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值； （ 3）它的左右子樹(shù)也分別為二叉排序樹(shù)。1 方案一：二叉樹(shù)的建立和遍歷 具體內(nèi)容：先生成一棵二叉樹(shù)，再用中序遍歷方式打印每個(gè)結(jié)點(diǎn)值，并統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個(gè)數(shù) 。 Binary Tree） 樹(shù)的基本概念 二叉樹(shù) 遍歷二叉樹(shù)和線索二叉樹(shù) 樹(shù)和森林 Huffman樹(shù)及其應(yīng)用 4 先介紹二叉樹(shù)的典型應(yīng)用 平衡樹(shù) —— 排序樹(shù) —— 字典樹(shù) —— 判定樹(shù) —— 帶權(quán)樹(shù) —— 最優(yōu)樹(shù) —— 由字符串構(gòu)成的二叉排序樹(shù) 特點(diǎn) ：分
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1