本篇文章是介绍树与二叉树知识点的最后一篇文章，主要简单的介绍了哈夫曼树与哈夫曼编码

最优树的定义

结点的路径长度：从根结点到该结点的路径上分支的数目

树的路径长度：树中每个结点的路径长度之和

树的带权路径长度：树种所有叶子结点的带权路径之和WPL(T) = Σwkjk（对所有叶子结点，权值*分支数）

在所有含n个叶子节点、并带有相同权值的m叉树中，必存在一棵带权长度路径取最小值的树，称为“最优树”

如何构造最优树

（哈夫曼算法）以二叉树为例：

1）根据给定的n个权值{w1,w2,w3,…,wn}，构造n棵二叉树的集合F = {T1,T2,…,Tn}，其中每棵二叉树中均只含有一个带权值为wi的根节点，其左、右子树为空树
2）在F中选取其根节点的权值为最小的两棵二叉树，分别作为左右子树构造一颗新的二叉树，并置这棵新的二叉树的根节点的权值为其左、右子树根节点的权值之和
3）从F中删除这两棵树，同时加入刚生成的新树
4）重复2）3）两步，直至F中只含有一棵树为止

哈夫曼编码思想:将构成电文的每个不同字符都作为一个叶子结点，其权值为电文中字符的使用频率或者次数，构造哈夫曼树。此哈夫曼树中从根到每个叶子结点都有一条唯一的路径，对路径上各分支约定，左分支标识为“0”码，右标识为“1”码，则从根节点到叶子结点的路径上分支的“0”“1”码组成的字符串即为该叶子结点的哈弗曼编码。

前缀编码：若要设计长短不等的编码，则必须是任一个编码的字符都不是另外一个编码的前缀，这种编码称为前缀编码

哈夫曼编码是编码总长最短的前缀编码，因为每一个码值所代表的结点皆为叶子结点，其没有孩子结点，所以其编码不是另外一个编码的前缀。

举例：数据传送中的二进制编码，要传送数据：state,seat,act,tea,cat,set,a,eat，如何使传送的长度最短？

首先规定二叉树的构造为：左走为0，右走为1

为了保证长度最短，先确定字符出现的次数，然后将出现次数当做权，如下所示：

1
2

字	   符：	s	t	a	e	c
字符出现次数：	3	8	7	5	2

然后构造哈夫曼树，则有如下编码：

1
2
3

000		001		01		10		11
2		3		5		7		8
c		s		e		a		t

所以有state的编码为00111101101

上文所构造的编码满足哈夫曼编码的最短最优性质：

1）若di!=dj（字母不同），则对应的树叶不同，因此前缀码不同，一个路径不可能是其他路径的一部分，所以字母之间可以完全区别
2）将所有字符变为二进制的哈夫曼编码，使带权路径长度最短

总结

构造哈夫曼树的常见错误：在合并中不是选取根节点权值最小的两棵二叉树（包括已合并的和未合并的），而是选取未合并的根节点权值最小的一颗二叉树和已经合并的二叉树合并（这种选法是不对的）

对哈夫曼树的总结

• 用n个权值（对应n个叶子结点）构造哈夫曼树，共需要n-1此合并，即哈夫曼树中非叶子结点的总数为n-1，总结点个数为2n-1
• 哈夫曼树中没有度为1的结点，因为非叶子结点都是通过两个结点合并而来的。但是，没有度为1的二叉树并不一定是哈夫曼树
• 用n个权值构造的哈夫曼树结构并不是唯一的

对哈夫曼编码的小结

• 哈夫曼编码是能使电文代码总长最短的编码方式。此结论由哈夫曼树是带权路径最小的树的特征可得
• 哈夫曼编码是一种前缀编码，保证其在译码是不会出现歧义。因为，在哈夫曼编码中，每个字符都是叶子结点，而叶子结点不可能从根结点到其他叶子结点的路径上，所以一个字符的哈夫曼编码不可能是另外一个字符的哈夫曼编码的前缀
• 深度为h的哈夫曼树，其叶子结点的最大编码长度是h-1