Huffman 树 ​

给定 n 权值作为 n 个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为 Huffman 树。

利用 Huffman 树对每一个字符编码，该编码又称为 Huffman 编码，Huffman 编码是一种前缀编码，即一个字符的编码不是另一个字符编码的前缀。

性质： ​

1. 对应一组权重构造出来的 Huffman 树一般不是唯一的

2. Huffman 树具有最小的带权路径长度

3. Huffman 树中没有度为 1 的结点

4. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近

5. Huffman 树的带权路径长度 WPL 等于各叶子结点的带权路径长度之和

详细资料可以参考： ​

• 《数据结构和算法—— Huffman 树和 Huffman 编码》
• 《详细图解哈夫曼 Huffman 编码树》