|
|
| |
|
| |
| |
| 构造哈夫曼 |
|
[ 2007-3-22 14:04:00 | By: nin124 ] |
构造哈夫曼
net_hawk 发表于 2007-3-13 17:41:00 |
如何构造哈夫曼树？D.A.Huffman 最早研究出一个带有一般规律的构造算法，俗称哈夫曼算法，其基本思想是让权值最大的叶子离根最近。构造方法如下：
1) 由给定的n个权值{w1, w2, …, wn}，构造n棵扩充二叉树的集合F = {T1, T2, …,
Tn}，其中每棵扩充二叉树中均只含一个带权值wi的根结点,其左、右子树均为空;
2) 重复下列步骤，直到F中只含一棵树为止：
j 在F中选取其根结点的权值为最小的两棵扩充二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
k 从F中删去这两棵树，同时加入刚生成的新树;
3) 按上述步骤得到的二叉树就是哈夫曼树。
任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码 | | |
| 发表评论：
| | |
|
