樹和二叉樹ppt課件(2)(已修改)
2025-05-11 02:58 本頁面
【正文】 第 5章 樹 和二叉樹 第 5章 樹和二叉樹 樹的概念和基本操作 二叉樹 樹和森林 哈夫曼樹及其應(yīng)用 應(yīng)用舉例 ? 哈夫曼樹的基本概念 ? 哈夫曼樹的構(gòu)造算法 ? 哈夫曼編碼 ? 哈夫曼編碼的算法實(shí)現(xiàn) 最優(yōu)二叉樹 — 哈夫曼樹 哈夫曼樹的基本概念 : 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑 . :是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。 : 從樹根到每個(gè)結(jié)點(diǎn)的路徑長度之和。完全二叉樹就是這種路徑長度最短的二叉樹 . 帶權(quán) 路徑長度 ：是從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)值的乘積 . 路徑長度 ：樹中所有 葉子 結(jié)點(diǎn)的帶權(quán)路徑長度之和 .通常記作 : n WPL =∑ w klk k=1 其中： Wk：第 k個(gè)葉子結(jié)點(diǎn)的權(quán)值； Lk：第 k個(gè)葉子結(jié)點(diǎn)的路徑長度 . ? （最優(yōu)二叉樹） 是指對于一組帶有確定權(quán)值的 葉子結(jié)點(diǎn)構(gòu)造的具有最小帶權(quán)路徑長度的 二叉樹。即： 設(shè)有給定的 n 個(gè)權(quán)值 {w1, w2, …, w n}， 構(gòu)造一棵由 n個(gè)葉子結(jié)點(diǎn)的 , 每個(gè)葉子結(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 個(gè)權(quán)值 {w1, w2, …, w n}， 構(gòu)造 n 棵二叉樹的集合 F = {T1, T2, … , T n}， 其中每棵二叉樹中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn) ,其左、右子樹為空樹 。 哈夫曼樹的構(gòu)造 (1) (哈夫曼算法 ) 以二叉樹為例 : 在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和 。 (2) 從 F中刪去這兩棵樹，同時(shí)加入 剛生成的新樹 。 重復(fù) (2) 和 (3) 兩步，直至 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)造哈夫曼樹的過程 ?由哈夫曼樹的定義，一棵二叉樹要使
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1