在数据结构与算法中,人们把最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树.
*路径是从树中一个节点到另一个节点之间的通路,路径上的分支数目称为路径长度.
*树的路径长度是从树根到每一个叶子之间的路径长度之和.
*节点的带权路径长度为从该节点到树根之间的路径长度与该节点树的乘积.
记为：
x09x09n
x09wpl = Σ Wk.Lk
x09x09k=1
其中,n为带权叶子节点数目,Wk为叶子节点的权值,Lk为叶子节点到根的路径长度
对应于霍夫曼树的算法也叫做霍夫曼算法.此算法的思想是： （1）设给定的一组权值为{W1,W2,W3,……Wn},据此生成森林F={T1,T2,T3,……Tn},F 中的没棵二叉树只有一个带权为W1的根节点（i=1,2,……n）. （2）在F中选取两棵根节点的权值最小和次小的二叉树作为左右构造一棵新的二叉树,新二叉树根节点的权值为其左、右子树根节点的权值之和. （3）在F中删除这两棵最小和次小的二叉树,同时将新生成的二叉树并入森林中. （4）重复（2）（3）过程直到F中只有一棵二叉树为止.
扩充方法如下,例：
（10,12,16,21,30）,权值从小到大（10-30）.
1）将5个节点看成是5棵二叉树,它们的根节点是这5个节点,它们的左右子树均空,所以不画出它们的左右子树：
2）选出根节点的权值最小的两棵二叉树,作为左右子树构造成一棵新的二叉树,且置新的二叉树的根节点的权值为其左右子树根节点权值之和.（至于哪棵子树作为新的二叉树的左/右子树,没有硬性规定,不过我们一般习惯将根节点的权值小的那个二叉树作为新的二叉树的左子树.）
先选出最小和次最小的两个根10,12 ,组合成一个二叉树,（括号为左右子树的权值之和）
(22)
/
10 12
然再从16,21,(22),30 中选出最小和次最小的两个根 16,21,组合成二叉树,
(37)
/
16 21
继续从(22),30,(37)中选出最小的和次最小的根(22),30组合
(52)
/
(22) 30
/
10 12
继续从(52)(37)中选出最小的和次最小的根(72),37组合
x09x09(81)
x09x09/
(52)x09x09(37)
/ \x09x09/
(22) 30x09x0916 21
/
10 12
最终得到树如下图
x09 ()
x09 /
()x09 ()
/ \x09 /
() 30x09 16 21
/
10 12
** 带权路径长度答案是 ＝ (10+12) *3 + (30+16+21)*2 = 200