哈夫曼树:又称最优树(二叉树),是一类带权路径最短的树。
结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和,记做WPL
WPL为最小的二叉树就称作最优二叉树或哈夫曼树。
哈夫曼树的构造:
(1)将结点按照权值从小到大排列。
(2)每次取前两个权值最小的结点作为左右子树,其根节点的权值为这两个子树结点权值之和。
(3)将原两个结点权值最小的结点从排列中删除,并将这两个结点的根结点加入排列中。
(4)重复(1)(2)(3),直到最后只剩下一个结点为止。则哈夫曼树构造成功。
例如:
在代码中,使用优先队列构建哈夫曼树。
哈夫曼编码:从哈夫曼树根结点开始,左0右1,即对左子树分配代码"0",右子树分配代码"1",一直到叶子结点为止,然后将从树根沿每条路径到达叶子结点的代码排列起来,便得到了哈夫曼编码。
如上例:由哈夫曼树获得每个字母编码为:
a : 0 ; b : 10 ; c : 110 ; d : 111 ;
哈夫曼压缩:无损的压缩算法,一般用来压缩文本和程序文件。个体符号用一个特定长度的位序列替代,在文件中出现频率高的,使用短的位序列,而那些很少出现的符号,则用较长的位序列。如将字符转化为它们的01串。
public class hfmTree {
private hfmNode root;
private int size;
private int i=0;
Comparator<hfmNode> OrderIsdn=new Comparator<hfmNode>(){
@Override
public int compare(hfmNode node1, hfmNode node2) {
// TODO Auto-generated method stub
int numbera=node1.getTimes();
int numberb=node2.getTimes();
if(numberb>numbera){
return -1;
}else if(numberb<numbera){
return 1;
}else{
return 0;
}
}
};
public void createTree(int [] CountArray){
//优先队列
PriorityQueue<hfmNode> nodeQueue=new PriorityQueue<hfmNode>(10,OrderIsdn);
//把所有的结点都加入到队列里面去
for(int i=0;i<CountArray.length;i++){
if(CountArray[i]!=0){
hfmNode node=new hfmNode(i+97,CountArray[i]);
nodeQueue.add(node);//加入结点
}
}
size=nodeQueue.size();
//构建哈夫曼树
while(nodeQueue.size()>1){
hfmNode min1=nodeQueue.poll();//获取队列头
System.out.print(min1.getTimes()+" ");
System.out.println();
hfmNode min2=nodeQueue.poll();
hfmNode result=new hfmNode(0,min1.getTimes()+min2.getTimes());
result.setlChild(min1);//将最小的设为左子树
result.setrChild(min2);//将第二小的设为右子树
nodeQueue.add(result);//加入合并结点
}
root=nodeQueue.peek();//得到根结点
}
public void getMB(hfmNode root,String s){
Code [] SaveCode=new Code [size];
if((root.getlChild()==null)&&root.getrChild()==null){
Code hc=new Code();
hc.setNode(s);
hc.setN(s.length());
System.out.println("结点 "+(char)(root.getData())+" 编码 "+hc.getNode());
SaveCode[i++]=hc;//保存字节
}
if(root.getlChild()!=null){//左0右1
getMB(root.getlChild(),s+'0');
}
if(root.getrChild()!=null){
getMB(root.getrChild(),s+'1');
}
}
注意:应该让优先队列按照你给的自然顺序对结点进行排列,此处是需要对结点的权值进行排列,所以需要重写Comparator类中的compare()方法,否则会出现类转换异常。
相关推荐
哈夫曼树是一种在计算机科学中广泛使用的数据结构,尤其在数据压缩领域有着重要的应用。本实验报告主要探讨了如何运用哈夫曼树对文本文件进行编码和解压缩,以实现无损数据压缩。 首先,我们需要理解哈夫曼树的基本...
哈夫曼树(Huffman Tree),也称为最优二叉树,是数据压缩领域中的一个重要概念。它是基于贪心策略的一种数据结构,用于构建一种特殊的二叉树,使得带权路径长度最短,从而达到编码效率最高。哈夫曼树的核心思想是...
"数据结构哈夫曼树PPT学习教案.pptx" 哈夫曼树是一种特殊的二叉树,它的带权路径长度最小。哈夫曼树的构造是数据结构中的一种重要算法,广泛应用于数据压缩、编码和决策树等领域。 一、基本术语 在哈夫曼树中,...
哈夫曼树是一种特殊的二叉树,用于解决数据编码和压缩问题,特别是在数据通信和文件压缩领域广泛应用。哈夫曼编码是一种高效的前缀编码方法,它根据数据出现频率分配最短的二进制码,频繁出现的字符拥有较短的编码,...
数据结构课程设计的目标是让学生能够灵活运用所学的数据结构知识,特别是哈夫曼树这一重要概念,来解决实际问题。哈夫曼树是一种特殊的二叉树,常用于数据压缩和编码,通过构建最小带权路径长度的二叉树,使得频率高...
数据结构中的哈夫曼树(Huffman Tree),也称为最优二叉树,是一种特殊的二叉树,主要用于数据的编码压缩。哈夫曼树是通过哈夫曼编码(Huffman Coding)来实现的,这是一种用于无损数据压缩的算法。在这个算法中,...
哈夫曼树与哈夫曼编码是数据结构和算法领域中的一个重要概念,广泛应用于数据压缩、文本编码以及优先队列等场景。哈夫曼编码是一种特殊的前缀编码方法,能够为字符提供一种高效的二进制表示,使得频繁出现的字符具有...
哈夫曼树及哈夫曼编码译码的实现 哈夫曼树是一种特殊的二叉树,它的每个节点的权重是其所有子节点的权重之和。哈夫曼树的应用非常广泛,如数据压缩、编码、译码等。 哈夫曼树的存储结构 哈夫曼树的存储结构可以...
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入...
### 数据结构:哈夫曼树上机实验 #### 实验目的 本次实验旨在通过实际编程操作,加深学生对哈夫曼树(又称最优二叉树)的理解与掌握,熟悉哈夫曼树的构造过程及其应用。 #### 实验背景 哈夫曼树是一种带权路径长度...
根据给定的文件信息,我们可以深入探讨哈夫曼树(Huffman Tree)的基本操作与实现。哈夫曼树是一种在编码领域广泛应用的数据结构,主要用于数据压缩中的编码算法,特别是无损数据压缩。以下是对该代码及其功能的详细...
哈夫曼树的编译码器 哈夫曼树是一种特殊的二叉树,它的叶子结点权值和内部结点权值的关系满足某些特定的条件,常用于数据压缩和编码。在本文中,我们将使用 C 语言实现哈夫曼树的编译码器,包括建立哈夫曼树、...
哈夫曼树是一种特殊的二叉树,也称为最优二叉树或最小带权路径长度树。在信息编码领域,哈夫曼树常用于创建哈夫曼编码,这是一种用于数据压缩的有效方法。它通过构建一种特殊的树结构,使得树中每个叶子节点代表一个...
根据给定的信息,本文将详细解析哈夫曼树的实现及其相关知识点,包括类的定义、构造过程以及编码方法。 ### 哈夫曼树的基本概念 哈夫曼树(Huffman Tree),又称最优二叉树,是一种带权路径长度最短的二叉树,在...
哈夫曼树(Huffman Tree)和哈夫曼编码(Huffman Coding)是数据压缩领域中的基础算法,它们主要用于无损数据压缩。哈夫曼编码是一种可变长度的前缀编码,通过为每个字符分配一个唯一的二进制码,使得出现频率高的...
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if...
哈夫曼树程序设计问题 哈夫曼树是一种特殊的二叉树,它的每个节点的权重都是其左右子树的权重之和。哈夫曼树的主要应用是用于数据压缩,特别是文本压缩。哈夫曼树的构建过程是从叶子节点开始,逐渐构建树形结构,...
哈夫曼树(Huffman Tree),也称为最优二叉树,是数据压缩中的一种关键算法。它是基于贪心策略构建的,用于实现哈夫曼编码(Huffman Coding),这是一种无损数据压缩方法。在C++中实现哈夫曼树压缩与解压涉及到几个...
哈夫曼树是一种特殊的二叉树,主要用于数据压缩和编码,尤其在文本传输中能有效减少数据量。它的构建基于赫夫曼编码的概念,通过构建一个具有特定特性的二叉树来实现对字符的编码和解码。 哈夫曼树的构造过程可以...