数据结构|哈夫曼树

最优二叉树又称哈夫曼树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。

哈夫曼树是二叉树中带权路径长度最小的二叉树。

构造最优二叉树的哈夫曼算法如下：

1）根据给定的n个权值｛w1,w2,…,wn｝,构成n棵二叉树的集合F=｛T1,T2,…,Tn｝，其中，每棵树Ti中只有一个带权为wi的根结点，其左、右子树均空。

2）在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的取值为其左、右子树根结点的权值之和。

3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。

重复2）、3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。

由此算法可知，以选中的两棵子树构成新的二叉树，哪个作为左子树，哪个作为右子树，并没有明确。所以，构造的二叉树不唯一，但其带权路径长度是唯一确定的。

当给定了n个权值后，构造的最优二叉树中的结点数目m就确定了，即m=2*n-1。