考研数据结构 06 哈夫曼树

发布于 2021-09-13  136 次阅读


图1
图1:哈夫曼树的建立

1. 平均带权路径长度

  下面来计算哈弗曼树的平均带权路径长度:

长度 = 所有(节点值 * 高度)
// 高度从0开始计算。

例如,上图的平均带权路径长度为

Dist =
F(1) * 4 +
D(1) * 4 +
T(3) * 3 +
E(4) * 2 +
R(5) * 2 +
A (8) * 2
= 51

2. 哈夫曼编码

  对于上面的例子哈夫曼编码:

E: 00
R: 01
A: 11
T: 011
F: 0100
D: 0101