java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
所谓哈夫曼树就是要求最小加权路径长度,这是什么意思呢?简而言之,就是要所有的节点对应的路径长度(高度 - 1)乘以该节点的权值,然后保证这些结果之和最小。下面这篇文章就给大家详细介绍
前言
我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的 "最优二叉树",为了纪念他呢,我们称之为 "哈夫曼树"。哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等。今天一起来看看哈夫曼树到底是什么东东。
概念
当然,套路之一,首先我们要了解一些基本概念。
1、路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度。
2、树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全二叉树就是这种路径长度最短的二叉树。
3、树的带权路径长度:如果在树的每一个叶子结点上赋上一个权值,那么树的带权路径长度就等于根结点到所有叶子结点的路径长度与叶子结点权值乘积的总和。
那么我们怎么判断一棵树是否为最优二叉树呢,先看看下面几棵树:
他们的带权长度分别为:
WPL1:7*2+5*2+2*2+4*2=36
WPL2:7*3+5*3+2*1+4*2=46
WPL3:7*1+5*2+2*3+4*3=35
很明显,第三棵树的带权路径最短(不信的小伙伴可以试一试,要是能找到更短的,估计能拿图灵奖了),这就是我们所说的 "最优二叉树(哈夫曼树)",它的构建方法很简单,依次选取权值最小的结点放在树的底部,将最小的两个连接构成一个新结点,需要注意的是构成的新结点的权值应该等于这两个结点的权值之和,然后要把这个新结点放回我们需要构成树的结点中继续进行排序,这样构成的哈夫曼树,所有的存储有信息的结点都在叶子结点上。
概念讲完,可能有点小伙伴还是 "不明觉厉"。
下面举个例子构建一下就清楚了。
有一个字符串:aaaaaaaaaabbbbbaaaaaccccccccddddddfff
第一步,我们先统计各个字符出现的次数,称之为该字符的权值。a 15 ,b 5, c 8, d 6, f 3。
第二步,找去这里面权值最小的两个字符,b5 和 f3,构建节点。
然后将 f3 和 b5 去掉,现在是 a15,c8,d6,fb8。
第三步,重复第二步,直到构建出只剩一个节点。
现在是 dfb14,a15,c8。
最后,
ok, 这样我们的哈夫曼树就构造完成了。
构建的步骤
按照上面的逻辑,总结起来,就是一下几个步骤:
来源: http://www.phperz.com/article/17/1120/360216.html