哈夫曼樹:給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達 -百科知識中文網

基本術語

哈夫曼樹又稱為最優樹.
哈夫曼樹
1、路徑和路徑長度
在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。
2、結點的權及帶權路徑長度
若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
3、樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為wpl。

結構構造

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合併，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重複(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

相關套用

哈夫曼編碼

在數據通信中，需要將傳送的文字轉換成二進制的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的報文為“AFTER DATA EAR ARE ART AREA”，這裡用到的字元集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進制編碼方式是等長編碼，固定採用3位二進制，可分別用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼傳送，當對方接收報文時再按照三位一分進行解碼。顯然編碼的長度取決報文中不同字元的個數。若報文中可能出現26個不同字元，則固定編碼長度為5。然而，傳送報文時總是希望總長度儘可能短。在實際套用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高於X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以最佳化整個報文編碼。
為使不等長編碼為前綴編碼(即要求一個字元的編碼不能是另一個字元編碼的前綴)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，求出此樹的最小帶權路徑長度就等於求出了傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大檔案中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。
哈夫曼解碼
在通信中，若將字元用哈夫曼編碼形式傳送出去，對方接收到編碼後，將編碼還原成字元的過程，稱為哈夫曼解碼。

程式實現

Basic
VERSION 1.0 CLASS
BEGIN
MultiUse = -1 'True
Persistable = 0 'NotPersistable
DataBindingBehavior = 0 'vbNone
DataSourceBehavior = 0 'vbNone
MTSTransactionMode = 0 'NotAnMTSObject
END
Attribute VB_Name = "clsBinTree"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = True
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
Private Type BinTreeType
LChild As Integer
RChild As Integer
Parents As Integer

Power As Long
End Type
Private BinTree() As BinTreeType
Public UB As Integer
Public Sub InitData(Power As Long, LChild As Integer, RChild As Integer)
If UB = 0 Then UB = 1
ReDim Preserve BinTree(1 To UB)
BinTree(UB).Power = Power
BinTree(UB).LChild = LChild
BinTree(UB).RChild = RChild
UB = UB + 1
End Sub
Private Sub Min(Min1 As Integer, Min2 As Integer, ErrTag As Integer)
Dim P As Integer, Q As Integer
P = 1
While BinTree(P).Parents > 0
P = P + 1
Wend
For I = P + 1 To UB - 1
If BinTree(I).Power < BinTree(P).Power And BinTree(I).Parents = 0 Then P = I
Next
Q = 1
While BinTree(Q).Parents > 0 Or Q = P
Q = Q + 1
If Q = UB Then
ErrTag = 1
Exit Sub
End If
Wend
ForI=Q+1ToUB-1
IfBinTree(I).Power<BinTree(Q).PowerAndQ<>PAndBinTree(I).Parents=0ThenQ=I
Next
Min1=P:Min2=Q:ErrTag=0
EndSub
PublicSubHuffman()
DimErrorHappenAsInteger
DimMin1AsInteger,Min2AsInteger
DimIAsInteger
MinMin1,Min2,ErrorHappen
DoUntilErrorHappen
InitDataBinTree(Min1).Power+BinTree(Min2).Power,Min1,Min2
BinTree(Min1).Parents=UB-1
BinTree(Min2).Parents=UB-1
MinMin1,Min2,ErrorHappen
Loop
EndSub
PublicFunctionHuffmanCode(IAsInteger)AsString
HuffmanCode=I&",LChild:"&BinTree(I).LChild&"RChild:"&BinTree(I).RChild&"Parents:"&BinTree(I).Parents&"Power:"&BinTree(I).Power
EndFunction
AttributeVB_Name="Module1"
PublicHTAsNewclsBinTree
PrivateWordAsString,Ping()AsInteger,PUBAsInteger
PublicSubCreatHT(WordsAsString)
DimTempAsString,IAsInteger
Word=""
ForI=1ToLen(Words)
Temp=Mid(Words,I,1)
P=InStr(1,Word,Temp)
IfP>0Then
Ping(P-1)=Ping(P-1)+1
Else
Word=Word&Temp
ReDimPreservePing(PUB)
Ping(PUB)=1
PUB=PUB+1
EndIf
Next
Form1.Text2.SelText=Word&vbCrLf
ForI=0ToPUB-1
Form1.Text2.SelText=Ping(I)&","
HT.InitDataCLng(Ping(I)),0,0
Next
Form1.Text2.SelText=vbCrLf&vbCrLf
HT.Huffman
ForI=1ToHT.UB-1
Form1.Text2.SelText=HT.HuffmanCode(I)&vbCrLf
Next
EndSub
Pascal
Programhuffman_tree(input,output);
constmax=32767;n=20;m=2*n-1
Typetnode=RECORD
data:integer;
Lc,Rc:integer;
END;
Vartree:ARRAY[0..m]oftnode;
weight:ARRAY[0..n]ofinteger;
im,num:integer;
procedureinitial;
vari:integer;
begin
write('Firstinputnun(<',n:2,')');
readln(num);
writeln('Pleaseinputweight:');
fori:=0tonum-1doread(weight[i])
end;
functionminimum:integer;
vari:integer;
begin
min:=max;
fori:=0tonum-1do
if(min>weight[i])then
begin
min:=weight[i];
im:=i;
end;
weight[im]:=max;
minimum:=min;
end;
procedurehuffman;
vari,k:integer;
begin
fori:=numto2*num-1do
begin
tree[i].Lc:=minimum;
tree[i].Rc:=minimum;
tree[i].data:=tree[i].Lc:+tree[i].Rc;
weight[im]:=tree[i].data
end;
writeln;
writeln('Theresultofhuffmantree:');
k:=1;
fori:=2*num-2downtonumdo
begin
write(tree[i].data:6,':',tree[i].Lc:3,tree[i].Rc:3);
if(kmod3=0)thenwriteln;k:=k+1;
end
writeln
end;
procedureprintd;
vari:integer;
begin
write('Theweightoftree:');
fori:=0tonum-1do
write{weight[i]:3}
end;
begin{main}
initial;
printd;
huffman
end.
C++
#include
#include
usingnamespacestd;
constintMaxValue=10000;//初始設定的權值最大值
constintMaxBit=4;//初始設定的最大編碼位數
constintMaxN=10;//初始設定的最大結點個數
structHaffNode//哈夫曼樹的結點結構
{
intweight;//權值
intflag;//標記
intparent;//雙親結點下標
intleftChild;//左孩子下標
intrightChild;//右孩子下標
};
structCode//存放哈夫曼編碼的數據元素結構
{
intbit[MaxN];//數組
intstart;//編碼的起始下標
intweight;//字元的權值
};
voidHaffman(intweight[],intn,HaffNodehaffTree[])
//建立葉結點個數為n權值為weight的哈夫曼樹haffTree
{
intj,m1,m2,x1,x2;
//哈夫曼樹haffTree初始化。n個葉結點的哈夫曼樹共有2n-1個結點
for(inti=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weight[i];
elsehaffTree[i].weight=0;
haffTree[i].parent=0;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
//構造哈夫曼樹haffTree的n-1個非葉結點
for(inti=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else
if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
//將找出的兩棵權值最小的子樹合併為一棵子樹
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
}
}
voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[])
//由n個結點的哈夫曼樹haffTree構造哈夫曼編碼haffCode
{
Code*cd=newCode;
intchild,parent;
//求n個葉結點的哈夫曼編碼
for(inti=0;i<n;i++)
{
cd->start=n-1;//不等長編碼的最後一位為n-1
cd->weight=haffTree[i].weight;//取得編碼對應權值的字元
child=i;
parent=haffTree[child].parent;
//由葉結點向上直到根結點
while(parent!=0)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;//左孩子結點編碼0
else
cd->bit[cd->start]=1;//右孩子結點編碼1
cd->start--;
child=parent;
parent=haffTree[child].parent;
}
//保存葉結點的編碼和不等長編碼的起始位
for(intj=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start;
haffCode[i].weight=cd->weight;//保存編碼對應的權值
}
}
intmain()
{
inti,j,n=4;
intweight[]={1,3,5,7};
HaffNode*myHaffTree=newHaffNode[2*n+1];
Code*myHaffCode=newCode[n];
if(n>MaxN)
{
cout<<"定義的n越界，修改MaxN!"<<endl;
exit(0);
}
Haffman(weight,n,myHaffTree);
HaffmanCode(myHaffTree,n,myHaffCode);
//輸出每個葉結點的哈夫曼編碼
for(i=0;i<n;i++)
{
cout<<"Weight="<<myHaffCode[i].weight<<"Code=";
for(j=myHaffCode[i].start+1;j<n;j++)
cout<<myHaffCode[i].bit[j];
cout<<endl;
}
return0;
}
C
#include
#include
#defineN8
typedefstructnode{
intitem;
structnode*l;
structnode*r;
}*link;
link*h;
intNq=N;
linkNODE(intitem,linkl,linkr)
{
linkt=malloc(sizeof*t);
t->l=l;
t->r=r;
t->item=item;
returnt;
}
voidshif_up(inti)
{
intj;
while(i>1)
{
j=i/2;
if()
}
}
voidinsert(linkt)
{
h[++Nq]=t;
shif_up(Nq);
}
linkdelmin()
{
swap(1,Nq--);
shif_down(1,Nq);
returnh[Nq+1];
}
linkcreat_heap(intfreq,intlen)
{
inti;
for(i=0;i<len;i++)
h[i]=NODE(freq[i],NULL,NULL);
for(i=N/2;i>=0;i--)
shif_down(i,N);}
voidhuffman(intfreq[],intlen)
{
h=malloc(len*sizeof(link));
creat_heap(h,freq,len);
while(Nq>1)
{
linkt1=delmin();
linkt2=delmin();
insert(NODE(t1->item+t2->item,t1,t2));
}
}
intmain(void)
{
intfreq[N]={5,29,7,8,14,23,3,11};
huffman(freq,N);
return0;
}

哈夫曼樹

基本信息

基本術語

結構構造

相關套用

哈夫曼編碼

哈夫曼解碼

程式實現

相關搜尋

熱門詞條