04月
01

发表于 • 字数统计 4323 • 被 1,375 人看爆

简介

哈夫曼树又称最优树，是一类带权路径长度最短的树

最优二叉树(哈夫曼树)

1.树的路径长度

树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

2.树的带权路径长度(WPL)

结点的权: 在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度: 结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度(WPL): 定义为树中所有叶结点的带权路径长度之和。

3.最优二叉树或哈夫曼树

带权路径长度WPL最小的二叉树称为最优二叉树 或 哈夫曼树 。

完全二叉树一定是最优二叉树，否则不一定是最优二叉树

例

给定4个叶子结点a, b，c和d，分别带权8，5，4和2。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为:
(a):WPL=8×3+5×3+2×1+4×2=49
(b):WPL=8×3+5×2+2×3+4×1=44
(c):WPL=8×1+5×2+2×3+4×3=36
其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

哈夫曼树示例.png

哈夫曼算法

1.构造哈夫曼树方法

  • ①将给定的权值按照从小到大排列成{W1，W2，… ，Wm}，并且构造出树林F={T1, T2, ..., Tm}。此时，其中的每棵树Ti(1≤i≤m)为左、右子树均为空的二叉树，二叉树的根结点的权值为Wi。
  • ②把F中树根结点的权值最小的两棵二叉树T1和T2合并为一棵新的二叉树T(T的左子树为T1，右子树为T2），并令T的根结点的权值为T1和T2的根结点的权值之和，然后将T按其根结点的权值大小依次加入到树林F中。同时，从F中删去T1和T2这两棵二叉树。
  • ③重复步骤②，直到构造成一棵哈夫曼树。

构造过程：
哈夫曼树构造过程.png

例

用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_____

解答

用6个权值构造的过程如下图
构造哈夫曼树示例.png
构造的哈夫曼树的带权路径长度=(16+18+30）2+133+(6+7)*4=219

2.哈夫曼算法实现

算法分析

第一步： 初始森林中共有n棵只含有根结点的二叉树
第二步： 将当前森林中的两棵根结点权值最小的二叉树，合并成一颗新的二叉树
第三步： 每合并一次就产生一个新结点，森林中相应减少一颗树。

显然要进行n-1次合并，所以共产生n-1个新结点，它们都具有两个孩子的分支结点
由此可知，最终求得的哈夫曼树中一共有2n-1个结点，其中n个叶结点是初始森林的n个孤立结点。
并且哈夫曼树中没有度数为1的分支结点，可用大小为2n-1的一维数组来存储哈夫曼树中的结点

哈夫曼树存储结构

#define n 100       //叶子结点数
#define m 2*n-1     //哈夫曼树中结点总数
typedef struct{
    float weight;   //权值
    int lchild, rchild, parent;        //左右孩子及双亲指针，可通过parent的值是否为0来区分当前双亲结点是根与非根结点
}BTNode;                                //树中结点类型
typedef HTNode HuffmanTree[m+1];        //0号单元不用，表示空指针

实现步骤

  • (1)将哈夫曼树组HT[1...m]中的2n-1个结点初始化，将各结点中的三个指针均置空(即置为0)，权值也置为0
  • (2)读入n各权值，存入数组HT的前n个元素中，它们是初始森林中n个孤立的根结点上的权值
  • (3)对森林中的树进行n-1次合并，共产生n-1个新结点，依次存入数组HT的第i个元素中(n+1 ≤ i ≤ m)中。每次合并步骤如下：
    • ①在当前森林的所有结点HT[j](1 ≤ j ≤ i-1)中选取具有最小权值和次小权值的两个根结点，分别用s1和s2记住这两个根结点在数组中的下标
    • ②将根为HT[s1]和HT[s2]的两棵树合并，使其成为新结点HT[i]的左右孩子，得到一颗以新结点HT[i]为根的二叉树，同时修改HT[s1]和HT[s2]的双亲域parent，使其指向新的结点ht[i]，并将HT[s1]和HT[s2]的权值之和作为新结点HT[i]的权值

3.哈夫曼树的特点:

  • ①在哈夫曼树中，权值越大的叶子离根结点越近。
  • ②若有n0个权值，需要进行n0-1次合并，构造成为哈夫曼树。
  • ③哈夫曼树没有度为1的结点。
  • ④由n0个权值构成的哈夫曼树，叶结点数为n0，度为2的结点数为n0-1，结点总数为n0+ n2= n0+ n0-1=2n0-1。
  • ⑤给定一组权值，构造出的哈夫曼树的形态可能不唯一，但它们的带权路径长度都一样。

哈夫曼编码

利用哈夫曼树求的用于通信的二进制编码
树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树的分支表示"0"码，指向右子树的分支表示"1"码，取得每条路径上的"0"或"1"的序列作为各个叶子结点对应的字符编码
设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。

编码概念

(1)编码和解码

数据压缩过程称为编码。即将文件中的每个字符均转换为一个唯一的二进制位串。
数据解压过程称为解码。即将二进制位串转换为对应的字符。

(2)前缀码方案

对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。

例1

哈夫曼编码树.png

如图(a)所示哈夫曼树，左分支表示字符"0"，右分支表示字符"1"，则以根结点到叶结点路径上的分子字符组成串作为该叶结点的字符编码，可得到字符a、b、c、d的二进制前缀编码分别为0、10、110、111

如图(b)所示哈夫曼树，左分支表示字符"0"，右分支表示字符"1"，可得到字符a(0110)、b(110)、c(0111)、d(000)、e(111)、f(10)、g(001)、h(010)的二进制前缀编码

例2

假设通信电文使用的字符集为{a，b，c，d， e， f，g， h)，各字符在电文中出现的频度分别为:7，26，2，.28，13，10，3，11，试为这8个字符设计哈夫曼编码。
要求
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值);
(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

解答

【解析】先按昭权值构造哈夫曼树，注意要满足题目的要求:树中左孩子结点的权值不大于右孩子结点的权值。构造过程如下图:
哈夫曼编码示例解答1.png
哈夫曼编码示例解答2.png
到这里就很容易写出每个字符的哈夫曼编码了。
【答案】
哈夫曼编码示例解答3.png
(2) 各字符的编码: a(0101), b(10), c(01000), d(11), e(011), f(000), g(01001), h(001)
注意： 每个字符的编码都不是另外一个编码的前缀。

分享到：