哈夫曼树+总结+习题(2学时).ppt

6 6Huffman树基本概念 构造 编码 1 基本概念路径 从一个结点到另一个结点之间的分支 路径长度 路径上分支数目 结点的路径长度 从根结点到该结点的路径长度 树的路径长度 树中每个结点的路径长度之和 完全二叉树这种长度最短的二叉树 结点的带权路径长度 该结点的路径长度 结点的权值树的带权路径长度 树中所有叶子结点的带权路径长度之和 记作 WPL wklk例如最优二叉树 在所有含n个叶子结点 并带相同权值的二叉树中 必存在WPL最小的二叉树 又叫Huffman树 W 7 2 4 5 9 A E D B C B C D A E 7 2 4 9 5 7 2 4 5 9 WPL1 wklk 7 2 5 2 2 3 4 3 9 2 60 WPL2 wklk 7 4 9 4 5 3 4 2 2 1 89 在解决某些判定问题时 利用Huffman树可得到最佳判定算法例如 某厂生产螺钉 要求直径为d 误差 现测量某螺钉直径 方法与标准的比较 判定树 d d d d 5 10 50 25 10 WPL 5 3 10 3 50 2 25 2 10 2 概率最大的最靠近根判断 2 Huffman树的构造 自底向上 A 7 D 5 E 9 F2 F3 W 7 2 4 5 9 接上页 F4 F5 根的权值为27WPL 7 2 2 3 4 3 5 2 9 2 60 Huffman树形态不唯一 构造过程 Huffman算法 1 n个权值构成n棵独立二叉树的森林F T1 Tn 2 在森林中选出两棵根权值最小的二叉树作为左右子树 构造二叉树 根权值为左右子树的和 3 在F中删除这两棵 新构成的添加到F中 4 重复 2 和 3 直到F中含一棵二叉树为止 两个结论 1 在Huffman树中没有度为1的结点 2 一棵有n个叶子结点的Huffman树共有2n 1个结点 证明 设总结点数为m个 叶子n个 度为1的n1个 度为2的n2个m n n1 n2由性质3n n2 1所以n2 n 1m n n1 n2 n n1 n 1 2n n1 1有 1 得n1 0所以m 2n 0 1 2n 1 3 Huffman编码 1 等长编码 2 不等长编码 出现多的字符采用短码 总长短了 但出现二义性 3 前缀编码 一个字符的编码都不是另一个字符的编码的前缀 ABCD00011011 两位一分进行译码 ABCD000111 用二叉树实现 左分支0 右分支1 A 00B 01C 1 4 Huffman编码 设计Huffman树而得到的编码 例如 有8种字符 概率如下 0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 解 同时扩大100倍 得权值集合 5 29 7 8 14 23 3 11 设计Huffman编码 WPL 0 23 2 0 11 3 Huffman编码0 05 01100 29 100 07 11100 08 11110 14 1100 23 000 03 01110 11 010 作业 本章小结1 掌握树的定义 表示形式和术语 二叉树通用 掌握树的存储结构 孩子 兄弟表示 掌握树与二叉树的转换了解树的ADT定义与树和森林遍历2 掌握二叉树的ADT定义 特点 结点