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