哈夫曼树及其应用教学内容安排

一、最优二叉树（Huffman树）

哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。

1、基本术语

•路径和路径长度

•树的路径长度

•结点的权和带权路径长度

•树的带权路径长度

•Huffman树（最优二叉树）

路径：若在一棵树中存在着一个结点序列k1，k2 … kj，使得 ki 是k i+1(1£i<j) 的父亲，则该结点序列是k1 到kj的路径

路径长度：从k1 到kj所经过的分支数称为这两点间的路径长度 。

•树的路径长度：树中每个结点的路径长度之和。

•结点的权：树中的结点赋予的一定意义上的实数称之为该结点的权

•树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T) = SwkLk (对所有叶子结点)。

在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。

最优二叉树（也称Huffman树）：它是n个带权叶子结点构成的所有二叉树中带权路径长度 WPL最小的二叉树。

2、为何要构造哈夫曼树

3、如何构造哈夫曼树

哈夫曼算法：

（1）根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合 F = {T1, T2,… , Tn}，

其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；

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

（3）从F中删去这两棵树，同时加入刚生成的新树；

（4）重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。

例1: 已知权值 W={ 6，7，2，3，5，11，12 }，试构造一棵哈夫曼树，并求加权路径长度

二、哈夫曼编码

1、问题的提出

通讯中常需要将文字转换成二进制字符串电文进行传送。文字电文，称为编码。

反之，收到电文后要将电文转换成原来的文字，电文     文字，称为译码。

反之，收到电文后要将电文转换成原来的文字，电文     文字，称为译码。

设有n种字符，每种字符出现的次数为Wi ,其编码长度为Li ( i=1,2,…n)，则整个电文总长度为∑ Wi Li ，要得到最短的电文，即使得∑ Wi Li最小。也就是以字符出现的次数为权值，构造一棵 Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。

用构造Huffman树编出来的码，称为Huffman编码。

2. 哈夫曼编码的构造方法

（1）构造Huffman 树

（2）产生Huffman 编码