根樹及其應(yīng)用課件

1、二叉樹及其應(yīng)用姓名：李 曲學(xué)院：軟件學(xué)院數(shù)缺形少直覺，形缺數(shù)難入微。華羅庚（19101985）2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)本次課在離散數(shù)學(xué)課的地位離散數(shù)學(xué)是軟件工程本科的計(jì)算機(jī)數(shù)學(xué)專業(yè)必修課。也是唯一的一門計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)課。前面我們學(xué)習(xí)了樹和二叉樹的基本概念。本節(jié)內(nèi)容是關(guān)于樹和根樹的概念深化和重要應(yīng)用。二叉樹及其應(yīng)用是后續(xù)數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、編譯原理等課程的重要基礎(chǔ)。二叉樹同時(shí)也是許多前沿科學(xué)例如演化計(jì)算的重要工具。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)問題的來源對(duì)于同一內(nèi)容的編碼，如果采用多種不同的編碼，其中重碼率最小，編碼長度最短的編碼顯然效率最高。在實(shí)際的通訊和代碼傳輸過程中

2、，我們除了考慮編碼和解碼的準(zhǔn)確率以外，還要常常要考慮編碼和解碼的效率，以及傳輸?shù)男蕟栴}（總的編碼長度問題）。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)一個(gè)通信的實(shí)例假設(shè)我們需要采用二進(jìn)制字符串來傳送一組電文ABACCDA。我們要考慮以下幾個(gè)問題：1.什么樣的編碼能夠解決這個(gè)問題？2.什么樣的編碼效率最高（即總的電文碼長最短）？2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)解決方案A原電文只有ABCD四種字符。如果采用等長二進(jìn)制編碼，我們只需要二位二進(jìn)制編碼即可解決這個(gè)問題。設(shè)ABCD的編碼分別為00，01，10，1100010010101100A B A C C D A優(yōu)點(diǎn)：簡單明了，編碼和譯碼都簡單。

3、缺點(diǎn)：總碼長較長。對(duì)稍大的問題而言，冗余太大。有沒有更短的編碼方案？2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)解決方案B假設(shè)ABCD的編碼分別為0，00，1，01采用不等長編碼。對(duì)電文中出現(xiàn)頻率較高的字母采用盡可能短的編碼，則總電文可減少。A B A C C D A0 00 0 1 1 01 0優(yōu)點(diǎn)：總碼長為9，更短。缺點(diǎn)：解碼時(shí)有歧義。0000譯成AAAA還是ABA還是BB？2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)前綴碼的概念給定一個(gè)序列的集合，若沒有一個(gè)序列是另外一個(gè)序列的前綴，則該集合稱為前綴碼。例如 000,001,01,10,11是前綴碼，而111,00011,000,01就不是前綴碼。2

4、022/7/28軟件學(xué)院李曲離散數(shù)學(xué)解決方案C采用不定長的前綴碼。假設(shè)ABCD的編碼分別為01,000,001,1A B A C C D A01 000 01 001 001 1 01優(yōu)點(diǎn)：譯碼時(shí)不會(huì)產(chǎn)生歧義。缺點(diǎn)：編碼比等長編碼還長，效率太低（16位長度）。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)解決方案D高效的編碼應(yīng)該具備以下兩個(gè)性質(zhì)：編碼要避免歧義（譯碼時(shí)不能出現(xiàn)同一串字符出現(xiàn)多種譯法的情況）。編碼的總長度盡可能短（出現(xiàn)頻率高的字母的碼長盡量短）。滿足以上兩條的編碼方法是否存在？2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)Huffman樹的引入前面我們已經(jīng)學(xué)習(xí)了路徑和路徑長度的概念。學(xué)會(huì)了采用葉

5、節(jié)點(diǎn)的權(quán)值和路徑長度來求樹的權(quán)值。53322W(T) 22335332382+112=22022/7/28軟件學(xué)院李曲離散數(shù)學(xué)最優(yōu)二叉樹的引入上面的二叉樹是不是權(quán)為2,2,3,3,5的最優(yōu)樹？我們可以用Huffman算法來求最優(yōu)樹。如果不是最優(yōu)樹，那么應(yīng)該如何求最優(yōu)樹？在所有帶權(quán)w1,w2, , wt的二叉樹中，w(T)最小的那棵二叉樹稱為最優(yōu)二叉樹（簡稱最優(yōu)樹）。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)Huffman算法給定一組權(quán)值w1,w2,wt,且w1w2 wt。(1)連接權(quán)為w1, w2的兩片樹葉，得到一個(gè)分支點(diǎn)，其權(quán)為w1+w2。(2)在w1+w2,w3,wt中，選出兩個(gè)最小的權(quán)，連接

6、它們對(duì)應(yīng)的頂點(diǎn)，得到新分支點(diǎn)及其所帶的權(quán)。(3)重復(fù)(2)，直到形成t-1個(gè)分支點(diǎn)，t片樹葉為止。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)Huffman算法的實(shí)例求帶權(quán)2，2，3，3，5的最優(yōu)二叉樹。解：對(duì)于2,2,3,3,5，最小的兩個(gè)權(quán)為2,2224得到權(quán)值為3,3,4,5的一個(gè)權(quán)值序列。2022/7/28軟件學(xué)院李曲離散數(shù)學(xué)對(duì)于權(quán)值為3,3,4,5的一個(gè)權(quán)值序列。224336得到權(quán)值為4，5，6的權(quán)值序列。224336592022/7/28軟件學(xué)院李曲離散數(shù)學(xué)最后得到權(quán)值為6，9的權(quán)值序列，得到如下的Huffman樹，即為最優(yōu)樹。1522433659從這個(gè)最優(yōu)二叉樹我們可以看到它的權(quán)為： W(T)2323523232342022/7/28軟件學(xué)院李曲離散數(shù)學(xué)二叉樹和前綴碼的關(guān)系152243365900001111000000101101112022/7/28軟件學(xué)院李曲離散數(shù)學(xué)用Huffman樹求通信問題的D方案1）對(duì)于電文ABACCDA，統(tǒng)計(jì)ABCD出現(xiàn)的頻率。得到ABCD的對(duì)應(yīng)的權(quán)分別為3,1,2,1。原問題轉(zhuǎn)化成為求3，1，2，1為權(quán)的Huffman