哈夫曼树的详细讲解（手把手教学）

学习目标：

• 了解哈夫曼树是什么，理解路径和路径长度的概念
• 学会哈夫曼树的权值计算（WPL）
• 学会哈夫曼树的构造
• 理解哈夫曼树编码算法思想

学习内容：

> 1. 最优二叉树（哈夫曼树）的介绍

哈夫曼树又称为最优树，是一类带权路径长度最短的树，应用光泛。 在学习哈夫曼树的时候，我们来先引入路径和路径长度的概念。 ***1.1路径：***从树中的一个结点到另一个结点的之间的分支构成的。 ***1.2路径长度：***路径上的分支数目。 ***1.3树的路径长度：***从树根到每一个结点的路径长度之和 结点的带权路径长度：从该结点到树根之间的路径长度与结点上的权值的乘积 ***1.4树的带权路径长度：***树中所有叶子结点的·带权路径长度之和，也就是WPL，WPL=每一个结点的对应的权值乘以对应的路径长度之和。 注意： 1.满二叉树不一定是哈夫曼树 2.哈夫曼树中权值越大的叶子结点离根越近 3.具有相同带权结点的哈夫曼树不惟一 4.在结点相同的二叉树中，完全二叉树是路径长度最短的二叉树。

> 2. WPL权值计算的方法

先举几个例子： 比如下面3棵二叉树都有4个叶子结点a，b，c，d。其权值分别是7,5，2,4。 第一种：

这个a，b，c，d，都在同一行，所以他们的路径长度都相同，也就是·2. 即WPL=（7+5+2+4）*2

第二种：

此图标出来了个路径长度 WPL=2 * 1（c的）+2 * 4（d的）+3 * 7（a的）+3 * 5（b的）

第三种：

WPL=7 * 1（a的）+5 * 2（b的）+4* 3（d的）+3 * 2（c的）

经过比较我们可以得出，第三种的WPL最小。那么下面让我们探讨一下如何来创建一棵这样的二叉树呢？。

3. 构造哈夫曼树的方法

这种方法也就是俗称哈夫曼算法。其过程如下： 3.1 构造森林全是根 根据n个给定的权值{w1,w2,w3…wn}构成n棵二叉树的森林F={T1,T2,T3…Tn}，其中每棵二叉树Ti只有一个权值为wi的根结点，其左右子树为空。

3.2选用两小造新树 在F中选两棵根结点权值最小的树作为左右子树，构造成一棵新的二叉树，并把新的二叉树的根结点的权值设置成两个左右结点的权值之和。

3.3删除两小填新人 即在F中把刚才构成二叉树的两个树（结点）删除掉，再把新得到的二叉树加入到森林（F）中。

3.4重复（3.2）和（3.3） 直到森林中只含有一棵树为止。这棵树便是哈夫曼树。

举例 比如如下的树

首先来先选择两棵权值最小的根结点。即d和e

然后把新树的根结点加入到森林当中，并删除原来的两个结点

重复上述两个步骤，下面就是分步的理解图 选两小，组新树

新树根结点加入到森林中，删除原来两结点

当有好几个权值相同时，任意选取两个就行 继续…

继续…

继续…

到此就结束了，当前就是一棵哈夫曼树。 注意：在这个过程当中我们可以把每一层的结点都按大小顺序，从小到大，或者从大道小，来排列。会使图更加美观。

4. 哈夫曼编码

哈夫曼编码可以说是哈夫曼树的应用了。 在传送电文信息时，我们常常用编码来加密电文信息。 比如1100011，可能代表“有危险”，或者代表任何我们想让它代表的文字。 在编码时，我们要去避免出现歧义，比如·a的编码是0 b的编码是00 那么000 代表什么呢？这就会出现歧义，但是哈夫曼树可以避免。因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点的前缀。 介绍一下前缀编码： 要设计长度不等的编码，必须使任一字符的编码都不是另外一个字符编码的前缀。 所以设计电文总长度最短的二进制前缀编码问题就是以n种字符出现的频率为权值设计一棵哈夫曼树的问题。 哈夫曼编码方法: 1、统计字符集中每个字符在电文中出现的平均概率(概率越大，要求编码越短)。 2、利用哈夫曼树的特点:权越大的叶子离根越近; 将每个字符的概率值作为权值，构造哈夫曼树。 则概率越大的结点，路径越短。 3、在哈夫曼树的每个分支上标上0或1结点的（左分支标0，右分支标1） 把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。 也就是如下图所示：

a的编码是：00 c的编码是：01 f的编码是：11 b的编码是：100 d的编码是：1010 e的编码是：1011