离散数学耿素云PPT版.ppt

* 例(续) 编码: 0---01 1---11 2---001 3---100 4---101 5---0001 6---00000 7---00001 传100个按比例出现的八进制数字所需二进制数字的个数 为 W(T)=285. 传10n(n?2)个所用二进制数字的个数为2.85?10n, 而用等长 码(长为3)需要用 3?10n个数字. * 行遍2叉有序树 行遍(周游)根树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叉有序树表示算式 每一个分支点放一个运算符. 二元运算符所在的分 支点有2个儿子, 运算对象是以这2个儿子为根的根 子树表示的子表达式, 并规定被减数和被除数放在 左子树上; 一元运算符所在的分支点只有一个儿 子, 运算对象是以这个儿子为根的根子树表示的子 表达式.数字和变量放在树叶上. 实例 例1 表示((b+(c+d))?a)?((e?f)?(g+h)?(i?j))的2叉有序树 中序行遍: ((b+(c+d))?a)?((e?f)?(g+h)?(i?j)) 前序行遍: ?(?(?b(?cd))a)(?(?ef)(?(?gh)(?ij))) 后序行遍: ((b(cd?)?)a?)((ef?)((gh?)(ij?)?)?)? 注:中序行遍的结果是原式 * * 波兰符号法 波兰符号法(前缀符号法): 按前序行遍法访问表示算式的2叉有序树, 并舍去所有括号. 例1(续) ???b+cda??ef?+gh?ij 计算方法: 从左到右, 每个运算符号对它后面紧邻的2个(或1个)数进行运算. 例1(续) 设a=3, b=1, c=d=2, e=f=3, g=i=1, h=j=2. ???1+223??33?+12?12, ???143??33?+12?12 ??53??33?+12?12, ?(15)??33?+12?12 ?(15)?9?+12?12, ?(15)?9?3?12 ?(15)?9?32, ?(15)?96, ?(15)3, 5 * 逆波兰符号法 逆波兰符号法(后缀符号法): 按后序行遍法访问表示算式的2叉有序树, 并舍去所有括号. 例1(续) bcd++a?ef?gh+ij??? ? 计算方法: 从右到左, 每个运算符号对它前面紧邻的2个(或1个)数进行运算. 例1(续) 122++3?33?12+12??? ? 122++3?33?12+2?? ? , 122++3?33?32?? ? 122++3?33?6? ?, 122++3?96? ? 122++3?3 ?, 14+3?3 ?, 53?3 ?, (15)3 ?, 5 实例 例2 用2叉有序树表示下述命题公式, 并写出它的波兰符号法和逆波兰符号法表达式. (p??q)?((?p?r)?(q?r)) 解 波兰符号法表达式 ??p?q???pr?qr 逆波兰符号法表达式 pq??p?r?qr??? 注: 当一元运算符在运算对象前面时, 应画成右儿子. * ? ? ? ? ? ? ? p p q q r r * 第7章 树 7.1 无向树及生成树 7.2 根树及其应用 * 7.1 无向树及生成树 无向树与森林 生成树与余树 基本回路与基本回路系统 基本割集与基本割集系统 最小生成树与避圈法 * 无向树 无向树: 无回路的连通无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 右图为一棵12阶树. 注:本章中所讨论的回路均 指简单回路或初级回路 树的应用 英国数学家凯莱(Arthur Cayley)于19世纪中叶研究 饱和碳氢化合物CnH2n+2的同分异构体时提出树的概 念. 当n=1,2,3时, 都只有一棵非同构的树; 当n=4时, 有2棵不同构的树. * 甲烷 乙烷 丙烷 丁烷 异丁烷 * 无向树的性质 定理 设G=V