哈夫曼树
一、 基本术语
1. 路径与路径长度
若在一棵树中存在一个结点序列 k1, k2, …., kj ，使得kj是kj+1的双亲（1<=i
列为A，B，E，J。
路径长度为3。
8 10
4 5 3
2. 结点的权和带权路径长度
如果根据需要给树中的结点赋予一个有某中意义的实数，则称此实数为该结点的权，结点带权路径长度规定为从树根结点到该结点之间的路径长度乘上该结点的权值所得到的乘积。
3. 树的带权路径长度
树的带权路径长度定义为树中所有叶结点的带权路径长度之和，通常记为：
n
WPL=∑ wili wi和li 分别代表叶结点ki的权值和ki到
i=1 根结点的路径长度
例如：上图的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼树
哈夫曼树又称为最优二叉树，它是由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
例如：有四个叶结点a，b，c，d，分别带权为9，4，5，2，可以构成三棵不同的二叉树（当然可以构成更多的二叉树）见下图：
9 4 5 2 WPL=（9+4+5+2）*2=40
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
9
5
4 2
WPL=9*1+5*2+（2+4）*3=37
可以证明最后一棵二叉树是哈夫曼树。
二、 构造哈夫曼树
1. 将n个叶结点构成独立的n棵二叉树，每棵二叉树只有一个根结点。
2. 选择两棵权值最小的二叉树合并成一棵二叉树，并以这两棵二叉树的权值之和作为这棵二叉树的权值，取消原来的两棵二叉树。
3. 重复2，知道只剩一棵二叉树为止。
例如：有6个带权叶结点的权值分别为：3，6，8，5，2，2，构造一棵哈夫曼树，并计算WPL的结果。
1.构造6棵二叉树
3 6 8 5 2 2
2选出两个权值最小的二叉树的组成一棵二叉树
2 2 合并权值为4
3 6 8 5
3 6 8 5 4
2 2
选出两个权值最小的二叉树的组成一棵二叉树
7 6 8 5
3
2 2
选出两个权值最小的二叉树的组成一棵二叉树
7 11 8
3
5 6
2 2
选出两个权值最小的二叉树的组成一棵二叉树
15 11
8
5 6
3
2 2
选出两个权值最小的二叉树的组成一棵二叉树（最终的哈夫曼树）
8
5 6
3
2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作业：P221/9
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
基本术语
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为WPL= ∑ wili
i=1
哈夫曼树
哈夫曼(Huffman)树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树
构造算法如下：
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点，其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵，同时把新树加入F中
(4) 重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树
哈夫曼编码
等长编码缺点：使传送电文总长度很长
不等长编码缺点：译码的二义性或多义性
前缀编码：对某一字符集进行不等长编码时，任一字符编码都不是其它字符编码的前缀
哈夫曼编码：由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例：在一电文中，六个字符A,B,C,D,E,F的出现频率依次为4，2，6，8，3，2,如图(a)
由此构造的哈夫曼编码树如图(b)所示
A、B、C、D、E、F的哈夫曼编码依次为：00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61
既然这么急，就说是用什么语言啊，C/C++、Basic...
还有，英文词典里的单词统计前，是读带单词表的文件，还是自定义初始化赋值就可以了呢！
你说要用C，我用的是Turbo C 2 编译的，怎么不是C＋＋呢，我可是从百忙中啊！
其中假设英语词典以单词表形式保存在C:\word.txt中，且每一行一个单词。
代码如下：
-----------------------------------------------------------
/*
HuffmanCode BY TC 2
Author: ejau
Ver 1.00
Data:19/05/2006
*/
#include
#include
#include
#include
#include
typedef struct {
float weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);
void main()
{
HuffmanTree T=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n=26;
printf("Default Input n = %d\n",n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
float *kt=(float *)malloc((n+1)*sizeof(float *));
kt[0]=0;
for(i=0;i<=n;i++)
w[i] = 0;
char * count;
FILE * file1;
char filen[30] = "C:\\word.txt";
if((file1 = fopen(filen,"r"))==NULL)
{
printf("File Read Error!\n");
exit(0);
}
while(fscanf(file1,"%s",count)!=EOF)
{
int temp;
if(countofpoint[0]>='a'&&count[0]<='z')
temp = (int)count[0]-96;
if(countofpoint[0]>='A'&&count[0]<='Z')
temp = (int)count[0]-64;
w[temp]++;
}
fclose(file1);
int tatolnum=0;
for(i=0;i<=n;i++)
tatolnum=tatolnum+w[i];
for(i=1;i<=n;i++)
kt[i]=(float *)w[i]/tatolnum;
HC=HuffmanCoding(HT,HC,kt,n);
printf("HuffmanCode:\n");
printf("Letter\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%c\t\t%f\t\t%s\n",i+64,kt[i],HC[i]);
}
void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,kt++)
{
p->weight=*kt;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.s2;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
printf("HT List:\n");
printf("Letter\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%c\t\t%f\t\t%d\t\t%d\t\t%d\n",i+64,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}
MinCode Select(HuffmanTree HT,unsigned int n)
{
float min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
基本术语
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为WPL= ∑ wili
i=1
哈夫曼树
哈夫曼(Huffman)树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树
构造算法如下：
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点，其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵，同时把新树加入F中
(4) 重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树
哈夫曼编码
等长编码缺点：使传送电文总长度很长
不等长编码缺点：译码的二义性或多义性
前缀编码：对某一字符集进行不等长编码时，任一字符编码都不是其它字符编码的前缀
哈夫曼编码：由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例：在一电文中，六个字符A,B,C,D,E,F的出现频率依次为4，2，6，8，3，2,如图(a)
由此构造的哈夫曼编码树如图(b)所示
A、B、C、D、E、F的哈夫曼编码依次为：00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024