Re: [問題] 唯一樹造的出來嗎?

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 ((short)(-15074))時間16年前 (2009/11/20 00:14)推噓6(6推 0噓 7→)

留言13則, 4人參與討論串2/2 (看更多)

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