最优二叉树（哈夫曼树）知识点

路径：在一棵树中从一个结点往下到孩子或孙子结点之间的通路

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

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

结点的权：给树中的结点赋予一个某种含义的值，则该值为该节点的权

结点的带权路径长度：结点的路径长度乘以结点的权

树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度 (Weight Path Length)

最优二叉树（哈夫曼树）：带权路径长度最小的二叉树

构造哈夫曼树：

给定n个权值{w1,w2,…wn}，则构造出的哈夫曼树有n个叶子结点,构造过程如下：

1. 将w1,w2…wn按从小到大排序，并将他们看做n棵只有一个结点的树组成的森林；

2. 选出两个根节点权值最小的树合并，作为新树的左右子树，新树的根节点权值是左右子树根节点权值之和

3. 从森林中删除选取的两棵树，将新树加入森林

4. 重复2,3，直到只剩一棵树，所得即为最优二叉树

实例如下：给定权值{5,6,2,7,9}构造哈夫曼树

解：(1)排序后为w={2,5,6,7,9}

取出2,5w={6,7,7,9}

取出6,7w={7,9,13}

取出7,9 w={13,16}

取出13,16

上面的哈夫曼树的wpl=6X2+7X2+2X3+5X3+9X2=65

哈夫曼树在编码中的应用：

在通讯中，经常需要将文本转换成二进制串，即编码。为了使电文代码尽可能的短，需要另经常使用的字符采用短的编码，使用频率小的字符采用长的编码。同时，一个字符的编码不能包含另一个字符的编码，例如A是00，B就不能是001，使用哈夫曼树就可以很好的实现 ,

例如A,B,C,D,E的频率分别是6,7,2,5,9对应的哈夫曼树为：

另左子树的路径为0，右子树路径为1

则A:00 B:01 C:100 D:101 E:11