最優(yōu)編碼與譯碼的實現(xiàn).ppt

《最優(yōu)編碼與譯碼的實現(xiàn).ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、2教學目標教學目標1、知識目標1）了解二叉樹的有關概念以及二叉樹的存儲結構；2）了解哈夫曼樹的概念，會生成哈夫曼樹；3）掌握哈夫曼基本操作的實現(xiàn)算法。2、能力目標1）具有恰當?shù)倪x擇二叉樹作為數(shù)據(jù)的邏輯結構和存儲結構的能力；2）具有應用二叉樹解決實際問題的能力。3、素質目標養(yǎng)成善于思考解決實際問題的良好習慣。一、任務描述任務描述：利用哈夫曼編碼進行信息通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼；在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要

2、一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。3二、相關知識（一）二叉樹1．二叉樹的定義和基本運算1．1定義定義：二叉樹是另一種樹形結構。它與樹形結構的區(qū)別是：（1）每個結點最多有兩棵子樹；（2）子樹有左右之分。4二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個結點的有限集合。當n=0時，稱為空二叉樹；當n>0時，有且僅有一個結點為二叉樹的根，其余結點被分成兩個互不相交的子集，一個作為左子集，另一個作為右子集，每個子集又是一個二叉樹。51．2二叉樹的基本運算（1）構造一棵二叉樹CreateBTree(BT)（2）清空

3、以BT為根的二叉樹ClearBTree(BT)（3）判斷二叉樹是否為空BTreeEmpty(BT)（4）獲取給定結點的左孩子和右孩子LeftChild(BT,node)，RightChild(BT,node)（5）獲取給定結點的雙親Parent(BT,node)（6）遍歷二叉樹Traverse(BT)62．二叉樹的性質二叉樹具有下列5個重要的性質?！拘再|1】在二叉樹的第i層上最多有2i-1個結點（i≥1）。證明：二叉樹的第1層只有一個根結點，所以，i=1時，2i-1=21-1=20=1成立。假設對所有的j，1≤j

4、成立。若j=i-1，則第j層上最多有2j-1=2i-2個結點。由于在二叉樹中，每個結點的度最大為2，所以可以推導出第i層最多的結點個數(shù)就是第i-1層最多結點個數(shù)的2倍，即2i-2*2=2i-1。7【性質2】深度為K的二叉樹最多有2K-1個結點（K≥1）。證明：由性質1可以得出，1至K層各層最多的結點個數(shù)分別為：20,21,22,23,...,2K-1。這是一個以2為比值的等比數(shù)列，前n項之和的計算公式為：8【性質3】對于任意一棵二叉樹BT，如果度為0的結點個數(shù)為n0，度為2的結點個數(shù)為n2，則n0=n2+1。證明：假設度為1的結點個數(shù)為n1，結點總數(shù)為

5、n，B為二叉樹中的分支數(shù)。因為在二叉樹中，所有結點的度均小于或等于2，所以結點總數(shù)為：n=n0+n1+n2（1）再查看一下分支數(shù)。在二叉樹中，除根結點之外，每個結點都有一個從上向下的分支指向，所以，總的結點個數(shù)n與分支數(shù)B之間的關系為：n=B+1。又因為在二叉樹中，度為1的結點產生1個分支，度為2的結點產生2個分支，所以分支數(shù)B可以表示為：B=n1+2n2。將此式代入上式，得：n=n1+2n2+1（2）用（1）式減去（2）式，并經過調整后得到：n0=n2+1。9滿二叉樹：如果一個深度為K的二叉樹擁有2K-1個結點，則將它稱為滿二叉樹。10完全二叉樹：有

6、一棵深度為h，具有n個結點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結點按從上到下，從左到右的順序分別進行編號，且該二叉樹中的每個結點分別與滿二叉樹中編號為1~n的結點位置一一對應，則稱這棵二叉樹為完全二叉樹?！拘再|4】具有n個結點的完全二叉樹的深度為?log2n?+1。其中，?log2n?的結果是不大于log2n的最大整數(shù)。證明：假設具有n個結點的完全二叉樹的深度為K，則根據(jù)性質2可以得出：2K-1-1

7、log2n?=K-1。整理后得到：K=?log2n?+1。11【性質5】對于有n個結點的完全二叉樹中的所有結點按從上到下，從左到右的順序進行編號，則對任意一個結點i（1≤i≤n），都有：（1）如果i=1，則結點i是這棵完全二叉樹的根，沒有雙親；否則其雙親結點的編號為?i/2?。（2）如果2i>n，則結點i沒有左孩子；否則其左孩子結點的編號為2i。（3）如果2i+1>n，則結點i沒有右孩子；否則其右孩子結點的編號為2i+1。下面我們利用數(shù)學歸納法證明這個性質。我們首先證明（2）和（3）。當i=1時，若n≥3，則根的左、右孩子的編號分別是2，3；若n<3，

8、則根沒有右孩子；若n<2，則根將沒有左、右孩子；以上對于（2）和（3）均成立。假設：對于所有的