哈夫曼树（HuffmanTree）
目录
哈夫曼树（HuffmanTree）
事例
基本概念
路径
结点的路径长度
例1：计算路径长度
例2：计算路径长度
树的路径长度
例：计算树的路径长度
权（weight）
结点的带权路径长度
例：计算结点的带权路径长度
树的带权路径长度（Weighted Path Length，WPL）
例：求WPL
哈夫曼树定义
例：哈夫曼树
哈夫曼算法（构造哈夫曼树的方法）
例：构造哈夫曼树
例：构造哈夫曼树
哈夫曼树的结点特点
哈夫曼编码
例：哈夫曼编码传输文字内容了解
前缀编码
哈夫曼编码性质
进行哈夫曼编码
哈夫曼树（HuffmanTree）
事例
基本概念
路径
- 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
结点的路径长度
- 两结点间路径上的分支数
例1：计算路径长度
- A 到 B 的路径长度：1
- A 到 D 的路径长度：2
- A 到 G 的路径长度：3
- A 到 I 的路径长度：4
- ……
例2：计算路径长度
- A 到 B 的路径长度：1
- A 到 D 的路径长度：2
- A 到 G 的路径长度：2
- A 到 I 的路径长度：3
- ……
树的路径长度
- 从树根到每一个结点的路径长度之和。记作：TL
- 根结点到自身的路径长度是0
- 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树
- 但路径长度最短的树不一定是完全二叉树
例：计算树的路径长度
权（weight）
将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权（weight）
结点的带权路径长度
从根结点到该结点之间的路径长度，与该结点的权的乘积
例：计算结点的带权路径长度
- F 的带权路径长度为 2 × 7 = 14
- H 的带权路径长度为 2 × 3 = 6
树的带权路径长度（Weighted Path Length，WPL）
- 树中所有叶子结点的带权路径长度之和
例：求WPL
哈夫曼树定义
- 哈夫曼树：带权路径长度（WPL）最短的二叉树（最优二叉树）
- “带权路径长度最短”是在“度相同” 的树中比较而得的结果，因此有最优二叉树、最优三叉树等等
- 满二叉树不一定是哈夫曼树
- 哈夫曼树中权越大的叶子离根越近
- 具有相同带权结点的哈夫曼树不唯一
例：哈夫曼树
哈夫曼算法（构造哈夫曼树的方法）
口诀
- 构造森林全是根
- 选用两小造新树
- 删除两小添新人
- 选用2、3剩单根
例：构造哈夫曼树
Q：有 4 个结点 a, b, c, d，权值分别为7，5，2，4，构造哈夫曼树
- 构造森林全是根
- 选用两小造新树
- 删除两小添新人
- 重复2、3剩单根
例：构造哈夫曼树
Q：有 5 个结点 a, b, c, d, e，权值分别为 7，5，5，2，4，构造哈夫曼树
- 构造森林全是根
- 选用两小造新树
- 删除两小添新人
- 重复2、3剩单根
- 重复2，挑选两小造新树
- 重复3，删除两小添新人
- 重复2，挑选两小造新树
- 重复3，删除两小添新人
- 最后
哈夫曼树的结点特点
- 哈夫曼树的结点的度数为 0 或 2，没有度为 1 的结点
- 因为包含 n 棵树的森林要经过 n-1 次合并才能形成哈夫曼树
- 共产生 n-1 个新结点，且这 n-1 个新结点都是具有两个孩子的分支结点
- 共有 2n-1（n+n-1） 个结点
哈夫曼编码
- 在远程通讯中，要将待传字符转换成由二进制的字符串
- 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）
- 利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短
- 在哈夫曼树的每个分支上标0或1
- 结点的左分支标0，右分支标1
- 把从根到每个叶子的路径上的标号连起来，作为该叶子代表的字符的编码
例：哈夫曼编码传输文字内容了解
- 如，要将内容为“BADCADFEED”要网络传输给别人，显然要用二进制的数字来表示
- 对方接收时，为001000011010000011101100100011，可以按照 3 位一分来译码 ，如果一篇文章很长，这样的二进制也将非常可怕
- 假设六个字母的频率为A 27，B 8，C 15，D15，E 30，F 5，合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们
- 左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树
- 我们对这六个字母用其从树根到叶子所经过路径的0或1来编码
- 我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了
- 原编码二进制串：001000011010000011101100100011（共30个字符）
- 新编码二进制串：1001010010101001000111100（共25个字符）
- 也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本
前缀编码
- 编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码
- 在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则
哈夫曼编码性质
哈夫曼编码是前缀码
哈夫曼编码是最优前缀码
进行哈夫曼编码
需要
- 编码的字符集
- 各个字符在电文中出现的次数或频率的集合
