版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、6.8 哈 夫 曼 樹 與 哈 夫 曼 編 碼 最優(yōu)樹的定義 如何構(gòu)造最優(yōu)樹 前綴編碼 赫夫曼編碼 6.8 哈 夫 曼 樹 與 哈 夫 曼 編 碼 一、最優(yōu)樹的定義樹的路徑長度定義為: 樹中每個結(jié)點的路徑長度之和。 結(jié)點的路徑長度定義為: 從根結(jié)點到該結(jié)點的路徑上 分支的數(shù)目。 一、最優(yōu)樹的定義樹的路徑長度定義為: 結(jié)點的路徑長度定義為 樹的帶權(quán)路徑長度定義為: 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點)。假設(shè)有n個權(quán)值w1,w2,wn,構(gòu)造一棵有n個葉子結(jié)點的二叉樹,每個葉子結(jié)點帶權(quán)為Wi,則其中帶權(quán)路徑長度取最小值的二叉樹稱為“最優(yōu)樹”。例如: 樹的
2、帶權(quán)路徑長度定義為:假設(shè)有n個權(quán)值w1,w2,w27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 5427 9 75492WPL(T)= 7 根據(jù)給定的 n 個權(quán)值 w1, w2, , wn, 構(gòu)造 n 棵二叉樹的集合 F = T1, T2, , Tn, 其中每棵二叉樹中均只含一個帶權(quán)值 為 wi 的根結(jié)點,其左、右子樹為空樹;二、如何構(gòu)造最優(yōu)樹(1) (赫夫曼算法) 以二叉樹為例: 根據(jù)給定的 n 個權(quán)值 w1, w2, , 在 F 中選取其根結(jié)點的權(quán)值為最 小的兩棵二叉樹,分別作為左、 右子樹構(gòu)造一棵新的二叉樹,并
3、 置這棵新的二叉樹根結(jié)點的權(quán)值 為其左、右子樹根結(jié)點的權(quán)值之 和;(2) 在 F 中選取其根結(jié)點的權(quán)值為最(2) 從F中刪去這兩棵樹,同時加入 剛生成的新樹; 重復(fù) (2) 和 (3) 兩步,直至 F 中只 含一棵樹為止。(3)(4) 從F中刪去這兩棵樹,同時加入 重復(fù) (29例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 5627527697671395279例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 56713952795271667132900001111000110110111從根結(jié)點到葉子結(jié)點的路徑上分支字符組成的字符串,可以作為每個葉子結(jié)點編碼。約定左分支表示字符0,右
4、分支表示字符1。671395279527166713290000111100 若要設(shè)計不等長的編碼,則必須任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴,這種編碼稱為前綴編碼。三、前綴編碼以傳送的電文為例比較等長編碼和不等長編碼方法:一、等長編碼:電文中所需傳送的字符有A、B、C、D,編碼分別為00、01、10、11,若要發(fā)送ABACCDA電文,則以字符串00010010101100發(fā)送,根據(jù)字符對應(yīng)的編碼,在接收端能知道發(fā)送的電文為ABACCDA。二、不等長編碼:當(dāng)A、B、C、D的編碼分別為0、00、1、10,要發(fā)送上述電文以電文ABACCDA ,相應(yīng)的字符串為000011100
5、,在接收端,對于子串0000的譯法就有多種,可以是AAAA、BB、ABA、BAA等等。 若要設(shè)計不等長的編碼,則必須任何一個字符的編碼都不是同一四、赫夫曼編碼 如何得到使電文 總長最短的二進制前綴編碼呢?假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi,其編碼長度為li,電文中只有n種字符,則電文總長為wili。 對應(yīng)到二叉樹上,置wi為葉子結(jié)點的權(quán),li為根到葉子的路徑長度,則wili恰為二叉樹上帶權(quán)路徑長度。 設(shè)計電文總長最短的二進制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán),設(shè)計一棵赫夫曼樹的問題,由此得到的二進制前綴編碼稱為赫夫曼編碼。 四、赫夫曼編碼 如何得到使電文 總長最短的二進 利用赫夫曼樹可以構(gòu)
6、造一種不等長的二進制編碼,并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼,即使所傳電文的總長度最短。 例62: 利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼,1. 熟練掌握二叉樹的結(jié)構(gòu)特性,了解相應(yīng)的證明方法。2. 熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。3. 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法,靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。1. 熟練掌握二叉樹的結(jié)構(gòu)特性,了解相應(yīng)的證明方法。4. 理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系,熟練掌握二叉樹的線索化
7、過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷,而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。4. 理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的5. 熟悉樹的各種存儲結(jié)構(gòu)及其特點,掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是進行其它操作的前提,因此讀者應(yīng)掌握 1 至 2 種建立二叉樹和樹的存儲結(jié)構(gòu)的方法。6. 學(xué)會編寫實現(xiàn)樹的各種操作的算法。7. 了解最優(yōu)樹的特性,掌握建立最優(yōu)樹和哈夫曼編碼的方法。5. 熟悉樹的各種存儲結(jié)構(gòu)及其特點,掌握樹和森林與二叉樹的復(fù)習(xí)題一棵完全二叉樹上有1001個結(jié)點,其中葉子結(jié)點的個數(shù)是()。250500254
8、505以上答案都不是答案:E復(fù)習(xí)題一棵完全二叉樹上有1001個結(jié)點,其中葉子結(jié)點的個數(shù)是以下說法錯誤的是()存在這樣的二叉樹,對它采用任何次序遍歷其結(jié)點訪問序列均相同。二叉樹是樹的特殊情形。由樹轉(zhuǎn)換成二叉樹,其根結(jié)點的右子樹總是空的。在二叉樹只有一棵子樹的情況下,也要明確指出該子樹是左子樹還是右子樹。答案:B以下說法錯誤的是()樹的基本遍歷策略可分為先根遍歷和后根遍歷,二叉樹的基本遍歷策略分為先序、中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該樹對應(yīng)的二叉樹,則下面()是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同。樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同。樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同。以上均不對。答案:A樹的基本遍歷策略可分為先根遍歷和后根遍歷,二叉樹的基本遍歷策下面幾個符號串編碼集合中,不是前綴編碼的是()。0,10,110,111111,10,001,101,000100,010,0110,1000b,c,aa,ac,aba,abb,abc答案:B下面幾個符號串編碼集合中,不是前綴編碼的是()。對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為(),對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為()。一般二叉樹只有根結(jié)點的二叉樹根結(jié)點無左孩子的二叉樹根結(jié)點無右孩子的二叉樹所有結(jié)點只有左子樹的二叉樹所有結(jié)點只有右子樹
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 金屬制品配送服務(wù)合同模板
- 汽車進口物流合同范本
- 重金屬運輸安全管理協(xié)議
- 2024年護創(chuàng)敷料耗材項目合作計劃書
- 食品加工設(shè)備搬遷協(xié)議
- 山東省淄博市臨淄區(qū)第一中學(xué)2024屆中考數(shù)學(xué)猜題卷含解析
- 礦權(quán)交易法律法規(guī)咨詢協(xié)議
- 高速公路廢料清運合同
- 服裝批發(fā)居間合同委托書
- 美食廣場裝修合同
- 2025屆四川省新高考八省適應(yīng)性聯(lián)考模擬演練 歷史試卷(含答案)
- 跨境電商市場細分方案
- 2024年中國美術(shù)用品市場調(diào)查研究報告
- 2024年遼寧鞍山臺安縣中小學(xué)教師招聘104人歷年高頻500題難、易錯點模擬試題附帶答案詳解
- 2024-2030年中國機器狗行業(yè)市場發(fā)展分析及前景趨勢研究報告
- 翡翠借貨合作協(xié)議書模板
- 離職證明(標(biāo)準(zhǔn)模版)
- 腸梗阻診治及案例分析讀書筆記
- 2024年高考語文新高考Ⅱ卷試題評析及答案詳解(含作文范文)
- 職業(yè)健康工作開展情況的報告
- 2024至2030年中國it外包服務(wù)行業(yè)市場深度分析及發(fā)展趨勢預(yù)測報告
評論
0/150
提交評論