Re: [理工] 一題資料結構二元樹排序
是唯一喔
後序 LRD 依序為 D A H F J I E G B C
所以C是10個node的root
中序 LDR 依序為 D C A B E H F I J G
所以C的左右子樹為 D A B E H F I J G
這樣就知道C的左右子樹的組成了
如此將後序分為 (D) (A H F J I E G B) (C) 3部份
C
/ \
(D) (A H F J I E G B)
其中(A H F J I E G B)為C的右子樹
由於是後序 所以B是root
再回來看中序 分為 A E H F I J G
知道說B的右子樹組成為 E H F I J G
將C的右子樹的後序 分為 (A) (H F J I E G) (B) 3部份
B
/ \
(A) (H F J I E G)
其中(H F J I E G)為B的右子樹
由於是後序 所以G是root
再回來看中序 E H F I J 可知G只有左子樹 無右子樹
將B的右子樹的後序 分為 (H F J I E) (G) 2部份
G
/
(H F J I E)
其中(H F J I E)為G的左子樹
由於是後序 所以E是root
再回來看中序 H F I J 可知E只有右子樹 無左子樹
將G的左子樹的後序 分為 (H F J I) (E) 2部份
E
/
(H F J I)
其中(H F J I)為E的左子樹
由於是後序 所以I是root
再回來看中序 H F J
將E的左子樹的後序 分為 (H F) (J) (I) 3部份
I
/ \
(H F) (J)
由於(H F)是後序 所以F是root
再回來看中序 H F
F
/
H
可得結果為
C
/ \
D B
/ \
A G
/
E
\
I
/ \
F J
/
H
結論:
這種題目會給你中序 和前後序其中之一
你要做的就是
do{
從前後序找root 前序就把第一個抓出來 後序就把最後一個抓出來
用root把中序分成 左子樹 root 右子樹 3部份
}until(整棵樹被畫出來)
如此就能畫出來了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.205.246
推
03/17 13:21, , 1F
03/17 13:21, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 3 篇)：
理工
1
4