哈夫曼树的构造：就是将给定的数据中选择最小的两个权值进行合并，然后重复该操作，构造出一个二叉树。使其带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。
例如：给定几个数值：0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.01
可以将其扩大一百倍，以方便计算，不会影响哈夫曼树的构造
W={7, 19, 2, 6, 32, 3, 21, 10}
选择最小的2，3进行合并为5，5 和 6 为最小的再进行合并为 11 ， 重复该操作可以得到该哈夫曼树。
哈夫曼编码：
在进行数据压缩的时候，为了使压缩后的数据文件尽可能短，可采用不定长编码。其基本思想是：为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。
编码的概念：
（1）前缀编码：如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。00，001这个就不是前缀编码。其实就是通过这些编码准确得出数据信息，不会混淆。
（2）哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各个支的赋值分别构成一个二进制，该二进制就称为哈夫曼编码
哈夫曼编码性质：
（1）哈夫曼编码是前缀编码
（2）哈夫曼编码是最优前缀编码
| 字母编号 | 出现频率 | 哈夫曼编码 | 等长编码 |
| 1 | 0.07 | 1100 | 000 |
| 2 | 0.19 | 00 | 001 |
| 3 | 0.02 | 11110 | 010 |
| 4 | 0.06 | 1110 | 011 |
| 5 | 0.32 | 10 | 100 |
| 6 | 0.03 | 11111 | 101 |
| 7 | 0.21 | 01 | 110 |
| 8 | 0.10 | 1101 | 111 |
由上面的例子得出该表
如何得出这个哈夫曼编码？以0.07扩大一百倍之后是7为例子讲解：
从叶子结点到根节点：7 ——> 17是左分支，所以赋予0
17 ——> 28是左分支，所以赋予0
28 ——> 60是右分支，所以赋予1
60 ——> 100是右分支，所以赋予1
哈夫曼编码是从根节点到叶子结点：所以0.07的哈夫曼编码是1100.
等长编码就相当于一个从根节点到叶子节点的路径为K的满二叉树，上面列表就是通过一个从根节点到叶子节点的路径为3的满二叉树得来的等长编码，方法和得到哈夫曼编码一样。
以0.07扩大一百倍后为7来讲解以下;
从叶子结点到根节点： 7——> 26 是左分支，所以赋予0
26 ——>34 是左分支，所以赋予0
34 ——>100是左分支，所以赋予0
等长编码是从根节点到叶子结点，所以等长编码是000
在对多个有序表进行两两合并时，若表长不同，则最坏的情况下总的比较次数依赖于表的合并次序（归并排序），可以借助哈夫曼树的构造思想，依次选择最短的两个表进行合并，这样可以获得最坏的情况下最佳的合并效率
