哈夫曼编码树例题_哈夫曼树的构造_哈夫曼编码树

哈夫曼树又称最优二叉树，是一种带权路径长最短的树。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权（比如字符在某串中的使用频率）的乘积。

比如有一串字符串如：3334444555556666667777777，它是由3、4、5、6、7这五个数字组成的，现要使用一种编码方式，让它编码存储最短，如何做？如果五个数使用3位的定长的

二进制就可表示，如：(3:000) (4:001) (5:010) (6:100) (7:101)，则编码后的存储空间需 3 * (3 + 4 + 5 + 6 + 7) = 75 比特位。能否有一种压缩的方法把存储空间缩小？这就是Huffman编码，它是一种不等长编码，这就要求一个字符编码的不是另一个字符编码的前缀，它是一种最优前缀编码。这需要一开始就需要统计出每个字符出现的频率，然后基于这些频率来设计出编码树，将可以节省大量的空间。利用字符出现的频率决定编码这一思想是Huffman编码的基础，Huffman编码是所有无前缀编码中最优的一种编码策略。Huffman编码是Unix中compress工具的基础，也是联合图的是专家组(JPEG)编码过程上的一部分。

人们在数据压缩领域使用了优先级队列。给定一段消息，可以对每个字符进行无前缀的编码，使其编码长度具有最少的比特位。哈夫曼编码树使用Huffman树，可以得到这种最小编码。Huffman树是这样一棵完全的二叉树，它的每个叶节点都表示一个原消息中的不同字符，每个左分支都标为0，而每个右分支都标示为1。沿着根节点到叶节点字符的路径，将该路径中的分支标签依次组合起来，就可以得到该字符的Huffman编码。

下面给出二种编码的二叉树，但只有第二种是最优二叉树：

(:25)

0/ \1

(:18) 7

0/ \1

(:7) (:11)

0/ \1 0/ \1

3 4 5 6

权值 = (3 + 4 + 5 + 6) * 3 + 7 * 1 = 61（非最优二叉树）

(:25)

0/ \1

(:11) (:14)

0/ \1 0/ \1

5 6 7 (:7)

0/ \1

3 4

权值 = (3 + 4) * 3 + 7 * 2 + (5 + 6) * 2 = 57（最优二叉树）

因此，五个数的编码为 (3:000) (4:001) (7:01) (5:10) (6:11)，从这些不等长编码来看，不存在一个字符的编码是另一个字符编码的前缀。一个保证无前缀比特编码的方法是创建一棵二叉树，它的左分支通常使用0来表示，而右分支用1来表示。如果每个已编码的字符都在树的叶子上，那么该字符的编码就不可能是其它字符编码的前缀，换句话说，到达每个字符路径正好是一个无前缀编码。

哈夫曼树的构造过程：从原始元素集合T中拿出两个频度最小的元素组成一个二叉树，二叉树的根为这两个节点频度的和，然后从集合T中删除这两个元素，把根元素加入到T集合中，如此反复直集合T为空。

那么我说究竟如果实现上面叙述的思想呢？

在统计完每个字符出现的频率之后，按照频率递增的顺序将每个字符—频率对插入到一个优先级队列中，即优先队列中具有最高优先级的字符—频率对中的字符具有最小的出现频率，这些字符将在离Huffman树根最远的叶子节点外结束，因此它们的编码具有最多的比特位。相反，出现频率最高的字符将具有最小的比特位编码。

首先将下列字符—频率对插入到优先队列中：

（3:3）（4:4）（5:5）（6:6）（7:7）

形成的初始堆如下：

3

/ \

4 5

/ \

6 7

基于字符—频率对组成的优先级队列所构造的二叉树称作Huffman树，我们将自底向上构建Huffman树。现假设所有字符元素都已按使用频率添加到了优先级队列中去了，即初始堆已构造好（如上述所示），下面开始构建Huffman树：

首先调用两次优先级队列的removeMin方法，得到两个频率最低的字符。“3”是第一个被删除的元素，即第一个出队的元素，它成为二叉树的左叶子节点，而“4”成为右叶节点，它们两者的频率之和（:7）成为树的根节点，并又将根（:7）添加到优先级队列中，现在得到如下的Huffman树：

(:7)

0/ \1

3 4

此时优先级队列中包含：

（5:5）（6:6）（7:7）（:7）

堆结构如下：

5

/ \

6 7

/

(:7)

然后，删除5、6，但它们不能直接连先前哈夫曼树中，因为它们元素都不在哈夫曼树中。因为它们成为另一棵树的左子叶节点和右子叶节点，且该树的根是它们的频率之后（:11），根将入到优先级队列中，现在有两棵Huffman树：

(:11) 和 (:7)

0/ \1 0/ \1

5 6 3 4

此时，优先级队列中包含的元素如下：

(7:7) (:7) (:11)

堆结构如下：

7

/ \

(:7) (:11)

再然后，当(:7)被删除时，它成为二叉树的左分支，而另一个被删除的7元素则是树的右分支，两者频率之和成为二叉树的根(:14)，入优先级队列中。由于(:7)在树中，所以这一次在原来已有的某树上进行扩充，这样就得到下面Huffman树：

(:11) 和 (:14)

0/ \1 0/ \1

5 6 7 (:7)

0/ \1

3 4

此时优先队列中包含：

(:11) (:14)

堆结构如下：

(:11)

/

(:14)

最后，删除(:11)与(:14)两个节点，由于这两个节点都存在于已创建好的Huffman中，所以这次实质上这次是合并这两个Huffman树，最后形成最终的Huffman树：

(:25)

0/ \1

(:11) (:14)

0/ \1 0/ \1

5 6 7 (:7)

0/ \1

3 4

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29185-1.html