哈夫曼树

哈夫曼编码有等长和不等长之分。

等长

$n$个编码最多可以放$2^n$个字符。

不等长

要求：

• 频率越高，长度越短；
• 一个字符编码不能是另一个字符编码前缀，即不能有二义性；
• 编码只有$0$和$1$.

哈夫曼树

假如说现在有一个字符串aaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcdddfee

则里面的a有$3$个，b有$30$个，c有$1$个，d$3$个，e$2$个，f$1$个。

则我们编码规则左$0$右$1$。

那么我们先去两个最小的字符c,f，构成节点如下所示：
c1 f1，合并得

 []2
 /  \
c1  f1

再选一个最小的：

   []4
  /   \
 []2   e2
 /  \
c1  f1

递归即可。

成果：

         []40
        /    \
       []10   a30
      /   \
     []7   d3
    /   \ 
   []4   a3
  /   \
 []2   e2
 /  \
c1  f1