作者qrtt1 (隱者)
看板C_and_CPP
標題Re: [問題][難題]無運算子(+-*/)之前中後置轉換
時間Wed Jun 21 22:11:47 2006
※ 引述《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
1F：→ qrtt1:給前中序算法也一點, 前序的第一個為那一層的root 06/21 22:16
2F：→ qrtt1:中序則決定資料群落在左邊還右邊, root 左邊的是左邊, 右邊 06/21 22:16
3F：→ qrtt1:的是右邊@"@ (我在說什麼!?) ps. 給前後序就翻桌 06/21 22:17
4F：推 UNARYvvv:這篇好猛..推! 06/21 22:18
5F：→ qrtt1:這是期末考最佳良伴啊orz 只是前一次回答應該是3年前了.. 06/21 22:22
6F：推 jazzblur:@@ 真是一語驚醒我夢中人...嚇得我.屁滾...會種了會種了 06/21 22:38
7F：推 roga:推qrtt1前輩用心良苦。 06/22 00:19
8F：推 drkkimo:基本但蠻常見的題目:) 收精華~:) 06/22 00:31
9F：→ drkkimo:解說的很清楚 06/22 00:44
10F：推 garbager:厲害 上次看到這題 也很困惑@@ 06/22 11:20