哈夫曼树的概念

一棵具有n个带权叶节点的二叉树，使得所有叶节点的带权路径长度（叶节点×叶节点到根节点的路径长度）之和最小，这样的二叉树被称为最优二叉树，也称为哈夫曼树（Huffman Tree)

例如，有四个叶子结点a、b、c、d，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其他许多种）分别如图a、b和c所示。

上图由四个叶子结点构成的三棵不同的带权二叉树

这三棵二叉树的带权路径长度WPL分别为：

(a) WPL=9×2+4×2+5×2+2×2=40
(b) WPL=4×1+2×2+5×3+9×3=50
(c) WPL=9×1+5×2+4×3+2×3=37

其中图c树的WPL最小，此树就是哈夫曼树。

从上面可以看出，根据n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优二叉树。权值越大的结点离树根越近（即路径长度越短）的二叉树才是最优二叉树。