哈夫曼树

• 定义：带权路径长度 (WPL) 最小的二叉树，也称最优二叉树。
• WPL 计算公式： $WPL={\sum }_{k=1}^n{w}_k\times l_k$ 其中 $w_k$ 是叶子权值，$l_k$ 是路径长度（层数-1）。
• 构造算法 (Huffman Algorithm)：
  1. 选两棵根权值最小的树。
  2. 合并为一棵新树，根权值为左右子树之和。
  3. 新树放入集合，删除原两棵树。
  4. 重复直到剩下一棵。
• 应用：哈夫曼编码 (前缀编码，保证无歧义)。