什么是霍夫曼树

在了解霍夫曼树之前，首先来学习几个术语：

1、路径： 6.1.1节已经学习过路径这个概念，它是指从某一结点到另一个结点的线路。

2、树的路径长度：树的路径长度是从树根到树中每一个结点的路径长度之和。如图1所示，其路径长度为1+1+2+2+2+2+3+3=16。

图1 二叉树

结点数目相同的所有二叉树中，完全二叉树的路径长度最短。

3、树的带权路径长度（Weighted Path Length of Tree，简记为WPL）：

结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。例如用树结点存储一些字符时，可以用字符的ASCII码值作为结点权值；用树结点存储学生成绩划分时，那么学习成绩就可以是权值。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权值的乘积。

树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和，通常记为：

其中，n表示叶子结点数目；wi和li分别表示结点ki的数值和根到结点ki之间的路径长度。树的代权路径长度亦称为树的代价。

在由权为w1，w2，…，wn的n个叶子结点所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树。因为它是数学家霍夫曼（Huffuman）所提出，所以也叫作霍夫曼树。

假设一棵有4个叶子结点a,b,c,d的二叉树，带的权分别为7，5，2，4，我们构造出三棵结构不同但都有4个叶子结点的二叉树，如图2所示。

图2 有4个结点的三种二叉树形式

它们的带权路径长度分别为：

①WPL=7×2+2×2+5×2+4×2 = 36；

②WPL=7×1+5×2+2×3+4×3 = 35；

③WPL=7×2+2×3+5×3+4×1 = 39。

其中②中的二叉树是霍夫曼树，它的WPL最小。读者也可以再构建有4个结点的其他二叉树来计算树的带权路径长度，但它们都会比②中二叉树的值大。

当叶子结点的权值均相同时，权越大的叶子离根越近，权越小的叶子离根越远，树的代价就越小。注意：霍夫曼树的形态并不唯一。