还记得第一次接触哈夫曼树是在大二的数据结构课上,大家也都知道哈树的生成规则,很简单也很容易理解。给你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);// 同上 } }
至此,我们的哈夫曼树的生成过程已经演示完毕。刚才也说了,哈夫曼树的用处还有很多,我们能够创建他,也只是完成其中最基础的要求,我们不能止步于此。当然,我们不能认为这些东西很简单,就去轻视他,自己没有动手做过,你是不会知道什么叫做说着简单做着难的。
好啦, 之后我们会通过一个文件压缩程序的演示,其中包括了哈弗曼编码的生成,对象的序列化,文件的读出与写入等问题,跟大家进一步分享哈弗曼在数据编码上的用途。
相关推荐
- 重复:将新的二叉树加入到排序队列中,再次取频率最低的两个节点进行合并,直到只剩下一个节点,即为哈弗曼树。 3. **哈弗曼编码的生成** - 左孩子代表0,右孩子代表1。从根节点到每个叶子节点的路径形成该...
哈弗曼编码是一种高效的数据压缩方法,主要用于无损数据压缩,由哈弗曼在1952年提出。它的核心思想是通过构建最优的二叉树(哈弗曼树)来为每个输入符号分配最短的唯一二进制编码,使得最频繁出现的符号拥有最短的...
通过对源代码的阅读和理解,你可以深入学习哈弗曼编码的内部工作原理,并掌握如何在实际编程项目中应用这一技术。 哈弗曼编码的优化和变种包括动态调整哈弗曼树、变长码处理、以及结合其他编码方式如游程编码,以...
哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树
在C语言下实现哈弗曼树的创建并进行哈弗曼编码,同时输出哈弗曼编码。
根据给定的信息,本文将详细解释哈弗曼编码这一经典问题及其在C++中的实现。 ### 哈弗曼编码简介 哈弗曼编码(Huffman Coding)是一种广泛应用于数据压缩领域的编码方法,由David A. Huffman于1952年提出。其核心...
哈弗曼编码译码 哈弗曼树的建立,编码 对26个大写英文字母以及空格键的编码,译码
通过阅读和理解这段代码,你可以学习到如何在实际编程中应用哈弗曼编码和树的数据结构,这对于理解和优化数据压缩算法会有很大帮助。同时,这个源代码还可以作为学习C++编程和数据结构的实例,特别是涉及优先队列、...
哈弗曼树,又称最优二叉树或最小带权路径长度树,...这可能是一个学习资源,帮助理解哈弗曼编码的构建、编码和解码过程。通过阅读和理解这样的模板,可以加深对哈弗曼编码算法的理解,并能应用于实际的压缩和通信场景。
哈弗曼树(Huffman Tree),也称为最优二叉树,是一种特殊的二叉树结构,广泛应用于数据压缩领域。在信息编码中,哈弗曼编码是一种可变长度的前缀编码方式...通过学习和掌握哈弗曼编码,可以提高数据存储和传输的效率。
哈弗曼编码(C语言) 哈弗曼编码是一种变长前缀编码,用于无损数据压缩。该编码方法利用了字符出现频率的差异,高频字符使用短码,而低频字符使用长码。哈弗曼树是哈弗曼编码的核心结构,通过构建哈弗曼树,可以...
### 哈弗曼算法及其实现 哈弗曼算法是一种在数据压缩领域广泛应用的算法,主要用于构建一种称为哈弗曼树(Huffman Tree)的数据结构。这种算法由David A. Huffman于1952年提出,其核心思想是通过贪心算法来构造一个...
通过学习哈弗曼编码,不仅可以理解数据压缩的基本原理,还能掌握一种重要的算法思想——贪心算法,即每一步都采取当前最优的选择,以期望达到全局最优。哈弗曼编码的实现也是理解和实践数据结构(如二叉树、优先队列...
通过学习和实践哈弗曼编码,我们可以深入理解数据压缩的基本原理,并能灵活应用到实际问题中。在本项目中,学生可以通过编写代码,亲身体验哈弗曼编码的压缩与解压过程,提升自己的编程能力和对数据结构的理解。
哈弗曼编码是一种高效的数据压缩方法,由美国学者大卫·哈弗曼于1952年提出,广泛应用于数据通信、文件压缩等...通过对这些代码的分析和学习,我们可以深入理解哈弗曼编码的工作原理,并能够实际应用到自己的项目中。
【哈弗曼编码】是一种高效的前缀编码方法,主要用于数据压缩。它的基本思想是通过构建一棵特殊的二叉树(哈弗曼树)来为每个字符或符号分配唯一的二进制编码,使得出现频率高的字符拥有较短的编码,而出现频率低的...
理解并实现哈弗曼树和哈弗曼编码对于深入学习数据结构和算法非常重要,它不仅有助于提升编程能力,也有助于理解信息压缩的基本原理。通过分析和运行提供的代码,你可以更直观地了解这一过程,并将其应用到实际项目中...
### 哈弗曼编码与解码 哈弗曼编码是一种广泛应用在计算机科学中的编码方式,主要用于数据压缩。它基于二叉树结构实现,并利用字符出现的频率来构造一棵特殊的二叉树——哈弗曼树(又称最优二叉树)。在本篇内容中,...