基本概念

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

哈夫曼编码：依据字符出现概率来构造异字头的平均长度最短的码字的编码方法，称之为哈夫曼编码

理解：

哈夫曼树，即该二叉树满足所有叶子结点的带权路径（路径长度与结点权值的乘积）之和最小

哈夫曼编码，即将字符出现概率当成叶子结点权值，进行构造哈夫曼树，而后所有父结点的左子树为0，右子树为1，对字符进行编码的方法，称之为哈夫曼编码

哈夫曼树

如何构建哈夫曼树 重点

假设我们要将 7 19 2 6 32 3 21 10这8个叶子结点构造二叉树，如下

一般二叉树，构建完成如下：

权值计算：（7+19+2+6+32+3+21+10）*3= 300

哈夫曼树构造过程

1.取最小的两个叶子结点构成二叉树

2.将生成的父结点放入原来的叶子结点集，继续构建（取最小的两个叶子结点构成二叉树）

3.继续构建，但是我们发现此时最小的两个结点分别为7和10，均小于新增的叶子结点11，这是我们需要重新进行构建，即当我们取两个最小值时，如果不包括新增的叶子结点，我们需要新建一个二叉树，如下

4.重复上述步骤

权值计算：2*5 + 3*5 + 7*4 + 10*4 + 6*4 + 32*2 + 19*2 + 21*2 = 261

实际权值最小，可以再自行构建其他二叉树进行验证

哈夫曼编码 

如果需传送的电文为 ‘ABACCDA’，即：A, B, C, D 的频率（即权值）分别为 0.43, 0.14, 0.29, 0.14，试构造哈夫曼编码

转为上述哈夫曼二叉树，即为 四个结点 43 14 29 14 进行构建二叉树

此时则 A的编码为0 ，B的编码为110，C的编码为10，D的编码为111

实际问题

1.一般给出叶子结点求哈夫曼树

2.根据字符出现频率求哈夫曼编码

解题思路：

1.依次取最小的两个结点进行构建

2.注意新二叉树的构建和连接