第10章 拓展补充：哈夫曼树证明《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

哈夫曼编码 哈夫曼编码就是他在1952年做博士论文时发明的。可以依据字母的使用频率而设计的变长码，提高信息的传输效率,至今仍被广泛的应用 本次教学目标： 1、最优二叉树（哈夫曼树） 2、哈夫曼树的构建过程 3、哈夫曼树是最优树的证明 为提高通信效率，采用不等长编码，会出现错误 误译的原因是因为短的编码是其它编码的前缀 而利用二叉树任意一个叶子结点的归根路径都不可能是其它叶子结点归根路径的子集这一特性，可以利用二叉树这一特点保证通信编码不会出现错译问题 最优二叉树 何为最优二叉树？ 先看下面的一个例子 例如: 有4个结点：a、b、c、d，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,则叶子权值与归根路径长度乘积之和是不一样的： a b c d 7 5 2 4 d c a b 2 4 7 5 a b c d 7 5 2 4 36 46 35 最优二叉树定义： 在一棵二叉树中，某叶子结点权值与归根路径长度乘积称之和称为该叶子的带权路径长度，而二叉树的所有叶结点的带权路径长度之和，记为WPL（Weighted Path Length of Tree），若在所有具有m个叶子结点的二叉树中，某二叉树的WPL最小，称这样的二叉树为最优二叉树。 最优二叉树与通信编码的关系 设想基于二叉树带权叶子的归根路径构建编码： 1、通信编码的基码就是0，1两个符号，而二叉树归根路径，每一段只有两个方向，偏左或偏右，可行！ ２、二叉树的任何一个叶子的归根路径都不是其他叶子归根路径的子集，利用二叉树的路径编码，则保证了不会出现误译情况，可行！ ４、所以，设计思路应该是：权值越小，路径越长，权值越大，路径越短。其衡量标准就是WPL，而最优二叉树的WPL最小，则，保证了其对应的编码效率最高！ ３、从通信效率的角度，当然希望所有编码都很短，但一定深度的二叉树的叶子是有限制的 但如何构造最优树？ 显然，不能使用蛮力构造法，有无穷个！ 哈夫曼编码基于二叉树理论，是上个世纪五十年代由哈夫曼在读博期间提出的 由此构建的二叉树也称之为哈夫曼树 哈夫曼树 哈夫曼树构建过程 假设有n个权值分别为 w1,w2,…,wn,则构建n个叶子的哈夫曼树的规则为： (1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。 显然：哈夫曼树的n1=0 假设有A—H八个通信基码，基于历史数据统计，其被使用频率分别如下： A B C D E F G H 0.18 0.03 0.04 0.07 0.26 0.1 0.11 0.21 B C 0.07 0.07 0.14 0.32 0.21 0.58 D 0.14 A 0.32 0.58 E 1 F G H 0.21 0.42 0.42 A 0.18 0 0 0 B 0.03 0 0 1 0 0 C 0.04 0 0 1 0 1 D 0.07 0 0 1 1 E 0.26 0 1 F 0.1 1 0 0 G 0.11 1 0 1 H 0.21 1 1 WPL = 2×(0.26 + 0.21) + 3×(0.18 + 0.1 + 0.11) + 4×0.07 + 5×(0.03 + 0.04) = 2.74 下面采用归纳法及反证法证明哈夫曼树是最优树 符号定义： 1、树T的WPL值记为 W(T) 2、结点A的权值记为W(A) 引理1：一棵哈夫曼树的叶子结点数减一，则必定是去除某父结点的左右两个孩子叶子结点，而使其父结点成为新的叶子。且新构二叉树依然为哈夫曼树。 证明：哈夫曼树：n1=0，因此，如果直接删除一个叶子，会出现n1>0的情况；由于删除两个孩子后使其父结点成为叶子，从哈夫曼构建过程可知，其父结点所在树中的位置是依据其权值而不是是否是一个子树或结点。得证！ 引理2：对于一个叶子带权值的二叉树，如将某一个叶子分裂成两个叶子a,b，且两个叶子权值之和等于原结点，形成新的树T’，则总有 w(T’)=W(T)+W(a)+W(b)。 反之，将一个叶子带权值的二叉树T’的两兄弟叶子删去，使它的父结点成为新的叶子，且其权值等于二个孩子权值之和，则新的二叉树T有： W(T)= W(T’)-W(a)-W(b) 引理3：假设有n个结点构建出一个最优二叉树T，则n个结点中权值最小的两个结点必定是在最后一层（归根路径长度最大），且可以调整其成为同父结点的兄弟关系。（哈夫曼树从其构建过程