數(shù)據(jù)結(jié)構(gòu)（雙語(yǔ)）21-22-實(shí)驗(yàn)四（下）-數(shù)組實(shí)現(xiàn)哈夫曼樹

DataStructure

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)與信息技術(shù)系袁瑩Email:yuanying8011@163.com

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

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

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

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

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

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

電文（二進(jìn)制的0、1序列）

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

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