數(shù)據(jù)結(jié)構(gòu)算法之樹(shù)的應(yīng)用-文庫(kù)吧資料
2025-05-05 08:39本頁(yè)面
【正文】 出相應(yīng)的哈夫曼樹(shù)； 步驟 2：樹(shù)中各結(jié)點(diǎn)到其左孩子的邊上的權(quán)值設(shè)為 0、到其右孩子的邊上的權(quán)值設(shè)為 1（即所謂左 0右 1）； 步驟 3：從根開(kāi)始到“葉子”所經(jīng)歷的邊上的數(shù)值的序列即為該“葉子”所對(duì)應(yīng)的字符的編碼。 則對(duì)于電文“ ABACCDA”的二進(jìn)制電碼為： 000011010 總長(zhǎng)為 9位 如 000011010中的前 4個(gè) 0的譯碼會(huì)有如下幾種不同譯碼： 0000→ AAAA； 0000→ ABA；0000→ BB 思考：如何解決這一問(wèn)題？ 問(wèn)題的關(guān)鍵在于編碼是否為 無(wú)前綴編碼 。 設(shè)這 4個(gè)不同的字符為 A， B， C， D，則可進(jìn)行等長(zhǎng)編碼如下： 二、哈夫曼樹(shù)及其應(yīng)用 ① 等長(zhǎng) 編碼： 設(shè)這 4個(gè)不同的字符為 A， B， C， D，則可進(jìn)行等長(zhǎng)編碼如下： 二、哈夫曼樹(shù)及其應(yīng)用 ① 等長(zhǎng) 編碼： 設(shè)這 4個(gè)不同的字符為 A， B， C， D，則可進(jìn)行等長(zhǎng)編碼如下： A: 00 B: 01 C: 10 D: 11 則對(duì)于電文“ ABACCDA”的二進(jìn)制電碼為： 00010010101100 總長(zhǎng)為 14位 譯碼時(shí)，兩位一分進(jìn)行譯碼，可唯一得到電文：ABACCDA 。 7位二進(jìn)制數(shù)可以為 27個(gè)不同的英文字符編碼。 a 40 b 30 c 5 d 10 e 15 15 30 求解過(guò)程 二、哈夫曼樹(shù)及其應(yīng)用 ③ 實(shí)例：已知有 5個(gè)葉子結(jié)點(diǎn)的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫(huà)出一棵相應(yīng)的哈夫曼樹(shù)。 a 40 b 30 c 5 d 10 e 15 15 求解過(guò)程 二、哈夫曼樹(shù)及其應(yīng)用 ③ 實(shí)例：已知有 5個(gè)葉子結(jié)點(diǎn)的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫(huà)出一棵相應(yīng)的哈夫曼樹(shù)。若是，則求解過(guò)程結(jié)束；否則，轉(zhuǎn)步驟 2。 步驟 2:在 F中選取兩棵其根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù)，從F中刪除這兩棵樹(shù)，并以這兩棵二叉樹(shù)為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)添加到 F中，該新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右孩子二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值之和。 i=1 n 求解過(guò)程 二、哈夫曼樹(shù)及其應(yīng)用 ① 問(wèn)題： 已知 n個(gè)葉子的權(quán)值為 {w1,w2,...wn}，構(gòu)造一棵最優(yōu)二叉樹(shù)。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1