南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）图论——第27章 树的应用

树的应用 离散数学一树 南京大学计算机科学与技术系

树的应用 离散数学─树 南京大学计算机科学与技术系

内容提要 ·表达式的（逆）波兰记法 。二叉搜索树 。决策树 ·前缀码 ·Huffman?编码（算法)

内容提要  表达式的（逆）波兰记法  二叉搜索树  决策树  前缀码  Huffman编码（算法） 2

表达式的根树表示 。用根树表示表达式：内点对应于运算符，树叶对应于 运算分量。 ·举例：(x+y)个2+(x-4)/3)

表达式的根树表示  用根树表示表达式：内点对应于运算符，树叶对应于 运算分量。  举例：((x+y)2+ ((x-4)/3) x y + 2 x +  y x 4  x 4  3 / 2 x +  y x 4  3 / + 3

表达式的（逆）波兰表示法 ●(x+y)↑2+(x-4)/3) ·前缀形式（波兰表示法） 0+个+x灯y2/-x43 ·后缀形式（逆波兰表示法） 。+2个x4-3/+ 。中缀形式 0x+y个2+x-4/3

表达式的（逆）波兰表示法  (x+y)2+ ((x-4)/3)  前缀形式（波兰表示法）  ++xy2 /-x4 3  后缀形式（逆波兰表示法）  xy+2 x4- 3/+  中缀形式  x+y2+ x-4/3 2 x +  y x 4  3 / + 4

中缀表示法的缺陷 ●中缀形式：+yx+3 。有3种解释： ●(x+y)/x+3) ●+yx+3 ●x+y/c+3) 不同的根树有相同的中 缀形式。 前缀与后缀则有一定的唯一性。(p.565:26-27)

中缀表示法的缺陷  中缀形式：x+y/x+3  有3种解释:  (x+y)/(x+3)  x+y/x+3  x+y/(x+3) x + y / x 3 + 3 x + y x / + x 3 + / y x + 不同的根树有相同的中 缀形式。 前缀与后缀则有一定的唯一性。(p. 565: 26-27) 5

前缀表示法（波兰表示法） 。x+y)/x+3) ●/+y+X3 ●x+y/+3 ●++x/yx3 ●x+y/(x+3) ●+xy+x3 从右向左，遇到运算符，对右边 紧接着的2个运算对象进行运算

前缀表示法（波兰表示法）  (x+y)/(x+3)  /+xy+x3  x+y/x+3  ++x/yx3  x+y/(x+3)  +x/y+x3 x + y / x 3 + 3 x + y x / + x 3 + / y x + 从右向左，遇到运算符，对右边 紧接着的2个运算对象进行运算 6

后缀表示法（逆波兰表示法） ·(x+y)/x+3) ●y+x3+/ ●x+y/x+3 ●yx/+3+ ●x+y/x+3) ●gyx3+/+ 从左向右，遇到运算符，对左边 紧接着的2个运算对象进行运算

后缀表示法（逆波兰表示法）  (x+y)/(x+3)  xy+x3+/  x+y/x+3  xyx/+3+  x+y/(x+3)  xyx3+/+ x + y / x 3 + 3 x + y x / + x 3 + / y x + 从左向右，遇到运算符，对左边 紧接着的2个运算对象进行运算 7

后缀表示法（逆波兰表示法） ·(a*(b+c)+d*(e*f)/(g+(h-i)*j) ●逆波兰表示： abc+*def**+ghi-j*+/ 从左往右，遇到运算符，根据运算 符所需运算分量个数确定前面的 元素作为运算分量。 不需要括弧唯一地表示计算顺序

后缀表示法（逆波兰表示法）  (a*(b+c)+d*(e*f))/(g+(h-i)*j)  逆波兰表示：  abc+*def**+ghi-j*+/ 从左往右，遇到运算符，根据运算 符所需运算分量个数确定前面的 元素作为运算分量。 不需要括弧唯一地表示计算顺序。 j i a g b c d e f h / + + * * * + * - 8

后缀表达式求值 723-4个931+ 76s4↑931+ 14个931+ 193/+ 13+ 4 9

后缀表达式求值 7 2 3 * - 4  9 3 / + 7 6 - 4  9 3 / + 1 4  9 3 / + 4 1 9 3 / + 1 3 + 9

复合命题的根树表示 命题：((PAq)→（一pVq) 后缀形式：pqA一p一qVK→ 10

复合命题的根树表示 后缀形式：pqpq p  q     p q  命题：((pq))  (pq) 10