本文主要是介绍最优二叉树（哈夫曼树）知识点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
路径：在一棵树中从一个结点往下到孩子或孙子结点之间的通路
结点的路径长度：从根节点到该节点的路径上分支的数目
树的路径长度：树中每个结点的路径长度之和
结点的权：给树中的结点赋予一个某种含义的值，则该值为该节点的权
结点的带权路径长度：结点的路径长度乘以结点的权
树的带权路径长度（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,5 
取出6,7 
取出7,9 
取出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
这篇关于最优二叉树（哈夫曼树）知识点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
