數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學院4.5Huffman樹引言IntroductionHuffmanTree，中文名是哈夫曼樹或霍夫曼樹，它是最優(yōu)二叉樹。哈夫曼樹的應用很廣，在不同的應用中葉子結(jié)點的值可以有不同的解釋。當哈夫曼樹應用到信息編碼中，權(quán)值可看成是某個符號出現(xiàn)的頻率：當應用到判定過程中，可看成是某類數(shù)據(jù)出現(xiàn)的頻率；當應用到排序問題中，可看成是已排好次序而待合并的序列的長度等等。Part01Huffman樹基本概念給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達到最小，則這棵樹被稱為哈夫曼樹（HuffmanTree）?；靖拍?/p>

在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。

通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。路徑和路徑長度100和80的路徑長度是1，50和30的路徑長度是2，20和10的路徑長度是3。哈夫曼樹結(jié)點的權(quán)及帶權(quán)路徑長度哈夫曼樹結(jié)點20的路徑長度是3，它的帶權(quán)路徑長度=路徑長度*權(quán)=3*20=60

若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。

結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。樹的帶權(quán)路徑長度哈夫曼樹樹的WPL=1*100+2*50+3*20+3*10=100+100+60+30=290

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。比較兩棵二叉樹WPL哈夫曼樹右邊樹的WPL=1*100+2*50+3*20+3*10=290左邊樹的WPL=2*10+2*20+2*50+2*100=360Part02哈夫曼樹的構(gòu)造假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。n個權(quán)值分別設(shè)為w1、w2、…、wn，哈夫曼樹的構(gòu)造規(guī)則為：將w1、w2、…，wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點)；在森林中選出根結(jié)點權(quán)值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；從森林中刪除選取的兩棵樹，并將新樹加入森林；重復

、

步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼樹的構(gòu)造規(guī)則哈夫曼樹的構(gòu)造以{5,6,7,8,15}為例，來構(gòu)造一棵哈夫曼樹哈夫曼樹的構(gòu)造哈夫曼樹構(gòu)造實例步驟一哈夫曼樹構(gòu)造實例步驟二哈夫曼樹構(gòu)造實例步驟三以{5,6,7,8,15}為例，來構(gòu)造一棵哈夫曼樹哈夫曼樹的構(gòu)造哈夫曼樹構(gòu)造實例步驟四哈夫曼樹構(gòu)造實例步驟五創(chuàng)建哈夫曼樹-算法實現(xiàn)哈夫曼樹的構(gòu)造算法實現(xiàn)//創(chuàng)建哈夫曼樹public

voidcreateTree(){

//創(chuàng)建優(yōu)先隊列Queue<Node>q1=newPriorityQueue<Node>(

newComparator<Node>(){

public

intcompare(Nodeo1,Nodeo2){

return

o1.count-o2.count; }});

//將結(jié)點列表加入到隊列中

q1.addAll(nodes);

//如果隊列不為空

while(!q1.isEmpty()){

//出隊一個結(jié)點 Noden1=q1.poll();

//出隊一個結(jié)點 Noden2=q1.poll();

//通過兩個結(jié)點創(chuàng)建父節(jié)點Nodeparent=newNode(n1,n2,n1.count+n2.count);

//如果隊列為空

if(q1.isEmpty()){

root=parent;

return;}

//將父節(jié)點加入到隊列中

q1.add(parent);}}Part03Huffman樹的應用1.優(yōu)化判斷過程Huffman樹的應用

將百分制轉(zhuǎn)換成五級制的算法。顯然，此算法很簡單，只需利用if語句描述即可。

如果學生規(guī)模很大，該算法需反復多次執(zhí)行，就應該考慮算法執(zhí)行的時間問題。在實際應用中，學生的成績呈正態(tài)分布，大部分在70~89分之間，優(yōu)秀和不及格的概率較小。假設(shè)不及格、及格、中、良、優(yōu)的百分比為5％、12%、40%、35%、8%，則上述算法80%以上的成績需要進行三次或三次以上的比較才能得到結(jié)果。1.優(yōu)化判斷過程Huffman樹的應用

若以這些百分比值5,12,40,35,8為權(quán)值，使用哈夫曼算法來構(gòu)造一棵判定樹，則得到的判定過程，可使多數(shù)成績經(jīng)過較少的比較即可得到結(jié)果。

未使用哈夫曼樹判定

使用哈夫曼樹判定2.哈夫曼編碼Huffman樹的應用

在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進制的字符串，用0，1碼的不同排列來表示字符。需傳送的報文為“AFTER

DATA

EARAREARTAREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為{8，4，5，3，1，1}，現(xiàn)要求為這些字母設(shè)計編碼。要區(qū)別6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分別用000、001、010、011、100、101對“A，E，R，T，F(xiàn)，D”進行編碼發(fā)送。算法分析在實際應用中，各個字符的出現(xiàn)頻度或使用次數(shù)是不相同的，讓使用頻率高的用短碼，使用頻率低的用長碼，以優(yōu)化整個報文編碼。（非等長編碼）設(shè)計時能夠保證任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴，符合此要求的編碼稱為前綴編碼。2.哈夫曼編碼Huffman樹的應用public

classTreeNode{ Characterch;//ch存儲當前結(jié)點字符

int

val;

//若在構(gòu)建二叉樹的過程中該結(jié)點為左結(jié)點，則val=0,反之，val=1

int

freq;//存儲字符出現(xiàn)的頻次 TreeNodeleft;//左結(jié)點 TreeNoderight;//右結(jié)點

public

TreeNode(){

}

結(jié)點數(shù)據(jù)結(jié)構(gòu)有參數(shù)構(gòu)造方法publicTreeNode(Characterch,int

val,int

freq,TreeNodeleft,TreeNoderight){

this.ch=ch;

this.val=val;

this.freq=freq;

this.left=left;

this.right=right; }}2.哈夫曼編碼Huffman樹的應用初始化二叉樹結(jié)點判斷表空

選擇最小頻率的兩個結(jié)點組成一顆二叉樹2.哈夫曼編碼Huffman樹的應用選擇最小頻率的兩個結(jié)點組成二叉樹判斷表空哈夫曼編碼最終二叉樹2.哈夫曼編碼Huffman樹的應用判斷表空字符哈夫曼編碼表使用哈夫曼編碼的報文的最短傳送長度為：

6

L=WPL=(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51

k=1若采用等長編碼，報文的傳送長度為：L=8×3+4×3+5×3+3×3+1×3+1×3=662.哈夫曼編碼Huffman樹的應用//遍歷dataMap,初始化二叉樹結(jié)點，并將所有初始化后的結(jié)點放到nodeList中，并進行排序LinkedList<TreeNode>nodeList=newLinkedList<TreeNode>();for(Map.Entry<Character,Integer>entry:dataMap.entrySet()){ Characterch=entry.getKey();

int

freq=entry.getValue();

int

val=0; TreeNodetmp=newTreeNode(ch,val,freq,null,null);

odeList.add(tmp);}//對存放結(jié)點的鏈表進行排序，方便后續(xù)進行組合Collections.sort(nodeList,newComparator<TreeNode>(){

public

intcompare(TreeNodet1,TreeNodet2){

return

t1.freq-t2.freq; } });while(nodeList.size()>0){TreeNodet1=nodeList.removeFirst();TreeNodet2=nodeList.removeFirst();

//左子樹的val賦值為0，右子樹的val賦值為1

t1.val=0;

t2.val=1;

//將取出的兩個結(jié)點進行合并

if(nodeList.size()==0){//此時代表所有結(jié)點合并完畢，返回結(jié)果

root=newTreeNode(null,0,t1.freq+t2.freq,t1,t2);}else{

//此時代表還有可以合并的結(jié)點TreeNodetmp=newTreeNode(null,0,t1.freq+t2.freq,t1,t2);

if(tmp.freq>nodeList.getLast().freq){

nodeList.addLast(tmp); }else{ for(int

i=0;i<nodeList.size();i++){

int

tmpFreq=tmp.freq;

if(tmpFreq<=nodeList.get(i).freq){

nodeList.add(i,tmp);

break; }