6.11哈夫曼树及其应用

将大文档进行压缩可以将其空间减少，简单来说，就是把我们要压缩的文本进行了重新的编码，以减少不必要的空间

赫夫曼编码 —— 一种最基本的压缩编码方法

6.11.1哈夫曼树的基本概念

路径长度

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。

下图中的二叉树a中,根结点到结点D的路径长度就为4

二叉树中根结点到结点D的路径长度为2

树的路径长度就是从树根到每一结点的路径长度之和

二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20

二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16

完全二叉树是路径长度最短的二叉树

权

权(weight):也叫权重，从英文意思即可知道，将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度

从根节点到该节点的路径长度与该节点的权的乘积

树的带权路径长度

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

哈夫曼树:最优树

带权路径长度(WPL)最短的树 "带权路径长度最短”是在"度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

哈夫曼树:最优二叉树

带权路径长度(WPL)最短的二叉树 因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法。

满二叉树不一定是哈夫曼树

具有相同带权结点的哈夫曼树并不唯一

6.11.2哈夫曼树的构造

1.先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即: A5,E10，B15，D30， C40。

2.取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，新结点的权值为两个叶子权值的和5+10=15。

3.将N1当做A与E,插入有序序列中，保持从小到大排列。即: N15, B15

4.重复步骤2。将N1与B作为一个新节点N2的两个子结点N2的权值=15+15=30

5.将N2当做N1与B,插入有序序列中，保持从小到大排列。即: N230，D30，C40

6.重复步骤2。将N2与D作为一个新节点N3的两个子结点。N3的权值=30+30=60

7.将N3当做N2与D,插入有序序列中，保持从小到大排列。即: C40，N360

8.重复步骤2。将C与N3作为一个新节点T的两个子结点由于T即是根结点,完成赫夫曼树的构造。

二叉树的带权路径长度WPL=40x1+30x2+15x3+10x4+5x4=205。与上面的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

6.11.3哈夫曼编码

哈夫曼树的左分支代表0，右分支代表1，从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是哈夫曼编码

例题如下：

思路如下：

1、要传输的字符集D = {C，A，S，T，；}

字符出现的频率 w = {2,4,2,3,3}

2、把他们出现的频率作为权重，权重大的离根节点近，小的相反进行构造带权二叉树

3、用哈夫曼编码的思想左分支代表0，右分支代表1，每个子节点都是如此

4、最后从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码

\