哈夫曼树

• 结点的权：有某种现实含义的数值（如: 表示结点的重要性等）

• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

• 树的带权路径长度 WPL：树中所有叶子 结点的带权路径长度之和（WPL，Weighted Path Length）

  $$WPL=\sum _{i=1}^n{w}_i{l}_i$$

  

哈夫曼树的特点：

1. 每个初始结点最终都成为叶子结点，且权值越小的结点到根结点的路径长度越大
2. 哈夫曼树的结点总数为 2n₀-1,非叶子结点的总数为n₀-1
3. 哈夫曼树中不存在度为 1 的结点
4. 哈夫曼树并不唯一，但 WPL 必然相同且为最优

错题集

1. 

   答案与解析：

   
   答案： C
   解析：
   如图是长度为 4 时所有编码的可能性，绿色实心圆表示题目中的已知 绿色空心圆即为最多可得到的字符编码