哈夫曼树(Huffman)

• 概念

  • 只有它的叶子节点存储着实际权重值
  • 实际权重值一般代表出现的频率，用来生成压缩编码，频率高的获得更短的二进制编码

• 构建原理

  • 1. 把所有权重节点放到一片森林里
  • 2. 每次选出权重值最小的两个节点，作为左节点和右节点，组成一棵树
  • 3. 树的根节点是两个权重值之和
  • 4. 把树加入森林中
  • 5. 重复第2步，直到剩下一个节点