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

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

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

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

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

5、總數(shù)為： n=n0+n1+n2 （1） 再查看一下分支數(shù)。在二叉樹中，除根結(jié)點之外，每個結(jié)點都有一個從上向下的分支指向，所以，總的結(jié)點個數(shù)n與分支數(shù)B之間的關(guān)系為：n=B+1。 又因為在二叉樹中，度為1的結(jié)點產(chǎn)生1個分支，度為2的結(jié)點產(chǎn)生2個分支，所以分支數(shù)B可以表示為：B=n1+2n2。 將此式代入上式，得： n=n1+2n2+1 （2） 用（1）式減去（2）式，并經(jīng)過調(diào)整后得到：n0=n2+1。,9,滿二叉樹：如果一個深度為K的二叉樹擁有2K-1個結(jié)點，則將它稱為滿二叉樹。,10,完全二叉樹：有一棵深度為h，具有n個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右

6、的順序分別進行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1n的結(jié)點位置一一對應，則稱這棵二叉樹為完全二叉樹。,【性質(zhì)4】 具有n個結(jié)點的完全二叉樹的深度為 log2n+1。其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)。 證明：假設具有n個結(jié)點的完全二叉樹的深度為K，則根據(jù)性質(zhì)2可以得出： 2K-1-1n2K-1 將不等式兩端加1得到： 2K-1n2K 將不等式中的三項同取以2為底的對數(shù)，并經(jīng)過化簡后得到： K-1log2nK 由此可以得到：log2n =K-1。整理后得到：K= log2n+1。,11,【性質(zhì)5】 對于有n個結(jié)點的完全二叉樹中的所有結(jié)點按從上到下，從左到右的順序

7、進行編號，則對任意一個結(jié)點i （1in），都有： （1）如果i=1，則結(jié)點i是這棵完全二叉樹的根，沒有雙親；否則其雙親結(jié)點的編號為 i/2。 （2）如果2in，則結(jié)點i沒有左孩子；否則其左孩子結(jié)點的編號為2i。 （3）如果2i+1n，則結(jié)點i沒有右孩子；否則其右孩子結(jié)點的編號為2i+1。 下面我們利用數(shù)學歸納法證明這個性質(zhì)。 我們首先證明（2）和（3）。 當i=1時，若n3，則根的左、右孩子的編號分別是2，3；若n3，則根沒有右孩子；若n2，則根將沒有左、右孩子；以上對于（2）和（3）均成立。 假設：對于所有的1ji 結(jié)論成立。即：結(jié)點j的左孩子編號為2j；右孩子編號為2j+1。,12,13,

8、由完全二叉樹的結(jié)構(gòu)可以看出：結(jié)點i+1或者與結(jié)點i同層且緊鄰i結(jié)點的右側(cè)，或者i位于某層的最右端，i+1位于下一層的最左端。 可以看出，i+1的左、右孩子緊鄰在結(jié)點i的孩子后面，由于結(jié)點i 的左、右孩子編號分別為2i和2i+1，所以，結(jié)點i+1的左、右孩子編號分別為2i+2和2i+3，經(jīng)提取公因式可以得到：2(i+1)和2(i+1)+1，即結(jié)點i+1的左孩子編號為2(i+1)；右孩子編號為2(i+1)+1。 又因為二叉樹由n個結(jié)點組成，所以，當2(i+1)+1n，且2(i+1)=n時，結(jié)點i+1只有左孩子，而沒有右孩子；當2(i+1)n，結(jié)點i+1既沒有左孩子也沒有右孩子。 以上證明得到（2）

9、和（3）成立。,下面利用上面的結(jié)論證明（1）。 對于任意一個結(jié)點i，若2in，則左孩子的編號為2i，反過來結(jié)點2i的雙親就是i，而 2i/2=i；若2i+1n，則右孩子的編號為2i+1，反過來結(jié)點2i+1的雙親就是i，而 (2i+1)/2 =i，由此可以得出（1）成立。,14,3二叉樹的存儲結(jié)構(gòu) 二叉樹也可以采用兩種存儲方式：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 31 順序存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)適用于完全二叉樹。其存儲形式為：用一組連續(xù)的存儲單元按照完全二叉樹的每個結(jié)點編號的順序存放結(jié)點內(nèi)容。下面是一棵二叉樹及其相應的存儲結(jié)構(gòu)。,15,在C語言中，這種存儲形式的類型定義如下所示： #define MA

10、X_TREE_NODE_SIZE 100 typedef struct EntryType itemMAX_TREE_NODE_SIZE; /根存儲在下標為1的數(shù)組單元中 int n; /當前完全二叉樹的結(jié)點個數(shù) QBTree; 這種存儲結(jié)構(gòu)的特點是空間利用率高、尋找孩子和雙親比較容易。下面我們給出完全二叉樹在這種存儲形式下的操作算法。,16,（1）構(gòu)造一棵完全二叉樹 void CreateBTree(QBTree *BT,EntryType item ,int n) if (n=MAX_TREE_NODE_SIZE) n=MAX_TREE_NODE_SIZE-1; for (i=1; iit

11、emi=itemi; BT-n=n; （2）獲取給定結(jié)點的左孩子 int LeftCHild(QBTree BT,int node) if (2*nodeBT.n) return 0; else return 2*node; ,17,（3）獲取給定結(jié)點的雙親 int Parent(QBTree BT,int node) if (1=node ,18,32 鏈式存儲結(jié)構(gòu) 在順序存儲結(jié)構(gòu)中，利用編號表示元素的位置及元素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就應該考慮使用鏈式存儲結(jié)構(gòu)。 常見的二叉樹結(jié)點結(jié)

12、構(gòu)如下所示：,19,其中，Lchild和Rchild是分別指向該結(jié)點左孩子和右孩子的指針，item是數(shù)據(jù)元素的內(nèi)容。,在C語言中的類型定義為： typedef struct BTNode EntryType item; struct BTNode *Lchild,*Rchlid;BTNode,*BTree; 下面是一棵二叉樹及相應的鏈式存儲結(jié)構(gòu),20,21,這種存儲結(jié)構(gòu)的特點是尋找孩子結(jié)點容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個結(jié)點添加一個指向雙親結(jié)點的指針域，其結(jié)點結(jié)構(gòu)如下所示。 有關(guān)二叉樹在鏈式存儲結(jié)構(gòu)下的操作算法將在隨后介紹。,4 遍歷二叉樹 二叉樹是一種非線性的數(shù)據(jù)結(jié)

13、構(gòu)，在對它進行操作時，總是需要逐一對每個數(shù)據(jù)元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結(jié)點一次且僅一次的過程。這里的訪問可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。 二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進行訪問；另一類按層次訪問。下面我們將分別進行討論。,22,41 按根、左子樹和右子樹三部分進行遍歷 遍歷二叉樹的順序存在下面6種可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三種順序在左右

14、子樹之間均是先右子樹后左子樹，這與人們先左后右的習慣不同，因此，往往不予采用。余下的三種順序TLR、LTR和LRT根據(jù)根訪問的位置不同分別被稱為先序遍歷、中序遍歷和后序遍歷。,23,（1）先序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 訪問根結(jié)點； 先序遍歷左子樹； 先序遍歷右子樹。 （2）中序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 中序遍歷左子樹； 訪問根結(jié)點； 中序遍歷右子樹。 （3）后序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點。,24,25,下面是一棵二叉樹及其經(jīng)過三種遍歷得到的相應序列。,（1）先序遍歷遞歸算法 void PreOrder

15、(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); （2）中序遍歷遞歸算法 void InOrder(BTree BT) if (BT) InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); （3）后序遍歷遞歸算法 void PostOrder(BTree BT) if (BT) PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); ,26,5. 哈夫曼樹 5.1哈夫曼樹的定義,27,構(gòu)造哈夫曼樹的過

16、程： （1）將給定的n個權(quán)值w1,w2,.,wn作為n個根結(jié)點的權(quán)值構(gòu)造一個具有n棵二叉樹的森林T1,T2,.,Tn，其中每棵二叉樹只有一個根結(jié)點； （2）在森林中選取兩棵根結(jié)點權(quán)值最小的二叉樹作為左右子樹構(gòu)造一棵新二叉樹，新二叉樹的根結(jié)點權(quán)值為這兩棵樹根的權(quán)值之和； （3）在森林中，將上面選擇的這兩棵根權(quán)值最小的二叉樹從森林中刪除，并將剛剛新構(gòu)造的二叉樹加入到森林中； （4）重復上面（2）和（3），直到森林中只有一棵二叉樹為止。這棵二叉樹就是哈夫曼樹。,28,5.3前綴編碼 在電文傳輸中，需要將電文中出現(xiàn)的每個字符進行二進制編碼。在設計編碼時需要遵守兩個原則：（1）發(fā)送方傳輸?shù)亩M制編碼，到

17、接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣；（2）發(fā)送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。 （1）等長編碼 這種編碼方式的特點是每個字符的編碼長度相同（編碼長度就是每個編碼所含的二進制位數(shù)）。假設字符集只含有4個字符A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。若現(xiàn)在有一段電文為：ABACCDA，則應發(fā)送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文后，將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度并不是最短的。,29,（2）不等長編碼 在傳送電文時，為了使其二進制位數(shù)盡可能地

18、少，可以將每個字符的編碼設計為不等長的，使用頻度較高的字符分配一個相對比較短的編碼，使用頻度較低的字符分配一個比較長的編碼。例如，可以為A，B，C，D四個字符分別分配0，00，1，01，并可將上述電文用二進制序列：000011010發(fā)送，其長度只有9個二進制位，但隨之帶來了一個問題，接收方接到這段電文后無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，因此這種編碼方法不可使用。 有了以上這些準備知識，就可以完成這項最優(yōu)編碼與譯碼的實現(xiàn)任務了。,30,1、主要算法的基本思想 A、編碼算法： 1）根據(jù)輸入的數(shù)據(jù)，從中選取兩棵根結(jié)點權(quán)值最小且沒有被選過的樹作為左

19、右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為左右子樹上根結(jié)點的權(quán)值之和。 2）哈夫曼樹已經(jīng)建立后，從葉子到根逆向求每一個字符的哈夫曼編碼。 B、譯碼算法： 譯碼的過程是分解電文中的字符串，從根出發(fā)，如果為字符0就找左孩子，如果為字符1就找右孩子，直至葉子結(jié)點，得到該子串相應的字符并輸出。,31,三、任務分析,2、存儲結(jié)構(gòu) typedef struct int weight; int flag; int parent; char ch; int lchild; int rchild; HafNode; typedef struct int bitMAX; int start; int weight; char ch; Code;,32,四、任務分解,任務8.1：初始化。從終端讀入字符集大小n，及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree中。 任務8.2：編碼。利用已建好的哈夫曼樹，對文件tobetrans中的正文進行編碼，將結(jié)果存入文件codefile中。 任務8.3：譯碼。利用已建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結(jié)果存入textfile中。