樹和二叉樹ppt課件(2)-展示頁
2025-05-08 02:58本頁面
【正文】 n WPL =∑ w klk k=1 其中： Wk：第 k個葉子結(jié)點(diǎn)的權(quán)值； Lk：第 k個葉子結(jié)點(diǎn)的路徑長度 . ? （最優(yōu)二叉樹） 是指對于一組帶有確定權(quán)值的 葉子結(jié)點(diǎn)構(gòu)造的具有最小帶權(quán)路徑長度的 二叉樹。第 5章 樹 和二叉樹 第 5章 樹和二叉樹 樹的概念和基本操作 二叉樹 樹和森林 哈夫曼樹及其應(yīng)用 應(yīng)用舉例 ? 哈夫曼樹的基本概念 ? 哈夫曼樹的構(gòu)造算法 ? 哈夫曼編碼 ? 哈夫曼編碼的算法實(shí)現(xiàn) 最優(yōu)二叉樹 — 哈夫曼樹 哈夫曼樹的基本概念 : 從樹中一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成兩個結(jié)點(diǎn)之間的路徑 . :是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。 : 從樹根到每個結(jié)點(diǎn)的路徑長度之和。即： 設(shè)有給定的 n 個權(quán)值 {w1, w2, …, w n}， 構(gòu)造一棵由 n個葉子結(jié)點(diǎn)的 , 每個葉子結(jié)點(diǎn)的帶權(quán)為 wi,則其中帶權(quán)路徑長度 WPL最小的 二叉樹稱為最優(yōu)樹或 哈夫曼樹 . 2 7 5 4 9 WPL= 7?2+5?2+2?3+4?3+9?2 =60 WPL= 7?4+9?4+5?3+4?2+2?1 =89 7 9 2 5 4 根據(jù)給定的 n 個權(quán)值 {w1, w2, …, w n}， 構(gòu)造 n 棵二叉樹的集合 F = {T1, T2, … , T n}， 其中每棵二叉樹中均只含一個帶權(quán)值 為 wi 的根結(jié)點(diǎn) ,其左、右子樹為空樹 。 (2) 從 F中刪去這兩棵樹，同時加入 剛生成的新樹 。 (3) (4) 例如 : 已知權(quán)值 W={ 8, 6, 2, 4 } 構(gòu)造哈夫曼樹的過程 4 8 6 2 2 4 6 8 6 8 6 12 2 4 6 第一步 : 第二步 : 第三步 : 圖 523 構(gòu)造哈夫曼樹的過程 第四步 : 8 6 12 2 4 6 20 圖 523 構(gòu)造哈夫曼樹的過程 ?由哈夫曼樹的定義，一棵二叉樹要使其 WPL值最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越靠遠(yuǎn)離根結(jié)點(diǎn)。 B:01 。 D:11. 則上述電文可譯為 : 0001000010100100111000 A B AA CC B A D C A 總長 22位 ,接收方按兩位一組譯碼即可 . 哈夫曼編碼 由于采用定長編碼的電文總長無法縮短 ,因此 ,對字符采用 不定長 編碼 .且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼 ,從而盡可能的減小電文總長 . 例如 :上例中 ,A,C出現(xiàn)的頻率
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1