推 Baudouine:答案正確，非常感謝您的詳盡解說 61.228.39.161 02/09 23:55
※ 編輯: guanyi999 來自: 59.117.166.184 (02/10 00:01)
推 kobala:g大 你真多時間= = 幫你推一個218.164.121.137 02/10 00:29
推 sgracee:我的痛 差點再被當= = 122.116.152.87 02/10 00:31
這個還滿好玩的~~
※ 引述《Baudouine (我好矛盾)》之銘言：
: 如果一棵二元樹的前序追蹤為 ICBADFEGH
: 中序追蹤為 ABCDIEGFH
: 問後序追蹤為 ???
前序追蹤為 ICBADFEGH
中序追蹤為 ABCDIEGFH
所以root 是I
在I的左邊只有ABCD ，在I的右邊只有EGFH
I
第二個是c，C以中序來說在 I 的左邊，所以就排在I的左邊，
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
C的左邊只有AB，C的右邊只有D
以下同理可證，懶的寫了~
I
/
C
第三個B ，B在C的左邊，所以是
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/
C
/
B
第四個是A，A在B 的左邊，所以是
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/
C
/
B
/
A
第五個是D，D在C的右邊，所以是
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/
C
/ \
B D
/
A
第六個是F，F在I的右邊，所以是
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/ \
C F
/ \
B D
/
A
第七個是E，E在F左邊，所以是
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/ \
C F
/ \ /
B D E
/
A
第八個是G，G在F的左邊，在E的右邊
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
I
/ \
C F
/ \ /
B D E
/ \
A G
第九個是H，H在F的右邊，
前序追蹤為 ICBADFEGH
中序追蹤為 ABCD I EGFH
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