Re: [問題][難題]無運算子(+-*/)之前中後置轉換

[qrtt1 (隱者)]

※ 引述《jazzblur (雞蛋糕好食!)》之銘言：
: 程式的目標為
: 給定中序與前序求後序
: 或
: 給定中序與後序求前序
: 例
: 中序43512
: 前序13452
: 要求得
: 後序45321
: 例二
: 後序3 4 2 6 7 8 9 5 10 11 1 12 0
: 中序0 2 3 4 1 5 7 6 9 8 11 10 12
       後序最後一個是root, 0 is root
       得中序
               0
              / \ 2 3 4 1 5 7 6 9 8 11 10 12

       posto :  3 4 2 6 7 8 9 5 10 11 1 12
       ino   :  2 3 4 1 5 7 6 9 8 11 10 12

        這一層的root is 12
                           0
                          / \
                            12
 2 3 4 1 5 7 6 9 8 11 10   /  \

       posto :  3 4 2 6 7 8 9 5 10 11 1
       ino   :  2 3 4 1 5 7 6 9 8 11 10
       (這一層的root is 1)
                           0
                          / \
                            12
                           /
                          1
                  2 3 4  / \ 5 7 6 9 8 11 10

       posto :  3 4 2 6 7 8 9 5 10 11
       ino   :  2 3 4   5 7 6 9 8 11 10
       (這一層的root is 11)

                           0
                          / \
                            12
                           /
                          1
                  2 3 4  / \
                            11
                           /  \
                  5 7 6 9 8    10

       posto :  3 4 2 6 7 8 9 5
       ino   :  2 3 4   5 7 6 9 8
       (這一層的root is 5, 10到leaf了, 不理他)


                           0
                          / \
                            12
                           /
                          1
                  2 3 4  / \
                            11
                           /  \
                          5    10
                           \ 7 6 9 8

       posto :  3 4 2 6 7 8 9
       ino   :  2 3 4     7 6 9 8
       (這一層的root is 9)

                           0
                          / \
                            12
                           /
                          1
                  2 3 4  / \
                            11
                           /  \
                          5    10
                           \
                            9
                           / \
                        7 6   8

       posto :  3 4 2 6 7 8
       ino   :  2 3 4     7 6   8
       (這一層的root is 9)

       posto :  3 4 2 6 7 8
       ino   :  2 3 4     7 6   8
       (這一層的root is 8, 同上圖)

                           0
                          / \
                            12
                           /
                          1
                  2 3 4  / \
                            11
                           /  \
                          5    10
                           \
                            9
                           / \
                          7   8
                           \
                            6

       posto :  3 4 2 6 7
       ino   :  2 3 4     7 6
       (這一層的root is 7)

       posto :  3 4 2 6
       ino   :  2 3 4     6
       (這一層的root is 6)

       posto :  3 4 2
       ino   :  2 3 4
       (這一層的root is 2)

                           0
                          / \
                            12
                           /
                          1
                       /   \
                      2    11
                       \   /  \
                      3 4  5    10
                           \
                            9
                           / \
                          7   8
                           \
                            6

        ============================================好難畫orz
       posto :  3 4 2
       ino   :  2 3 4
       (這一層的root is 2)
                 .
                /
               2
                \ 3 4

       posto :  3 4
       ino   :    3 4
       (這一層的root is 4)

                 .
                /
               2
                \
                 4
                /
               3

        有樹了, 前序就靠施主了

: 要求得
: 前序0 12 1 2 4 3 11 5 9 7 6 8 10
: 沒有讀取運算子(+-*/)的作法
: 那還有辦法做嗎?
: 有沒有什麼公式還是規律
: .....真的想破頭了說Orz.....
: 請各位指點一下方向吧
: ===================================分隔線====================================
: ........明明就還沒學過資料結構
: 什麼二元樹的問題嘛 丟!
: 而且還沒有運算子.....丟!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.26.34.105
→ qrtt1:給前中序算法也一點, 前序的第一個為那一層的root
→ qrtt1:中序則決定資料群落在左邊還右邊, root 左邊的是左邊, 右邊
→ qrtt1:的是右邊@"@ (我在說什麼!?) ps. 給前後序就翻桌
推 UNARYvvv:這篇好猛..推!
→ qrtt1:這是期末考最佳良伴啊orz 只是前一次回答應該是3年前了..
推 jazzblur:@@ 真是一語驚醒我夢中人...嚇得我.屁滾...會種了會種了
推 roga:推qrtt1前輩用心良苦。
推 drkkimo:基本但蠻常見的題目:) 收精華~:)