- 浏览: 584460 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.
哈夫曼树的构造:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树
例:
假设一个文本文件中只包含7个字符{A,B,C,D,E,F,G},这7个字符在文本中出现的次数为{5,24,7,17,34,5,13},求这些字符的哈夫曼编码。
//上图的测试:
运行结果:
data:null;weight:105.0;Coding:
data:null;weight:41.0;Coding:0
data:null;weight:64.0;Coding:1
data:D;weight:17.0;Coding:00
data:B;weight:24.0;Coding:01
data:null;weight:30.0;Coding:10
data:E;weight:34.0;Coding:11
data:G;weight:13.0;Coding:100
data:null;weight:17.0;Coding:101
data:C;weight:7.0;Coding:1010
data:null;weight:10.0;Coding:1011
data:F;weight:5.0;Coding:10110
data:A;weight:5.0;Coding:10111
下载源码:
哈夫曼树的构造:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; public class HuffmanTree<T> { //构造哈夫曼树 public static <T> Node<T> createTree(List<Node<T>> nodes){ while(nodes.size() > 1){ Collections.sort(nodes); Node<T> left = nodes.get(nodes.size()-1); Node<T> right = nodes.get(nodes.size()-2); Node<T> parent = new Node<T>(null, left.getWeight()+right.getWeight()); parent.setLeft(left); parent.setRight(right); nodes.remove(left); nodes.remove(right); nodes.add(parent); } return nodes.get(0); } //递归生成Huffman编码 public static<T> void generateHuffmanCode(Node<T> root){ 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()); } public static <T> List<Node<T>> breadth(Node<T> root){ //广度优先遍历哈夫曼树 List<Node<T>> list = new ArrayList<Node<T>>(); Queue<Node<T>> queue = new ArrayDeque<Node<T>>(); if(root != null){ queue.offer(root); } while(!queue.isEmpty()){ list.add(queue.peek()); Node<T> node = queue.poll(); if(node.getLeft() != null){ queue.offer(node.getLeft()); } if(node.getRight() != null){ queue.offer(node.getRight()); } } return list; } } //哈夫曼树节点 public class Node<T> implements Comparable<Node<T>> { private T data; private double weight; private String coding = ""; //哈夫曼编码 private Node<T> left; private Node<T> right; public Node(T data, double weight){ this.data = data; this.weight = weight; } public T getData() { return data; } public void setData(T data) { this.data = data; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; } public Node<T> getLeft() { return left; } public void setLeft(Node<T> left) { this.left = left; } public Node<T> getRight() { return right; } public void setRight(Node<T> right) { this.right = right; } public String getCoding(){ return coding;} public void setCoding(String coding){ this.coding = coding;} @Override public String toString(){ return "data:"+this.data+";weight:"+this.weight+";Coding:"+this.coding; } @Override public int compareTo(Node<T> other) { if(other.getWeight() > this.getWeight()){ return 1; } if(other.getWeight() < this.getWeight()){ return -1; } return 0; } }
例:
假设一个文本文件中只包含7个字符{A,B,C,D,E,F,G},这7个字符在文本中出现的次数为{5,24,7,17,34,5,13},求这些字符的哈夫曼编码。
//上图的测试:
import java.util.ArrayList; import java.util.List; public class Test { public static void main(String[] args) { int a[]={5,24,7,17,34,5,13}; String s[]={"A","B","C","D","E","F","G"}; List<Node<String>> list1 = new ArrayList<Node<String>>(); for(int i=0;i<a.length;i++) list1.add(new Node<String>(s[i],a[i])); root = HuffmanTree.createTree(list1); HuffmanTree.generateHuffmanCode(root); List<Node<String>> list2=HuffmanTree.breadth(root); for(Node<String> node: list2) System.out.println(node); } }
运行结果:
data:null;weight:105.0;Coding:
data:null;weight:41.0;Coding:0
data:null;weight:64.0;Coding:1
data:D;weight:17.0;Coding:00
data:B;weight:24.0;Coding:01
data:null;weight:30.0;Coding:10
data:E;weight:34.0;Coding:11
data:G;weight:13.0;Coding:100
data:null;weight:17.0;Coding:101
data:C;weight:7.0;Coding:1010
data:null;weight:10.0;Coding:1011
data:F;weight:5.0;Coding:10110
data:A;weight:5.0;Coding:10111
下载源码:
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2329北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1947import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1831POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1355接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2421当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1769关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1675关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1753关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1703一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2024POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2486设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2036继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2500继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2603先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2218一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2013形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2787例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2062字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18575堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3988一、什么是并查集 ...
相关推荐
哈夫曼树和哈夫曼编码的Java实现,供新手学习使用。希望能给需要的人以帮助。
哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx
从终端读入字符集大小 n,及 n 个字符和 m 个权值,建立哈夫曼树,并将它存于文件 hfmtree 中。 (2)C:编码 (Coding)。利用已建好的哈夫曼树(如不在内存,则从文件 hfmtree 中读入),对文件 tobetrans 中的正文进行...
基于JAVA实现的Huffman哈夫曼树编码与解码
自适应哈弗曼Java版实现,内有可执行文件
采用java窗体设计编写,功能有哈夫曼树的生成,哈弗曼编码的生成,以及根据哈夫曼树和哈夫曼编码反编译成文档,资源为源代码。
java哈夫曼树的编码解码
java语言 数据结构 哈夫曼树 源代码 以前编写的,可以给学习数据结构的看看。
课程设计 霍夫曼编码译码 完整代码 可打印哈夫曼树
①哈夫曼树编码和译码:.\源程序\哈夫曼编码和译码\src ②手机信息管理: .\源程序\手机信息管理\src 哈夫曼树编码和译码: 采用UTF-8编码 文本文件:放在运行根目录下 主程序:\bin\com\gauze\Main.class ...
严蔚敏奶奶数据结构一书中,第六章树,哈夫曼编码的实现程序
用于哈夫曼树的编码与译码,并保存到文件中,并保存到文件中
数据结构哈夫曼树编码解码,自己用c++编的,vc6.0通过,可运行
主要为大家介绍了java哈夫曼树实例代码,感兴趣的小伙伴们可以参考一下
这样的数据结构课程设计的设计和实现过程,绝对让你对把它实现的开发者佩服,有了它,你对编程的兴趣和感受到它的强大也会倍增,有了它,你的数据结构课程设计之 哈夫曼树的应用 的实现也不会感到困难,绝不再是一个...
哈夫曼树的基本创建,同时还有哈夫曼编码的创建,用了动态申请内存空间的知识
利用哈夫曼树对文本进行压缩与解压缩,统计文本的字符数,建立哈夫曼树,再进行编码
哈夫曼树的应用-哈夫曼编码
大家都知道哈夫曼是用来做压缩解压的算法,通过...你也可以说是“每个字符出现的次数”或者“哈夫曼树”,不管是“每个字符出现的次数”还是“哈夫曼树”,你都需要通过他们得到“每个字符的编码”之后才能进行解码。