离散数学(第十六章)剖析.ppt

* * * * * * * * * * * * * * * * * 解答（续） 24 34 19 20 39 24 34 解答（续） 24 34 39 58 39 解答（续） 58 39 97 W(T)=6(2+3)+5*5 +4*7+3(11+13+17) +2(19+20) =264 * 最佳前缀码 定义16.10 设?1, ?2, …, ?n-1, ?n是长度为 n 的符号串 (1) 前缀——?1, ?1?2, …, ?1?2…?n?1 (2) 前缀码——{?1, ?2, …, ?m}中任何两个元素互不为前缀 (3) 二元前缀码——?i (i=1, 2, …, m) 中只出现两个符号，如0与1. 如何产生二元前缀码？ 定理16.6 一棵2叉树产生一个二元前缀码. 推论 一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1） * 图所示二叉树产生的前缀码为 { 00, 10, 11, 011, 0100, 0101 } * 用Huffman算法产生最佳前缀码 例6 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n?2）个按上述比 例出现的八进制数字需要多少个二进制数字？若用等长的 （长为3）的码字传输需要多少个二进制数字？ * 解 用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此权产生的最优树如图所示. 求最佳前缀码 01-----0 11-----1 001-----2 100-----3 101-----4 0001-----5 00000-----6 00001-----7 W(T)=285， 传10n(n?2)个 用二进制数字需 2.85?10n个， 用等长码需 3?10n个数字. * 波兰符号法与逆波兰符号法 行遍或周游根树T——对T的每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式： ① 中序行遍法——次序为：左子树、根、右子树 ② 前序行遍法——次序为：根、左子树、右子树 ③ 后序行遍法——次序为：左子树、右子树、根 对图所示根树按中序、前序、 后序行遍法访问结果分别为： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a * 用2叉有序正则树存放算式 存放规则 最高层次运算放在树根 后依次将运算符放在根子树的根上 数放在树叶上 规定：被除数、被减数放在左子树树叶上 算式 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j)) 存放在图所示2叉树上. * 波兰符号法 波兰符号法 按前序行遍法访问存放算式的2叉有序正则树，其结果不加 括号，规定每个运算符号与其后面紧邻两个数进行运算，运 算结果正确. 称此算法为波兰符号法或前缀符号法. 对上图的 访问结果为 ? ? ? b + c d a ? ? e f ? + g h ? i j 逆波兰符号法 按后序行遍法访问，规定每个运算符与前面紧邻两数运算， 称为逆波兰符号法或后缀符号法. 对上图的访问结果为 b c d + + a ? e f ? g h + i j ? ? ? ? * 第十六章 习题课 主要内容 无向树及其性质 生成树、最小生成树、基本回路系统、基本割集系统 根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法 基本要求 深刻理解无向树的定义及性质 熟练地求解无向树 准确地求出给定带权连通图的最小生成树 深刻理解基本回路、基本割集的概念，并会计算 理解根树及其分类等概念 会画n阶（n较小）非同构的无向树及根树（1?n?6） 熟练掌握求最优树及最佳前缀码的方法 掌握波兰符号法与逆波兰符号法 * （2） （3） 从而解出 练习1 1. 无向树 T 有ni个i 度顶点，i=2, 3, …,k，其余顶点全是树叶，求T 的树叶数. 解 用树的性质：边数 m=n?1（n为阶数），及握手定理. (1) * 2．设n阶非平凡的无向树T中，?(T) ? k，k ? 1. 证明T至少 有k片树