算法笔记：哈夫曼树、哈夫曼编码

1 字符的机内表示

2 前缀编码

• 字符只放在叶结点中
• 字符编码可以有不同的长度
• 由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀
• 前缀编码可被惟一解码

3 哈夫曼树

• 哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。
• 要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。

4 哈夫曼算法

可能看这个描述不太好理解，我们看一个例子：

4.1 举例

4.2 哈夫曼编码的生成

• 每个字符的编码是根节点到该字符的路径
  • 左枝为0，右枝为1