注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。
- 二叉树：每个结点最多含有两个子树的树称为二叉树。
- 定理：对于具有n个叶子结点的哈夫曼树,共有2n-1个结点。
哈夫曼树介绍
1哈夫曼树的定义
哈夫曼（Huffman）树,又称最优二叉树，是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。给定n个数值{ W1,W2,…,Wn}，若将它们作为n个结点的权，并以这n个结点为叶子结点构造一颗二叉树，那么就可以构造出多棵具有不同形态的二叉树，其中带权路径长度最短的那棵二叉树称为哈夫曼树，或称最优二叉树。如图（二）所示：
WPL：树中从根到所有叶子结点的各个带权路径长度之和
2 构建哈夫曼树的方法
如下:
(1) 初始化：根据给定的n个权值{W1,W2,….,Wn}构造n棵二叉树的森林T{T1,T2,…Tn}，其中每棵二叉树Ti (1≤i≤n)中都只有一个带权Wi为的根结点，其左、右子树均为空。
(2) 找最小树：在森林T中选取两棵结点权值最小的子树分别作为左、右子树构造一棵新的二叉树、且使左子树的权值小于右子树的权值、且置新的二叉树的根结点的权值为其左、右子树上根结点权值之和。
(3) 删除与加入：在森林T中，删除这二棵树，同时将新得到的二叉树加入Ｔ中。
(４) 判断：重复(2)与(3)操作，直到T只含一棵二叉树树为止，这棵树便是哈夫曼树。如图（三）所示：
因为权值的不同，哈夫曼树的样子有点不同，为了加深对哈夫曼树构建过程的认识，笔者再列举一个哈夫曼树的构建，见图（四）：
（1）8个结点的权值大小如下：
（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。
（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。
（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。
（ 注：如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）比如比较最小两个 7 10 11 所以只能另起一个
（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。
（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。
（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。
（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。
Original: https://www.cnblogs.com/2zly/p/13405836.html
Author: 颖火虫赵云
Title: 哈夫曼树的构建与最小带权路径长度
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/590493/
转载文章受原作者版权保护。转载请注明原作者出处！