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