哈夫曼树及哈夫曼编码
Huffman Tree 简介
哈夫曼树(Huffman Tree),又称最优二叉树,是一类带权路径长度最短的树。
带权路径长度
带权路径长度即为叶子节点的权值乘以该叶子节点到根节点的路径长度。
哈夫曼树具有如下的特性:
- 对于同一组权值,可以得到的哈夫曼树并不唯一。
- 哈夫曼树的左右子树可以互换。
- 权值越大的节点越靠近根节点,权值越小的节点越远离根节点。
- 带权值的节点都是叶子节点,不带权值的节点都是某棵子二叉树的根节点。
Huffman Tree 构建
若给出以下字符
{A,B,C,D,E,F,G}
其出现频率为
{9,11,5,7,8,2,3}
则构建步骤为
- 选出最小的两个元素构成一个二叉树。
- 再次选出最小的元素构成一个新的二叉树。
- 重复上输出操作,将所有元素构建出一个最小二叉树。
此时该二叉树即为哈夫曼树,其WPL(带权路径长度)为:
WPL = ( 9 + 11 ) * 2 + ( 5 + 7 + 8 ) * 3 + ( 2 + 3 ) * 3 = 115
此哈夫曼树构造的编码方案为:
- A: 00
- B: 10
- C: 010
- D: 110
- E: 111
- F: 0110
- G: 0111