爱华网给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。于是对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式,然后再按照哈夫曼树的方法进行构造即可。
哈夫曼树_哈夫曼树 -基本术语
哈夫曼树又称为最优树.哈夫曼树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个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。
哈夫曼译码
在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。哈夫曼树_哈夫曼树 -程序实现
BasicVERSION 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;
}
