哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树， 这种树在信息检索中很有用。

带权路径长度:从根结点到某结点的路径长度与该结点上权的乘积。

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

对图（a）: WPL =9×2+5×2+2×2+3×2=38

对图（b）: WPL =3×2+9×3+5×3+2×1=50

对图（c）: WPL =9×1+5×2+2×3+3×3=34

路径长度最短的二叉树，其带权路径长度不一定最短;结点权值越大离根越近的二叉树是带权路径最短的二叉树。可以验证 （c）为哈夫曼树。

构造哈夫曼树——哈夫曼算法

哈夫曼算法介绍如下:

    （1） 根据给定的 n个权值｛W1 ，W2 ，…，Wn ｝构成n棵二叉树的集合F=｛T1 ，T 2 ，…，Tn ｝，其中每棵二叉树中只有一个带权为Wi 的根结点。

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

    （3） 将新二叉树T加入二叉树集合 F中，从二叉树集合F中 去除原来两棵根结点权    值最小的树。

    （4） 重复（2）和（3）步直到 F 中只含有一棵树为止，这棵树就是哈夫曼树。

哈夫曼编码：左0右1

从根结点出发，按代码串中“0”为左子树，“1”为右子树的规则，直到叶子结点。路径扫描到的二进制位串就是叶子结点对应的字符的编码。例如对上述二进制代码串译码:0为左子树的叶子结点A，故0是A的编码;接着1为右子树，0为左子树到叶子结点C，所以10是C的编码;接着1是右子树，1继续右子树，1再右子树到叶子结点D，所以111是D的编码……如此继续，即可正确译码。

练习题：

给定一组权值（5，9，11，2，7，16）对应字符是abcdef，试设计相应的哈夫曼树，并求出对应的WPL及各数字的哈夫曼编码。

以数据集{3，4，5，8，12，18，20，30}为叶结点，构造一棵哈夫曼树并求其带权路径长度。 

由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

A.24  B. 48  C.72  D.53

有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度，及对应点的哈夫曼编码