哈弗曼树实现.docx
《哈弗曼树实现.docx》由会员分享，可在线阅读，更多相关《哈弗曼树实现.docx（21页珍藏版）》请在冰点文库上搜索。
哈弗曼树实现
Huffman树的实现
一、哈夫曼树的概念和定义
什么是哈夫曼树？
让我们先举一个例子。
判定树：
在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。
例如，编制一个程序，将百分制转换成五个等级输出。
大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：
if（score<60）
System.out.println（"不及格"）;
elseif（score<70）
System.out.println（"及格"）;
elseif（score<80）
System.out.println（"中等"）;
elseif（score<90）
System.out.println（"良好"）;
else
System.out.println（"优秀!
"）;
若考虑上述程序所耗费的时间，就会发现该程序的缺陷。
在实际中，学生成绩在五个等级上的分布是不均匀的。
当学生百分制成绩的录入量很大时，上述判定过程需要反复调用，此时程序的执行效率将成为一个严重问题。
但在实际应用中，往往各个分数段的分布并不是均匀的。
下面就是在一次考试中某门课程的各分数段的分布情况：
下面我们就利用哈夫曼树寻找一棵最佳判定树，即总的比较次数最少的判定树。
第一种构造方式：
第二种构造方式：
这两种方式，显然后者的判定过程的效率要比前者高。
在也没有别地判定过程比第二种方式的效率更高。
我们称判定过程最优的二叉树为哈夫曼树，又称最优二叉树
1.哈夫曼树的基本概念
哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。
在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念。
树中两个结点之间的路径由一个结点到另一结点的分支构成。
两结点之间的路径长度是路径上分支的数目。
树的路径长度是从根结点到每一个结点的路径长度之和。
设一棵二叉树有n个叶子结点，每个叶子结点拥有一个权值Ｗ1，Ｗ2，......Ｗn，从根结点到每个叶子结点的路径长度分别为L1，L2......Ln，那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。
通常记作WPL。
为了直观其见，在图中把带权的叶子结点画成方形，其他非叶子结点仍为圆形。
请看图中的三棵二叉树以及它们的带权路径长。
a）wpl=38（b）wpl=49（c）wpl=36
这三棵二叉树叶子结点数相同，它们的权值也相同，但是它们的wpl带权路径长各不相同。
图6.21（c）wpl最小。
它就是哈曼树，最优树。
哈夫曼树是，在具有同一组权值的叶子结点的不同二叉树中，带权路径长度最短的树。
也称最优树。
2.哈夫曼树的构造
构造哈夫曼树的方法（贪婪方法）
上图是是哈夫曼树构造过程
图（a）是一个拥有4棵小树的森林，图（b）森林中还有3子棵树，图（c）森林中剩下2棵树，图（d）森林只有一棵树，这棵树就是哈夫曼树。
这里或许会提出疑问，n个叶子构成的哈夫曼树其带权路径长度唯一吗？
确实唯一。
树形唯一吗？
不唯一。
因为将森林中两棵权值最小和次小的子棵合并时，哪棵做左子树，哪棵做右子树并不严格限制。
图之中的做法是把权值较小的当做左子树,权值较大的当做右子树。
如果反过来也可以，画出的树形有所不同，但WPL值相同。
为了便于讨论交流在此提倡权值较小的做左子树,权值较大的做右子。
3.哈夫曼树的应用
（1）用于最佳判断过程。
（上面已提到）
（2）用于通信编码
在通信及数据传输中多采用二进制编码。
为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。
设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。
假设有一段电文，其中用到4个不同字符Ａ，Ｃ，Ｓ，Ｔ，它们在电文中出现的次数分别为7，2，4，5。
把7，2，4，5当做4个叶子的权值构造哈夫曼树
如图所示。
在树中令所有左分支取编码为0，令所有右分支取编码为1。
将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图所示。
这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。
关于信息编码是一个复杂的问题，还应考虑其他一些因素。
比如前缀编码每个编码的长度不相等，译码时较困难。
还有检测、纠错问题都应考虑在内。
这里仅对哈夫曼树举了一个应用实例。
4、 哈夫曼树的JAVA实现
哈夫曼树节点:
publicclassNodeimplementsComparable>{
privateTdata;
privatedoubleweight;
privateStringcoding="";//此节点的哈夫曼编码
privateNodeleft;
privateNoderight;
publicNode（Tdata,doubleweight）{
this.data=data;
this.weight=weight;
}
publicTgetData（）{
returndata;
}
publicvoidsetData（Tdata）{
this.data=data;
}
publicdoublegetWeight（）{
returnweight;
}
publicvoidsetWeight（doubleweight）{
this.weight=weight;
}
publicNodegetLeft（）{
returnleft;
}
publicvoidsetLeft（Nodeleft）{
this.left=left;
}
publicNodegetRight（）{
returnright;
}
publicvoidsetRight（Noderight）{
this.right=right;
}
publicStringgetCoding（）{returncoding;}
publicvoidsetCoding（Stringcoding）{this.coding=coding;}
@Override
publicStringtoString（）{
return"data:
"+this.data+";weight:
"+this.weight+";Coding:
"+this.coding;
}
@Override
publicintcompareTo（Nodeother）{
if（other.getWeight（）>this.getWeight（））{
return1;
}
if（other.getWeight（）return-1;
}
return0;
}
}
//构造哈夫曼树的类
importjava.util.ArrayDeque;
importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.List;
importjava.util.Queue;
publicclassHuffmanTree{
//创建哈夫曼树
publicstaticNodecreateTree（List>nodes）{
while（nodes.size（）>1）{
Collections.sort（nodes）;
Nodeleft=nodes.get（nodes.size（）-1）;
Noderight=nodes.get（nodes.size（）-2）;
Nodeparent=newNode（null,left.getWeight（）+right.getWeight（））;
parent.setLeft（left）;
parent.setRight（right）;
nodes.remove（left）;
nodes.remove（right）;
nodes.add（parent）;
}
returnnodes.get（0）;
}
//递归生成Huffman编码
publicstaticvoidgenerateHuffmanCode（Noderoot）{
if（root==null）return;
if（root.getLeft（）!
=null）
root.getLeft（）.setCoding（root.getCoding（）+"0"）;
if（root.getRight（）!
=null）
root.getRight（）.setCoding（root.getCoding（）+"1"）;
generateHuffmanCode（root.getLeft（））;
generateHuffmanCode（root.getRight（））;
}
publicstaticList>breadth（Noderoot）{//广度优先遍历哈夫曼树
List>list=newArrayList>（）;
Queue>queue=newArrayDeque>（）;
if（root!
=null）{
queue.offer（root）;
}
while（!
queue.isEmpty（））{
list.add（queue.peek（））;
Nodenode=queue.poll（）;
if（node.getLeft（）!
=null）{
queue.offer（node.getLeft（））;
}
if（node.getRight（）!
=null）{
queue.offer（node.getRight（））;
}
}
returnlist;
}
}
//测试
importjava.util.ArrayList;
importjava.util.List;
publicclassTest{
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
List>list=newArrayList>（）;
list.add（newNode（"A",7））;
list.add（newNode（"T",5））;
list.add（newNode（"S",4））;
list.add（newNode（"C",2））;
Noderoot=HuffmanTree.createTree（list）;
HuffmanTree.generateHuffmanCode（root）;
System.out.println（HuffmanTree.breadth（root））;
//测试2
inta[]={5,24,7,17,34,5,13};
Strings[]={"A","B","C","D","E","F","G"};
List>list1=newArrayList>（）;
for（inti=0;ilist1.add（newNode（s[i],a[i]））;
root=HuffmanTree.createTree（list1）;
HuffmanTree.generateHuffmanCode（root）;
List>list2=HuffmanTree.breadth（root）;
for（Nodenode:
list2）
System.out.println（node）;
}
}
5、 哈夫曼树的C++实现
/*
1、问题描述
给定n个字符及其对应的权值，构造Huffman树，并进行huffman编码和译（解）码。
构造Huffman树时，要求左子树根的权值小于右子树根的权值。
进行Huffman编码时，假定Huffman树的左分支上编码为‘0’，右分支上编码为‘1’。
2、算法
构造Huffman树算法：
⑴、根据给定的n个权值（w1,w2,…,wn）构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个权值为wi的根结点
⑵、在F中选取两棵根结点的权值最小的树，作为左、右子树构造一棵新的二叉树，且置其根结点的权值为其左、右子树权值之和
⑶、在F中删除这两棵树，同时将新得到的二叉树加入F中
⑷、重复⑵,⑶，直到F只含一棵树为止
Huffman编码算法：
⑴、从Huffman树的每一个叶子结点开始
⑵、依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码‘0’，否则得到编码‘1’，先得到的编码放在后面
⑶、直到到达根结点，编码序列即为该叶子结点对应的Huffman编码
Huffman译（解）码算法：
⑴、指针指向Huffman树的根结点，取第一个Huffman码
⑵、如果Huffman码为‘0’，将指针指向当前结点的左子树的根结点；如果Huffman码为‘1’，将指针指向当前结点的右子树的根结点
⑶、如果指针指向的当前结点为叶子结点，则输出叶子结点对应的字符；否则，取下一个Huffman码，并返回⑵
⑷、如果Huffman码序列未结束，则返回⑴继续译码
Input
第一行：
样本字符个数，假设为n。
第二行，n个字符（用空格隔开）
第三行，n个字符对应的权值（用空格隔开）
第四行，待编码的字符串
第五行，待译码的Huffman码序列
Output
第一行，每个字符对应的Huffman编码（用空格隔开）
第二行，字符串对应的Huffman编码序列
第三行，Huffman码序列对应的字符串
SampleInput
4
abcd
9326
abcd
111001010
SampleOutput
010110011
010110011
dcba
*/
#include
#include
#include
usingnamespacestd;
constintMaxW=9999;//假设权值不超过9999
//定义hufffman树节点类
classHuffNode
{
public:
intweight;
intparent;
intleftchild;
intrightchild;
chardata;
};
//定义哈夫曼树类
classHuffMan
{
private:
voidMakeTree（）;//建树，私有函数，被公有函数调用
voidSelectMin（intpos,int*s1,int*s2）;//从1到pos找出权值最小的两个节点，把下标存在s1,s2中
public:
intlen;//节点数量
intlnum;//叶子数量
HuffNode*huffTree;//哈夫曼树，用数组表示
string*huffCode;//每个字符对应的哈夫曼编码
voidMakeTree（intn,intwt[],charc[]）;//公有函数，被主函数调用
voidCodeing（）;//公有函数，被主函数调用
voidCCodeing（stringc2）;//编码，，，公有函数，被主函数调用
voidCCCodeing（stringc3）;//译码，，，公有函数，被主函数调用
voidDestroy（）;
};
//构建huffman树
voidHuffMan:
:
MakeTree（intn,intwt[],charc[]）//参数是叶子节点数量和叶子权值
{
inti;
lnum=n;
len=2*n-1;
huffTree=newHuffNode[2*n];
huffCode=newstring[lnum+1];//位置从1开始计算
//hunffCode实质是个二维字符数组，第i行表示第i个字符对应的编码
//哈夫曼树初始化
for（i=1;i<=n;i++）
huffTree[i].data=c[i-1];//第0号不用，从1开始编号
for（i=1;i<=n;i++）
huffTree[i].weight=wt[i-1];//第0号不用，从1开始编号
for（i=1;i<=len;i++）
{
if（i>n）
huffTree[i].weight=0;//前n个节点是叶子，已经设值
huffTree[i].parent=0;
huffTree[i].leftchild=0;
huffTree[i].rightchild=0;
}
MakeTree（）;//调用私有函数建树
}
voidHuffMan:
:
SelectMin（intpos,int*s1,int*s2）
//找出最小的两个权值的下标
//函数采用地址传递的方法，找出的两个下标保存在s1和s2中
{
intw1,w2,i;
w1=w2=MaxW;
*s1=*s2=0;
for（i=1;i<=pos;i++）
{//如果第i节点的权值小于w1，且第i节点是未选择的节点（父亲为0）
//把w1和s1保存到w2和s2，即原来的第一最小值变成第二最小值
//把第i个节点的权值和下标保存到w1和s1，作为第一最小值
//else如果第i节点的权值小于w2，且第i节点是未选择的节点
//把第i节点的权值和下标保存到w2和s2，作为第二最小值
if（huffTree[i].weight{
w2=w1;
*s2=*s1;
w1=huffTree[i].weight;
*s1=i;
}elseif（huffTree[i].weight{
w2=huffTree[i].weight;
*s2=i;
}
}
}
voidHuffMan:
:
MakeTree（）
{
//私有函数，被公有函数调用
inti,s1,s2;
//构造哈夫曼树HuffTree的n-1个非叶节点
for（i=lnum+1;i<=len;i++）
{
SelectMin（i-1,&s1,&s2）;
//将找出的两颗权值最小的子树合并为一棵树，过程包括
//节点s1和s2的父亲设为i
//节点i的左右孩子分别设为s1和s2
//节点i的权值等于s1和s2的权值和
huffTree[s1].parent=i;
huffTree[s2].parent=i;
huffTree[i].leftchild=s1;
huffTree[i].rightchild=s2;
huffTree[i].weight=huffTree[s1].weight+huffTree[s2].weight;
}
}
//销毁哈夫曼树
voidHuffMan:
:
Destroy（）
{
len=0;
lnum=0;
delete[]huffTree;
delete[]huffCode;
}
//哈夫曼编码
voidHuffMan:
:
Codeing（）
{
char*cd;
inti,c,f,start;
//求n个叶节点的哈夫曼编码
cd=newchar[lnum];//分配求编码的工作空间
cd[lnum-1]='\0';
for（i=1;i<=lnum;++i）//逐个字符求哈夫曼编码
{
start=lnum-2;//编码结束符位置
//参考课本p147的第2个for循环代码
//....
c=i;
while（huffTree[c].parent!
=0）
{
f=huffTree[c].parent;
if（huffTree[f].leftchild==c）
cd[start]='0';
elseif（huffTree[f].rightchild==c）
cd[start]='1';
start--;
c=f;
}
huffCode[i].assign（&cd[start+1]）;//把cd中从start到末尾的编码复制到huffCode
}
delete[]cd;//释放工作空间
}
voidHuffMan:
:
CCodeing（stringc2）
{
inti,j;
for（i=0;ifor（j=1;j<=lnum;j++）
if（c2[i]==huffTree[j].data）
cout<}
voidHuffMan:
:
CCCodeing（stringc2）
{
inti,j=2*lnum-1;
for（i=0;iif（c2[i]=='0'）
{
j=huffTree[j].l
升级会员 