哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树
给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长
哈夫曼树 (3张)
度为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，自然会想到设计编码时，让
哈夫曼树 (4张)
使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。
2、哈夫曼译码
在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。
以前写的，证明最优子结构，随便一本算法书上就有.#include<stdio.h>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
tt=(a)(a)=(b)(b)=t}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj
int
pl
struct
cjys
*left
struct
cjys
*right
}cjystypedef
struct
cjdl
{
int
size
int
leapsize
cjys
*p
}cjdl
cjys
*fpnn(void)
void
input(cjdl
*p)
cjys
*fpnn(void)
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
void
rd(cjdl
*p,
cjys
tp)
cjys
cd(cjdl
*p)
void
hbs(cjdl
*p)
cjys
*cjs(cjdl
*p)
void
bls(cjys
*p,int
*jl,
int
i)
void
disp(char
*tp,
cjys
*p)int
main()
{
cjdl
p
char
x[255]
cjys
*re=NULL
int
jl[Size_Max_bm]
input(&p)
re=cjs(&p)
printf("对照编码图为:\n")
bls(re,jl,0)
freopen("CON","r",stdin)
printf("输入Huffman码(VLC):")
scanf("%s",x)
disp(x,re)
system("pause")
}
void
input(cjdl
*p)
{
int
i
cjys
*tp
tp=fpnn()
printf("输入字母个数:")
scanf("%d",
&p->size)
p->p=malloc(sizeof(cjys)*p->size)
p->leapsize=0
for(i
=
0
i
<
p->sizei++)
{
printf("输入第%d字母:",i+1),scanf("
%c",&tp->sj)
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl)
rd(p,*tp)
}
free(tp)
}
cjys
*fpnn(void)
{
cjys
*p=NULL
p=malloc(sizeof(cjys))
p->left=NULL
p->right=NULL
return
p
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r
if(mini
!=
i)
{
swap(p[i],p[mini])
zxdwh(p,mini,leapsize)
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("队列已满!")
exit(0)
}
p->p[p->leapsize]=tp
int
j=p->leapsize,k=parent(j)
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k])
j=k
k=parent(j)
}
p->leapsize++
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("队列已空!")
exit(0)
}
cjys
tp=p->p[0]
p->leapsize--
p->p[0]=p->p[p->leapsize]
zxdwh(p->p,0,p->leapsize)
return
tp
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL
cjys
tp
p1=fpnn()
p2=fpnn()
*p1=cd(p)
*p2=cd(p)
tp.left=p1
tp.right=p2
tp.pl=p1->pl+p2->pl
tp.sj=NIL
rd(p,tp)
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize
cjys
*tp=NULL
tp=fpnn()
for(i
=
0
i
<
n-1
i++)
hbs(p)
*tp=p->p[0]
return
tp
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return
if(p->sj!=NIL)
{
int
i2
printf("%c:",p->sj)
for(i2
=
0
i2
<
i
i2++)
printf("%d",jl[i2])
printf("\n")
}
jl[i]=0
bls(p->left,jl,i+1)
jl[i]=1
bls(p->right,jl,i+1)
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL
int
pd=0
while(1)
{
ttp=p
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj)
break
}
if(*tp
==
'\0')
{
pd=1
break
}
if(*tp++
==
'0'
)
ttp=ttp->left
else
ttp=ttp->right
}
if(pd)
break
}
}
