还记得第一次接触哈夫曼树是在大二的数据结构课上,大家也都知道哈树的生成规则,很简单也很容易理解。给你N个带权的节点,让你生成一颗哈树,相信大部分人都没有问题。而正是这种表面看似很简单的东西,我们就容易无视。我坦白,那年数据结构的学习,对于哈树这一块,我没有敲过一行代码,更没有去想过他存在的意义以及利用哈树能解决什么样的问题。
大三进入蓝杰,重新接触到了哈夫曼树。这个沉寂在我脑海已久且濒临消亡的知识点,仿佛又渐渐地回来了。也让我开始思考哈夫曼树存在的意义。在IT这么一个日新月异的领域,一个技术之所以能够存在,一定是有其价值的,他一定是能给我们决绝问题带来利益的。通过查找给方面的资料,发现哈弗曼的用处确实很广,尤其是在数据通信、图像处理、数据压缩等方面有着很大的用处。
下面,我想通过手动建造一棵哈夫曼树,再次走进哈夫曼的世界。 ------
一、哈弗曼的基础知识
大家要了解一下哈夫曼树的基础知识。网上有很多解释,度娘说的比我清楚,这里就不占用篇幅多做解释。
下图是建造一颗哈树的过程....
二、 进入主题--------代码的实现
(1)首先,定义一个树的节点类
/** * 哈夫曼树节点的定义 * * @author Administrator * */ public class HuffmanNode { // 成员属性 private HuffmanNode left_child = null; private HuffmanNode right_child = null; private HuffmanNode parend = null; // 权值 private int obj; public HuffmanNode getLeft_child() { return left_child; } public void setLeft_child(HuffmanNode left_child) { this.left_child = left_child; } public HuffmanNode getRight_child() { return right_child; } public void setRight_child(HuffmanNode right_child) { this.right_child = right_child; } public HuffmanNode getParend() { return parend; } public void setParend(HuffmanNode parend) { this.parend = parend; } public int getObj() { return obj; } public void setObj(int obj) { this.obj = obj; } // 构造函数 public HuffmanNode(int obj) { this.obj = obj; } }
(2)生成一颗哈树
这里用到了一个新的知识点---优先队列。因为哈夫曼树的构造规则是每次要取根节点权值最小的两棵树出来。所以我们必须根据这些根节点权值大小,将这些树进行排序。 优先队列恰好为我们提供了这项功能,我们通过重新定义Comparator比较器,可以设定自己想要的排序规则,十分方便。
Comparator<HuffmanNode> comparator = new Comparator<HuffmanNode>() { @Override public int compare(HuffmanNode o1, HuffmanNode o2) { int numbera = o1.getObj(); int numberb = o2.getObj(); if (numberb < numbera) { return 1; } else if (numberb > numbera) { return -1; } else { return 0; } } };
核心语句----哈树的生成
从森林中每次取根节点权值最小的两棵树出来,形成一棵新树,其权值为两树根绝点权值之和。并将这两棵树分别作为新树的左右子树。循环往复,知道深林中只剩下1棵树。那么,这棵树就是我们要找的哈夫曼树。
/** * 生成哈夫曼树的方法 * @param queue 优先队列 */ private void creathuffman(PriorityQueue<HuffmanNode> queue) { while (queue.size() != 1) { // 取得两个最小的节点 HuffmanNode node1 = queue.poll(); HuffmanNode node2 = queue.poll(); // 生成一个新的节点 HuffmanNode node3 = new HuffmanNode(node1.getObj() + node2.getObj()); node3.setLeft_child(node1); node3.setRight_child(node2); queue.add(node3); } }
(3)打印所生成的哈树(通过先序遍历)
// 打印哈夫曼树的方法 private void printhuffman(HuffmanNode rootnode) { // 指定根节点,从根节点开始找 HuffmanNode temp = rootnode; // 打印根节点的值 System.out.print("【"+temp.getObj()+"】" + " "); if (rootnode.getLeft_child() != null) { temp = rootnode.getLeft_child(); // 递归调用自己,表示只要左节点不为空,就把左节点作为新的根节点继续上边步奏 printhuffman(temp); } if (rootnode.getRight_child() != null) { temp = rootnode.getRight_child(); printhuffman(temp);// 同上 } }
至此,我们的哈夫曼树的生成过程已经演示完毕。刚才也说了,哈夫曼树的用处还有很多,我们能够创建他,也只是完成其中最基础的要求,我们不能止步于此。当然,我们不能认为这些东西很简单,就去轻视他,自己没有动手做过,你是不会知道什么叫做说着简单做着难的。
好啦, 之后我们会通过一个文件压缩程序的演示,其中包括了哈弗曼编码的生成,对象的序列化,文件的读出与写入等问题,跟大家进一步分享哈弗曼在数据编码上的用途。
相关推荐
哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树
哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码
哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼 典型问题 哈弗曼哈弗曼 典型问题 典型问题
哈弗曼树 数据结构课程设计 哈弗曼编码 哈弗曼树的建立
哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树
在C语言下实现哈弗曼树的创建并进行哈弗曼编码,同时输出哈弗曼编码。
哈弗曼编码译码 哈弗曼树的建立,编码 对26个大写英文字母以及空格键的编码,译码
哈弗曼编码哈弗曼编码哈弗曼编码哈弗曼编码哈弗曼编码
哈弗曼编码 哈弗曼树是基于编码压缩和传输而被广泛应用的数据结构
关于哈弗曼树的一个算法,用哈弗曼算法存储树
主要是哈弗曼编码的实现过程,就是建立哈弗曼编码的过程,只有源代码,但是源代码里面有解释。呵呵呵呵,希望对数据结构的学习者有帮助。
哈弗曼树 哈弗曼编码 构造哈弗曼编码 建立哈弗曼树 编码
构造一哈弗曼树并进行哈弗曼编码的源代码。
哈弗曼编码
将原文件进行哈弗曼编码后在利用哈弗曼编码进行压缩,建立哈弗曼树
哈弗曼树的建立 C++代码 哈弗曼树的建立 C++代码
哈弗曼编解码(C++),动态建立哈弗曼树,逆向求得编码…………………………………………
哈弗曼数,构建哈弗曼树,并输出存储结构,实现哈弗曼数的编码与译码,
哈弗曼树C++源代码 运行已通过 呵呵 希望对大家有所帮助
属于MFC在VC6.0下实现 哈弗曼编码 简单易懂……