什么是哈夫曼树 ​

示例 ​

定义 ​

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

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

WPL

哈夫曼树构造 ​

每次把权值最小的两棵二叉树合并，且权值最小的两棵二叉树的和继续与后面的数比较，选出两个最小的数重复以上操作步骤。整体复杂度为O(NlogN)

哈夫曼数特点 ​

哈夫曼编码 ​

前缀码prefix code：任何字符的编码都不是另一个字符编码的前缀（可以无二意的解码）。