數(shù)據(jù)結構（雙語）21-22-實驗四（下）-數(shù)組實現(xiàn)哈夫曼樹

DataStructure

數(shù)據(jù)結構計算機與信息技術系袁瑩Email:yuanying8011@163.com

2016年5月16日課件下載FTP://用戶名：yuanyings下載：課件下載/數(shù)據(jù)結構/實驗/21-22-實驗四（下）.pptx學號_姓名_04實驗報告.doc實驗四（下）-哈夫曼樹的建立和編碼-空白模板.c將VC中的字體調(diào)大：Tools->Options->Format

實驗項目名稱：二叉樹的基本操作及應用實驗目的：實現(xiàn)二叉樹的建立、刪除操作，實現(xiàn)二叉樹的四種遍歷方法，要求建立哈夫曼樹，并實現(xiàn)哈夫曼編碼。實驗步驟（1）二叉樹的建立要求實現(xiàn)二叉樹的建立與輸出操作，可以任選存儲結構。（2）樹的遍歷要求實現(xiàn)二叉樹的前序、中序、后序和層次遍歷。（3）二叉樹的葉子和深度。要求計算二叉樹的葉子節(jié)點個數(shù)和深度。（4）二叉樹的應用要求建立哈夫曼樹，并實現(xiàn)哈夫曼編碼。哈夫曼樹一、哈夫曼樹的定義及建立結點的路徑長度就是從根結點到每個結點的路徑長度，其值為路經(jīng)上的結點數(shù)減1。賦予了權值的結點的路徑長度與該結點權值的乘積即為結點的帶權路徑長度（WeightedPathLengthofNode）。樹的帶權路徑長度（WeightedPathLengthofTree，縮寫為WPL）定義為：樹中所有葉子結點的帶權路徑長度之和，記為：其中n表示葉子結點數(shù)，wi表示第i個葉子結點的權值，li代表第i個葉子結點的路徑長度。WPLa=2×2+3×2+6×2+8×2=38WPLb=8×1+6×2+2×3+3×3=35WPLc=2×1+6×3+8×3+3×2=50WPLd=8×1+2×3+3×3+6×2=35哈夫曼樹（HuffmanTree）又稱最優(yōu)二叉樹，是在含有n個葉子結點，權值分別為w1，w2，……，wn的所有二叉樹中，帶權路徑長度WPL最小的二叉樹。哈夫曼（D.A.Huffman）在上世紀五十年代初便提出了一個非常簡單的算法來建立哈夫曼樹，其算法描述如下：（1）將給定的n個權值{w1，w2，...，wn}作為n個根結點的權值，構造一個具有n棵二叉樹的森林{T1，T2，...，Tn}，其中每棵二叉樹只有一個根結點；（2）在森林中選取兩棵根點權值最小的二叉樹分別作為左、右子樹，增加一個新結點作為根，從而將兩棵樹合并成一棵樹，新根結點的權值為左右子樹根結點權值之和。森林中因此也減少了一棵樹；（3）重復上面步驟（2）的處理過程，直到森林中只有一棵二叉樹為止，這棵二叉樹就是哈夫曼樹。構造過程從哈夫曼樹構造過程和生成結果可知，哈夫曼樹具有以下特點：（1）哈夫曼樹不唯一。（2）哈夫曼樹中只包含度為0和度為2的結點。（3）樹中權值越大的葉子結點離根結點越近。例5.1

假設樹中葉子結點的權值為{5,29,7,8,14,23,3,11}，構造一棵哈夫曼樹。（1）將給定的8個權值作為根結點，構造具有8棵樹的森林（2）從森林中選取根點權值最小的兩棵二叉樹3、5，分別作為左右子樹，構造一棵新的二叉樹，新樹根點權值為8，森林中減少一棵樹。（3）重復步驟（2），直到森林中只剩一棵二叉樹為止。為方便查找雙親，將哈夫曼樹的存儲結構設計為三叉鏈表。每個結點包含四個域：weight為結點的權值，lchild、rchild、parent分別為左、右孩子和雙親結點的指針。含有N個葉子結點的哈夫曼樹共有2N-1個結點，由此可定義一個長度為2N-1的數(shù)組tree來存儲哈夫曼樹，下標從1開始，0代表指針空（NULL）。weightparentlchildrchild結構體聲明#defineN7 /*葉子結點數(shù)*/#defineM2*N-1 /*總結點數(shù)*/typedefstruct /*哈夫曼樹結點的存儲結構*/{ floatweight; /*結點的權值*/ intparent; /*雙親在數(shù)組中的下標*/intlchild,rchild; /*左、右孩子在數(shù)組中的下標，

葉結點的這兩個指針值為0*/}HufmTree;HufmTreetree[M+1];/*哈夫曼樹為靜態(tài)鏈表，下標為0的單元空出*/

在上述存儲結構上實現(xiàn)哈夫曼算法的過程如下：（1）將哈夫曼樹數(shù)組tree中的2N-1個結點初始化：即將各結點的權值、雙親、左孩子、右孩子均置為0。（2）讀入N個葉子結點的權值，分別存入數(shù)組tree[i]（1≤i≤N）的權值域中，構造包含N棵樹的初始森林，森林中的每棵樹只有一個根結點。（3）循環(huán)N-1次，對森林中的樹進行N-1次合并，產(chǎn)生N-1個新結點，依次放入數(shù)組tree[i]中（N+1≤i≤2N-1）。每次合并的步驟是：①在當前森林的所有結點tree[j]（1≤j≤i-1）中，選取具有最小權值和次小權值的兩個根結點（parent域為0的結點），分別用p1和p2記住這兩個根結點在數(shù)組tree中的下標。②將根為tree[p1]和tree[p2]的兩棵樹合并，使其成為新結點tree[i]的左、右孩子，得到一棵以新結點tree[i]為根的二叉樹即將tree[i].weight賦值為tree[p1].weight和tree[p2].weight之和tree[i]的左指針賦值為p1；tree[i]的右指針賦值為p2；同時將tree[p1]和tree[p2]的雙親域均賦值為i，使其指向新結點tree[i]即它們在當前森林中已不再是根結點。

哈夫曼樹的建立以權值{2,3,6,8}為例，分析上述的構造哈夫曼樹的實現(xiàn)算法。wplr012000230003600048000500006000070000wplr012500235003600048000550126000070000wplr0125002350036600480005561261105370000wplr01250023500366004870055612611753719046(a)初始森林(b)第一次合并(c)第二次合并(d)第三次合并二、哈夫曼編碼及譯碼在進行文字傳輸時，數(shù)據(jù)通信的發(fā)送方需要將原文中的每一個文字轉換成對應的二進制0、1序列（編碼）進行發(fā)送，接收方接收到二進制的0、1串后再還原成原文（譯碼）。其編碼和譯碼的過程如下所示：原文

電文（二進制的0、1序列）

原文常用的編碼方式有兩種：等長編碼和不等長編碼。等長編碼：ASCⅡ碼，其特點是每個字符的編碼長度相同。編碼簡單且具有唯一性，當字符集中的字符在電文中出現(xiàn)的頻度相等時，它是最優(yōu)的編碼。不等長編碼：字符的編碼長度不等，因此稱這種編碼方式為不等長編碼。為了使譯碼唯一，則要求字符集中任一字符的編碼都不是其他字符編碼的前面一部分，這種編碼叫做前綴（編）碼。利用二叉樹來對葉子結點進行編碼，所得的編碼一定為前綴碼。若要使報文總長最短，則利用哈夫曼樹對葉子結點進行編碼一定是最優(yōu)的編碼。哈夫曼編碼的實現(xiàn)方法如下：（1）利用字符集中每個字符的使用頻度作為權值構造一個哈夫曼樹；（2）從根結點開始，與左孩子的連線標上0，與右孩子的連線標上1；（3）由根到某葉子結點的路經(jīng)上的0、1序列組成該葉子結點的編碼。例5.2

假設有一個字符集包含8個字符：{a,b,c,d,e,f,g,h}，每個字符的使用頻度（權值）分別為{5,29,7,8,14,23,3,11}，為每個字符設計哈夫曼編碼。字符編碼a0001b10c1110d1111e110f01g0000h001哈夫曼編碼的實現(xiàn)算法首先根據(jù)字符的權值構建哈夫曼樹，然后從每個葉子結點開始不斷的向上搜索雙親結點，直到根點為止，得出字符的哈夫曼編碼。編碼的