看板 TL
作者 標題 [筆記] 以知前序和中序排列 如何求得整顆樹的結構
時間 2013年01月27日 Sun. PM 06:42:23
看板 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
→ :給前中序算法也一點, 前序的第一個為那一層的root1F 06/21 22:16
→ :中序則決定資料群落在左邊還右邊, root 左邊的是左邊, 右邊
→ :的是右邊@"@ (我在說什麼!?) ps. 給前後序就翻桌
→ :中序則決定資料群落在左邊還右邊, root 左邊的是左邊, 右邊
→ :的是右邊@"@ (我在說什麼!?) ps. 給前後序就翻桌
推 :這篇好猛..推!4F 06/21 22:18
→ :這是期末考最佳良伴啊orz 只是前一次回答應該是3年前了..5F 06/21 22:22
推 :@@ 真是一語驚醒我夢中人...嚇得我.屁滾...會種了會種了6F 06/21 22:38
推 :推qrtt1前輩用心良苦。7F 06/22 00:19
推 :基本但蠻常見的題目:) 收精華~:)8F 06/22 00:31
--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:42:23
※ 看板: TL 文章推薦值: 0 目前人氣: 0 累積人氣: 18
回列表(←)
分享