哈弗曼树实现Word下载.docx
《哈弗曼树实现Word下载.docx》由会员分享，可在线阅读，更多相关《哈弗曼树实现Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
为了直观其见，在图中把带权的叶子结点画成方形，其他非叶子结点仍为圆形。
请看图中的三棵二叉树以及它们的带权路径长。
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实现
哈夫曼树节点:
publicclassNode<
T>
implementsComparable<
Node<
>
{
privateTdata;
privatedoubleweight;
privateStringcoding="
;
//此节点的哈夫曼编码
privateNode<
left;
right;
publicNode（Tdata,doubleweight）{
this.data=data;
this.weight=weight;
}
publicTgetData（）{
returndata;
publicvoidsetData（Tdata）{
publicdoublegetWeight（）{
returnweight;
publicvoidsetWeight（doubleweight）{
publicNode<
getLeft（）{
returnleft;
publicvoidsetLeft（Node<
left）{
this.left=left;
getRight（）{
returnright;
publicvoidsetRight（Node<
right）{
this.right=right;
publicStringgetCoding（）{returncoding;
}
publicvoidsetCoding（Stringcoding）{this.coding=coding;
}
@Override
publicStringtoString（）{
return"
data:
+this.data+"
weight:
+this.weight+"
Coding:
+this.coding;
publicintcompareTo（Node<
other）{
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<
//创建哈夫曼树
publicstatic<
createTree（List<
nodes）{
while（nodes.size（）>
1）{
Collections.sort（nodes）;
left=nodes.get（nodes.size（）-1）;
right=nodes.get（nodes.size（）-2）;
parent=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编码
publicstatic<
voidgenerateHuffmanCode（Node<
root）{
if（root==null）return;
if（root.getLeft（）!
=null）
root.getLeft（）.setCoding（root.getCoding（）+"
0"
if（root.getRight（）!
root.getRight（）.setCoding（root.getCoding（）+"
1"
generateHuffmanCode（root.getLeft（））;
generateHuffmanCode（root.getRight（））;
}
List<
breadth（Node<
root）{//广度优先遍历哈夫曼树
list=newArrayList<
（）;
Queue<
queue=newArrayDeque<
if（root!
=null）{
queue.offer（root）;
while（!
queue.isEmpty（））{
list.add（queue.peek（））;
Nodenode=queue.poll（）;
if（node.getLeft（）!
queue.offer（node.getLeft（））;
if（node.getRight（）!
queue.offer（node.getRight（））;
returnlist;
//测试
publicclassTest{
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
String>
list.add（newNode<
（"
A"
7））;
T"
5））;
S"
4））;
C"
2））;
root=HuffmanTree.createTree（list）;
HuffmanTree.generateHuffmanCode（root）;
System.out.println（HuffmanTree.breadth（root））;
//测试2
inta[]={5,24,7,17,34,5,13};
Strings[]={"
"
B"
D"
E"
F"
G"
};
list1=newArrayList<
for（inti=0;
i<
a.length;
i++）
list1.add（newNode<
（s[i],a[i]））;
root=HuffmanTree.createTree（list1）;
list2=HuffmanTree.breadth（root）;
for（Node<
node:
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<
iostream>
string>
cstring>
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中
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;
=n;
huffTree[i].data=c[i-1];
//第0号不用，从1开始编号
huffTree[i].weight=wt[i-1];
=len;
{
if（i>
n）
huffTree[i].weight=0;
//前n个节点是叶子，已经设值
huffTree[i].parent=0;
huffTree[i].leftchild=0;
huffTree[i].rightchild=0;
MakeTree（）;
//调用私有函数建树
SelectMin（intpos,int*s1,int*s2）
//找出最小的两个权值的下标
//函数采用地址传递的方法，找出的两个下标保存在s1和s2中
intw1,w2,i;
w1=w2=MaxW;
*s1=*s2=0;
=pos;
{//如果第i节点的权值小于w1，且第i节点是未选择的节点（父亲为0）
//把w1和s1保存到w2和s2，即原来的第一最小值变成第二最小值
//把第i个节点的权值和下标保存到w1和s1，作为第一最小值
//else如果第i节点的权值小于w2，且第i节点是未选择的节点
//把第i节点的权值和下标保存到w2和s2，作为第二最小值
if（huffTree[i].weight<
w1&
&
huffTree[i].parent==0）
{
w2=w1;
*s2=*s1;
w1=huffTree[i].weight;
*s1=i;
}elseif（huffTree[i].weight<
w2&
{
w2=huffTree[i].weight;
*s2=i;
}
MakeTree（）
//私有函数，被公有函数调用
inti,s1,s2;
//构造哈夫曼树HuffTree的n-1个非叶节点
for（i=lnum+1;
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;
//销毁哈夫曼树
Destroy（）
len=0;
lnum=0;
delete[]huffTree;
delete[]huffCode;
//哈夫曼编码
Codeing（）
char*cd;
inti,c,f,start;
//求n个叶节点的哈夫曼编码
cd=newchar[lnum];
//分配求编码的工作空间
cd[lnum-1]='
\0'
=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）
1'
start--;
c=f;
huffCode[i].assign（&
cd[start+1]）;
//把cd中从start到末尾的编码复制到huffCode
delete[]cd;
//释放工作空间
CCodeing（stringc2）
inti,j;
for（i=0;
c2.length（）;
for（j=1;
j<
j++）
if（c2[i]==huffTree[j].data）
cout<
<
huffCode[j];
CCCodeing（stringc2）
inti,j=2*lnum-1;
if（c2[i]=='
）
j=huffTree[j].l
升级会员 