|
一 赫夫曼树相关概念的理解 赫夫曼树，既然是一种带权路径长度最短的树，这里就牵扯到“路径”、“路径长度”、“树的路径长度”、“结点的带权路径长度”以及“树的带权路径长度”的相关概念的理解。 1 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 2 路径长度：径路上的分支数目。 3 树的路径长度：从树根到一每结点的路径长度之和。 4 结点的带权路径长度：从该结点到树根之间的路径长度与结点上 权的乘积。 5树的带权路径长度:树中所有叶子结点的带权路径长度之和。记作 WPL= Sum（wk*lk）。 二：赫夫曼树的构造 “（1）由给定的n个权值{W1，W2，…，Wn}构成n棵二叉树的集合F＝{T1，T2，…，Tn},其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。 （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； （4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。”【1】 在构造赫夫曼树的时候，一定要注意第三步，在F中删除所指的两棵树后，一定记住将新得到的二叉树加入F中。这一步，对于初学者来说，是非常容易出错的地方。本人就有深刻的体会。 例：设给定权集w={5,29,7,8,14,23,3,11},构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。
在构造赫夫曼树的过程中，在第二次选择两棵权值最小的树时，最小的两个作为左右子树的分别是7和8，而此时的8有两种，一种是原来权集中的，另一种是经过第一次构造出的新的二叉树的根的权值。（见下图） 所以，7与不同的8结合，便生成了不同的赫夫曼树，但是它们的WPL是相同的。计算过程如下： 树1：WPL=2×23+3×(8+11)+2×29+3×14+4×7+5×(3+5)=271 树2：WPL=2×23+3×11+4×（3+5）+2×29+3×14+4×(7+8) =271 三、赫夫曼编码及其应用 设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。 上述的权集可假想为由这样的情境得出： “有一份电文中共使用8种字符：☆，★，○，●，◎，◇，◆，▲，它们出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试着设计赫夫曼编码。”
在树1中，编码为 ☆：11110，★：10，○：1110，●：010， ◎：110，◇：00，◆：11111，▲：011 在树2中，编码为 ☆：0110，★：10，○：1110，●：1111， ◎：110，◇：00，◆：0111，▲：010 在其他方面赫夫曼树还有很多的应用。 比如，对压缩后的数据文件另外，若在构造赫夫曼树时，有诸如：“请按左子树根节点的权小于等于右子树根节点的权的次序构造”等的要求，则所求的赫夫曼树会有所不同，每个字符的赫夫曼代码也有所不同。应该根据具体的要求，去设计符合条件的赫夫曼树。 除此以外，赫夫曼树在其进行解码则必须借助于哈夫曼树T，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子时便译出相应的字符。然后重新从根出发继续译码，直至文件结束。赫夫曼树在判定问题中也有十分重要的应用。比如将百分制转换为五级分制。 |
|
|
