作者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