哈夫曼树总结习题(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定义 特点 结点的形态 性质 存储结构 二叉链表 掌握二叉树的遍历 线索的方法掌握遍历算法的应用掌握二叉树与树和森林的转换掌握Huffman树概念 构造和编码