考研数据结构 06 哈夫曼树

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

图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