※ 引述《joeyeh (joe)》之铭言： : inorder: (3*(5-1/3*3)/(23 x^y 3)+2.5 e^x) x^0.5 : preorder: x^0.5 +/*3-5/1*3 3 x^y 23 3 e^x2.5 : 开方根运算符号我用x^0.5来代表,键盘上找半天找不到 : 学长真狠.....怎麽造... 以下用 ^ 表示 x^y √ 表示 开根号 exp 表示 自然指数 前序为: √ + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5 前提: √ 和 exp 是单元函数 其他是二元函数 首先先括号 (为什麽能先括号等会讲) √ + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5 √ + / * 3 - 5 / 1 (* 3 3) ^ 23 3 exp 2.5 √ + / * 3 - 5 (/ 1 (* 3 3)) ^ 23 3 exp 2.5 √ + / * 3 (- 5 (/ 1 (* 3 3))) ^ 23 3 exp 2.5 √ + / (* 3 (- 5 (/ 1 (* 3 3)))) ^ 23 3 exp 2.5 √ + / (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3) exp 2.5 √ + (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) exp 2.5 √ + (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) (exp 2.5) √ (+ (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) (exp 2.5)) 所以对应的中序是 √(((3*(5-(1/(3*3))))/(23^3))+(exp 2.5)) 如果像上面的表示法 单元函数把函数放後面的话 (此处用 sqrt 表根号...因为颇不直觉) 就是 (((3*(5-(1/(3*3))))/(23^3))+(2.5 exp)) sqrt --- 我觉得你问错问题了.... 运算式只需要其中之一就可以推得其他两个 因为运算式里面只有 operand 才是叶节点 同样的只有 operator 才是非叶节点 所以可以轻易从这里推得其他两个 (这也是刚刚括号的依据) 一般的树的表示法则不一定谁才是叶 所以才需要两个 --- 那麽就来看看一般的树的版本 (沿用 sqrt 为根号) 前序 sqrt + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5 中序 3 * 5 - 1 / 3 * 3 / 23 ^ 3 + 2.5 exp sqrt 一个重点: 前序第一个东西必然是根 所以 sqrt 是根 对照中序可知它只有左边有东西 sqrt ┌───────┘ 前序 + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5 中序 3 * 5 - 1 / 3 * 3 / 23 ^ 3 + 2.5 exp + 是根。 sqrt ┌───────┘ + ┌────┴────┐ 前 / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5 中 3 * 5 - 1 / 3 * 3 / 23 ^ 3 2.5 exp 右边比较简单: exp 是根 2.5 在左边 sqrt ┌───────┘ + ┌────┴────┐ 前 / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 中 3 * 5 - 1 / 3 * 3 / 23 ^ 3 ┌┘ 2.5 左边: / 是根....但不知道哪一个才是根? 简单: 前序和中序的元素个数是一样的 所以如果中序的第一个 / 是根 那同样取前面 5+1 个元素会得到不合理的东西 因此中序的第二个 / 是根 sqrt ┌───────┘ + ┌────┴────┐ / exp ┌───┴────┐ ┌┘ 前 * 3 - 5 / 1 * 3 3 ^ 23 3 2.5 中 3 * 5 - 1 / 3 * 3 23 ^ 3 同样右边简单: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌───┴────┐ ┌┘ 前 * 3 - 5 / 1 * 3 3 ^ 2.5 中 3 * 5 - 1 / 3 * 3 ┌┴┐ 23 3 左边: 看似中序的第一个 * 是根...第二个如何? 似乎也很合理... 先试第二个好了: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌──┴────┐ ┌┘ * ^ 2.5 ┌─┴────┐ ┌┴┐ 前 3 - 5 / 1 * 3 3 23 3 中 3 * 5 - 1 / 3 同样 两个 3 谁才是根呢? 第一个试试看: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌──┴────┐ ┌┘ * ^ 2.5 ┌─┴────┐ ┌┴┐ 3 3 23 3 └──┐ 前 - 5 / 1 * 3 中 * 5 - 1 / 3 - 是根...怪了 怎麽式子不合理? (左子树前 5 / 中 * 5 ) 所以这里不对 那换试第二个 3 是根呢: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌─┴────┐ ┌┘ * ^ 2.5 ┌─┴───┐ ┌┴┐ 3 3 23 3 ┌┘ 前 - 5 / 1 * 3 中 3 * 5 - 1 / 依然 - 是根...又不合理了 (左子树前 5 / 1 中 3 * 5) 所以这表示那个 * 并不是第二个 * 才是根 第一个 * 才是 卷回去吧: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌───┴────┐ ┌┘ * ^ 2.5 ┌──┴──┐ ┌┴┐ 3 前 - 5 / 1 * 3 3 23 3 中 5 - 1 / 3 * 3 这次 - 还是根 不过子树的字串就合理了: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌───┴────┐ ┌┘ * ^ 2.5 ┌──┴──┐ ┌┴┐ 3 - 23 3 ┌────┴─┐ 5 前 / 1 * 3 3 中 1 / 3 * 3 下面不用我说你也可以做得出来: sqrt ┌───────┘ + ┌────┴────┐ / exp ┌───┴────┐ ┌┘ * ^ 2.5 ┌──┴──┐ ┌┴┐ 3 - 23 3 ┌──┴─┐ 5 / ┌─┴─┐ 1 * ┌┴┐ 3 3 正好这个例子能解出唯一树来... 我猜你学长想说的是 当节点的名字重覆时也许会出现不一样的树 最简单的例子是: X X ┌┘ └┐ 这两个树前序和中序和後序都是 XX 谁知道你哪个是哪个... X X 因此用前中/中後建出原来的树有个条件是节点的名字需要各不同 而运算式方面则因为已经有刚刚说的那个条件在了 所以除了可以唯一决定外 更只需要其一即可 --- 给 end 了的其他 puzzle 版众: http://0rz.tw/8w8sn 这篇文章在说的是这个东西 --- 资料结构啊...那已经是好几年前学的东西了...(远目) -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.92