赫夫曼树及其应用

赫夫曼树及其应用：

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。如下图左图中根结点到结点D的路径长度为4.
树的路径长度就是从树根到每一结点的路径长度之和。下图中左图中的二叉树的树的路径长度为1+1+2+2+3+3+4+4=20，
右图中二叉树的树路径长度为1+2+3+3+2+1+2+2=16.（结点数目相同的二叉树中，完全二叉树时路径长度最短的二叉树）
如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。带权路径长度WPL最小的二叉树称为赫夫曼树（最优二叉树）。下图中左图中二叉树的WPL=5x1+15x2+40x3+30x4+10x4=315,右图中二叉树的WPL=5x3+15x3+40x2+30x2+10x2=220。这样的结果意味着在某些比较判断中会减少大量运算，提高性能。（满二叉树不一定是赫夫曼树，赫夫曼树中权越大的叶子离根越近，具有相同带权结点的赫夫曼树不唯一）

带权的二叉树

构造赫夫曼树：

1.根据给定的n个权值{w1,w2,……，wn}构成n棵二叉树的集合F={T1,T2,……，Tn},其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3.在F中删除这两棵树，同时将新得到的二叉树加入F中。
4.重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。
例：有5个结点a,b,c,d,e,权值分别为7,5,5,2,4，构造赫夫曼树
1.按照权值从小到大排序:d2,e4,b5,c5,a7,选最小的两个(d2,e4)构造新树，即为它们添加一个根结点N1，该根结点的权值为最小的两个的权值之和N1=2+4=6
2.去除d2,e4，添加N16，并重新排序，得到b5,c5,N16,a7,使用b5，c5构造新树，添加根结点N2，权值=5+5=10
3.去除b5,c5,添加N210,并中心排序，得到N16,a7,N210,依次类推，最终得到赫夫曼树。

赫夫曼树构造
注：赫夫曼树的结点的度为0或者2，没有度为1的结点，包含n个叶子结点的赫夫曼树中要经过n-1次合并才能形成赫夫曼树，共产生n-1个新结点，且度为2，共有2n-1个结点。

赫夫曼编码：

通常如果要传输一段字符，自然想到用固定长度的二进制（0和1）来表示，如果这一段字符很长，则要传输的二进制串也非常可怕，传输速度极慢。假设我们要传输“BADCADFEED”,每个字符的二进制表示如下表，则编码后为“001000011010000011101100100011”（共30个字符）。

普通编码
假设六个字母的频率分别为 A 27,B 8,C 15,D 15,E 30,F 5,构造赫夫曼树如下图左图所示。右图将权值左分支改为0，右分支改为1后的赫夫曼树。
对这六个字母用其从树根到叶子所经过的路径的0或1来编码，则可以得到每个字符的编码如下表所示。我们将“BADCADFEED”再次编码，得到新编码得到的二进制串“1001010010101001000111100”(共25个字符)，也就是说数据被压缩了，节省了传输/存储成本。
赫夫曼编码
编码中非0即1，长短不等的话是很容易混淆的，所以如果要设计长短不等的编码则任一字符的编码都不是另一个字符的前缀，这种编码称为前缀编码。仔细观察，上表中的编码不存在这种情况，不会混淆。
当我们接收到一串赫夫曼编码时，根据约定好的赫夫曼树即可进行解码。
一般地，设需要编码的字符集为{d1，d2，……，dn}，各个字符在电文中出现的次数或者频率集合为{w1，w2，……，wn}，以d1，d2，……，dn作为叶子结点，以w1，w2，……，wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列即为该结点对应字符的编码，这就是赫夫曼编码。