树的应用 离散数学一树 南京大学计算机科学与技术系
树的应用 离散数学─树 南京大学计算机科学与技术系
内容提要 ·表达式的（逆）波兰记法 。二叉搜索树 。决策树 ·前缀码 ·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+y2+ 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
复合命题的根树表示 后缀形式：pqpq p q p q 命题：((pq)) (pq) 10