基本概念

• 路径：
  从一个节点到另一个节点所经过的分支构成这两个节点之间的路径

• 路径长度
  路径上的分支数量

• 树的路径长度
  从树根到每个节点的路径长度之和

• 节点的带权路径长度
  节点的权值乘以节点的路径长度就是节点的带权路径长度

• 树的带权路径长度
  所有叶子节点的带权路径长度之和

霍夫曼树

霍夫曼树，也叫最优二叉树，是带权路径长度最小的二叉树。

霍夫曼编码

做如下规定：

在霍夫曼树中，所有左分支都表示 0，所有右分支都表示 1，然后将从根节点到叶子节点的路径上的二进制位作为叶子节点的编码。因为在树中，一条路径不可能经过 2 个叶子节点，所以霍夫曼编码一定是前缀编码，即任意字符的编码不是其它字符的编码的前缀。

Python 实现

tim-chow 的 Github

参考文档

• http://blog.csdn.net/shuangde800/article/details/7341289