`
guanxianxiao
  • 浏览: 19385 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

树之极品——哈夫曼树

阅读更多
1、哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。这种树在信息检索中很有用。

结点的带权路径长度:从该节点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和。即:WPL

WPL最小的二叉树就称作最优二叉树或哈弗曼树。

2、哈夫曼树的构造

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

如:
四个数: 7  5  2  4   构建的树为    
············18··········· 
··········/····\········· 
········7········11······
···············/···\·····
··············5·····6····
···················/·\···                    
··················2···4···                                                                              
构建规则:由最小的两个结点开始建树,左子节点权值小于右子结点权值

3、哈弗曼编码
从哈弗曼树根节点开始,对左子树分配代码“0”,右子树分配代码“1”,一直到达叶子节点为止,然后将从树根沿每条路径到达叶
子节点的代码排列起来,便得到了哈弗曼编码。

如上树中:  7 的哈弗曼编码:0
5   的哈弗曼编码为:10
2   的哈弗曼编码为: 110
4   的哈弗曼编码为:111

4、哈弗曼压缩
它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明Huffman算法在无损压缩算法中是最优的。
(1)将要压缩的文件一个一个字节的读出来即扫描要压缩的文件,并统计每个字节的权值即出现的频率。
(2)构建哈弗曼树
(3)取得每一个叶子节点的哈弗曼编码
(4)写出每一个字节对应编码的长度
(5)写出每一个字节所对应的编码
(6)将源文件中的所有byte转化为01哈弗曼编码,写入压缩文件

然后就没然后了,恭喜你已经实现了压缩!


哈弗曼树练习:
1.构建哈弗曼树
2.根据哈弗曼树生成码表并且打印出码表
3.根据字符串生成01串编码
4.再根据01串编码还原字符串

结点类:
public class Node  implements java.lang.Comparable<Node>{
	
	private int count;
	
	private char verb;
	
	private Node Lnode;
	
	private Node Rnode;
	
//构造函数
	public Node(char verb,int count) {
		this.verb = verb;
		this.count = count;
	}
//	返回左子树
	public Node getLnode() {
		return Lnode;
	}
//	设置左子树
	public void setLnode(Node lnode) {
		Lnode = lnode;
	}
//	返回右子树
	public Node getRnode() {
		return Rnode;
	}
//	设置右子树
	public void setRnode(Node rnode) {
		Rnode = rnode;
	}
//返回字符
	public char getVerb() {
		return verb;
	}
//设置字符
	public void setVerb(char verb) {
		this.verb = verb;
	}
//返回个数
	public int getCount() {
		return count;
	}
//设置数目
	public void setCount(int count) {
		this.count = count;
	}
	
	
	public int compareTo(Node no){
		if(this.count<no.count){
			return -1;
		 }
		else if(this.count>no.count){
			return 1;
		}
		else return 0;
		 
	 }
}


哈夫曼树类:
import java.util.PriorityQueue;

public class Hfmtree {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Hfmtree tree = new Hfmtree();
		tree.creattree();
		
	}
	
	

	public void creattree(){
		String s = new String("listentomeplease");
		
		System.out.println("字符串为:"+s);
		//实例化一个优先队列
		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		
		
	
		char[] c = new char[s.length()];
//		声明26个小写字母
		for(int i=0;i<26;i++){
			node[i]=new Node((char)(97+i),0);
		}
		
		System.out.println("node数组的长度"+node.length);
		
//		将字符分别存入数组里
		for(int i=0;i<s.length();i++){
			c[i] = s.charAt(i);
		}
		
		System.out.println("字符数组的长度"+c.length);
		
//		计数并存入优先队列
		for(int i=0;i<node.length;i++){
			int count=0;
			for(int j=0;j<s.length();j++){
				if(node[i].getVerb()==c[j]){
					count++;
					node[i].setCount(count);
				}
			}
		}
		for(int i=0;i<node.length;i++){
			if(node[i].getCount()!=0){
				System.out.print("字符:"+node[i].getVerb()+"\t 个数:"+node[i].getCount());
				System.out.println();
				queue.add(node[i]);
			}
		}
		
		System.out.println("队列的长度"+queue.size());
		
//		循环取出最小两个值 并构架二叉树
		while(queue.size()>1){
			Node node1 = queue.poll();//获取队列头
			Node node2 = queue.poll();
			Node result = new Node((char)0,node1.getCount()+node2.getCount());
			result.setLnode(node1);
			result.setRnode(node2);
			queue.add(result);
		}
//		得到根节点
		root = queue.peek();
		this.getMB(root, "");
	}
	
	public void getMB(Node root,String s){
		if(root.getLnode()==null&&root.getRnode()==null){
			System.out.println("叶子节点"+root.getVerb()+"编码"+s);
		}
		if(root.getLnode()!=null){//左 0 右 1
			getMB(root.getLnode(),s+'0');
		}
		if(root.getRnode()!=null){
			getMB(root.getRnode(),s+'1');
		}
	}
	
	
	private Node root= null;
	private Node[] node = new Node[26] ;
}


分享到:
评论

相关推荐

    树的应用——哈夫曼编码

    树的应用——哈夫曼编码 二、 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 从...

    树的应用——哈夫曼编码(C语言版)

    构建Huffman树,详细展示Huffman的初态和终态,通过Huffman树生成Huffman编码。

    课设——哈夫曼树的源代码

    哈夫曼树(Huffman Tree),也称为最优二叉树,是一种特殊的二叉树结构,广泛应用于数据压缩领域。在信息编码中,哈夫曼编码是一种可变长度的前缀编码,它根据字符出现的频率分配不同的二进制编码,频率高的字符编码...

    数据结构课程设计——哈夫曼树

    在数据结构的学习中,哈夫曼树(Huffman Tree)是一种非常重要的数据结构,它在数据压缩、编码优化等领域有着广泛的应用。哈夫曼树,也称为最优二叉树,是一种带权路径长度最短的二叉树。在这个数据结构课程设计中,...

    数据结构课设——哈夫曼树

    在这个课设中,我们关注的是哈夫曼树(Huffman Tree),一种在数据压缩领域广泛应用的数据结构。哈夫曼树,也称为最优二叉树,是通过哈夫曼编码实现数据压缩的关键工具。下面将详细阐述哈夫曼树的概念、构建过程、...

    数据结构——哈夫曼编码

    它的核心思想是通过构建一个特殊的二叉树——哈夫曼树(Huffman Tree),来为数据的各个符号分配最短的编码,使得频率高的符号编码较短,频率低的符号编码较长,从而实现数据的平均码长最小化,达到压缩数据的目的。...

    数据结构课程设计——哈夫曼编/译码器

    在这个“数据结构课程设计——哈夫曼编/译码器”项目中,我们将深入学习哈夫曼编码的原理和实现。哈夫曼编码的过程主要包括以下几个步骤: 1. **统计字符频率**:首先,我们需要统计输入文本中每个字符出现的次数,...

    数据结构——哈夫曼树(自己编的)

    哈夫曼树 基本功能: (1) 从文件中读出一篇英文文章,包含字母和空格等字符。 (2) 统计各个字符出现的频度。 (3) 根据出现的频度,为每个出现的字符建立一个哈夫曼编码,并输出。 (4) 输入一个字符串,为其...

    C++课程设计——哈夫曼树.txt

    设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。

    《数据结构》实验——哈夫曼编码

    哈夫曼编码是一种高效的数据压缩方法,源自于数据结构中的树形数据结构,主要用于无损数据压缩。在《数据结构》这本教材中,哈夫曼编码是重要的章节之一,通常由人民邮电出版社出版的教材会详细讲解这一概念。在进行...

    哈工大数据结构——哈夫曼编码

    哈夫曼树,也称为最优二叉树或最小带权路径长度树,是一棵特殊的二叉树,其中每个叶子节点代表一个需要编码的字符,而内部节点(非叶子节点)则表示合并两个频率较低的字符节点形成的新的频率节点。构建哈夫曼树的...

    最优二叉树——哈夫曼树.doc

    树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。

    重庆大学数据结构项目2——哈夫曼编码树

    3. 构建哈弗曼树:每次从队列中取出两个频率最小的节点,合并成一个新的节点,新节点的频率是两个子节点的频率之和,然后将新节点入队。 4. 生成哈弗曼编码:从根节点到每个叶子节点的路径构成该叶子节点的哈弗曼...

    数据结构——哈夫曼编码 完整代码

    哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短...

    数据结构哈夫曼树PPT学习教案.pptx

    "数据结构哈夫曼树PPT学习教案.pptx" 哈夫曼树是一种特殊的二叉树,它的带权路径长度最小。哈夫曼树的构造是数据结构中的一种重要算法,广泛应用于数据压缩、编码和决策树等领域。 一、基本术语 在哈夫曼树中,...

    用C语言实现三叉哈夫曼树

    用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树

Global site tag (gtag.js) - Google Analytics