唯一樹造的出來嗎? - 拼圖

※ 引述《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

--