作者guanyi999 (灌)
看板ask
标题Re: [请问] 二元树的追踪
时间Mon Feb 9 23:52:13 2009
这个还满好玩的~~
※ 引述《Baudouine (我好矛盾)》之铭言：
: 如果一棵二元树的前序追踪为 ICBADFEGH
: 中序追踪为 ABCDIEGFH
: 问後序追踪为 ???
前序追踪为
ICBADFEGH
中序追踪为 ABCD
IEGFH
所以root 是I
在I的左边只有ABCD ，在I的右边只有EGFH
I
第二个是c，C以中序来说在 I 的左边，所以就排在I的左边，
前序追踪为 I
CBADFEGH
中序追踪为 AB
CD I EGFH
C的左边只有AB，C的右边只有D
以下同理可证，懒的写了~
I
/
C
第三个B ，B在C的左边，所以是
前序追踪为 IC
BADFEGH
中序追踪为 A
BCD I EGFH
I
/
C
/
B
第四个是A，A在B 的左边，所以是
前序追踪为 ICB
ADFEGH
中序追踪为
ABCD I EGFH
I
/
C
/
B
/
A
第五个是D，D在C的右边，所以是
前序追踪为 ICBA
DFEGH
中序追踪为 ABC
D I EGFH
I
/
C
/ \
B D
/
A
第六个是F，F在I的右边，所以是
前序追踪为 ICBAD
FEGH
中序追踪为 ABCD I EG
FH
I
/ \
C F
/ \
B D
/
A
第七个是E，E在F左边，所以是
前序追踪为 ICBADF
EGH
中序追踪为 ABCD I
EGFH
I
/ \
C F
/ \ /
B D E
/
A
第八个是G，G在F的左边，在E的右边
前序追踪为 ICBADFE
GH
中序追踪为 ABCD I E
GFH
I
/ \
C F
/ \ /
B D E
/ \
A G
第九个是H，H在F的右边，
前序追踪为 ICBADFEG
H
中序追踪为 ABCD I EGF
H
I
/ \
C F
/ \ / \
B D E H
/ \
A G
所以後序就是... ABDCGEHFI
对一下答案吧~
有错请指正 ^^"
: 想问这是一定要去画树来看吗？还是有其他比较快的解法呢？
: I
: C F
: B D
: A
: ===========
: E G H 我不知道该怎麽画唉，有没有人可以跟我讲一下呢...
: 感谢了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.117.166.184
1F：推 Baudouine:答案正确，非常感谢您的详尽解说 61.228.39.161 02/09 23:55
※ 编辑: guanyi999 来自: 59.117.166.184 (02/10 00:01)
2F：推 kobala:g大 你真多时间= = 帮你推一个218.164.121.137 02/10 00:29
3F：推 sgracee:我的痛 差点再被当= = 122.116.152.87 02/10 00:31