※ 引述《lwhs (lwhs)》之銘言：
: 一個二元樹有10個節點
: 後序 LRD 依序為 D A H F J I E G B C
: 中序 LDR 依序為 D C A B E H F I J C
: 請畫出此二元樹 解答 Binary tree 如下:
: 小弟比較困惑的地方是 G E 這邊我有點轉不過來@@
: C
: / \
: D B
: / \
: A G
: /
: E
: \
: I
: / \
: F J
: /
: H
: 還有像這種考法的答案是不是都不唯一?
: 假如一個邏輯錯後面全錯了!?
: 想請問高手的思考模式? 感謝!!

後序 LRD D A H F J I E G B |C| (ROOT為C)
中序 LDR D |C| A B E H F I J G
切完後可得左子樹只有D一個點

左子樹 右子樹 ROOT
後序 D A H F J I E G B |C|

左子樹 ROOT 右子樹
中序 D C A B E H F I J G


可得到 C 這棵binary tree
/ \
D ABEHFIJG





因為左子樹只有一個點
所以只對這棵binary tree之右子樹做切割
LRD之右子樹 A H F J I E G B
LDR之右子樹 A B E H F I J G

由LRD得知右子樹之root為B
再由LDR可得知左子樹為A 右子樹為E H F I J G

左子樹(L) 右子樹(R) ROOT(D)
LRD A H F J I E G |B|
左子樹(L) ROOT(D) 右子樹(R)
LDR A |B| E H F I J G

可得到 C
/ \
D B
/ \
A EHFIJG




此時以B為ROOT之左子樹只有A一個點
只對這棵binary tree之右子樹做切割
LRD之右子樹 H F J I E G
LDR之右子樹 E H F I J G

由LRD得知右子樹之root為G
再由LDR可得知左子樹為EHFIJ 右子樹為空

左子樹(L) 右子樹(R) ROOT(D)
LRD H F J I E 空 |G|
左子樹(L) ROOT(D) 右子樹(R)
LDR E H F I J |G| 空

可得 C
/ \
D B
/ \
A G
/
EHFIJ


此時以G為ROOT之右子樹為空
只對這棵binary tree之左子樹做切割
LRD之左子樹 H F J I E
LDR之左子樹 E H F I J

由LRD得知左子樹之root為E
再由LDR可得知左子樹為空 右子樹為HFIJ

左子樹(L) 右子樹(R) ROOT(D)
LRD 空 H F J I |E|
左子樹(L) ROOT(D) 右子樹(R)
LDR 空 |E| H F I J
可得到 C
/ \
D B
/ \
A G
/
E
\
HFIJ

此時以E為ROOT之左子樹為空
只對這棵binary tree之右子樹做切割
LRD之右子樹 H F J I
LDR之右子樹 H F I J

由LRD得知此右子樹之root為I
再由LDR可得知左子樹為HF 右子樹為J


左子樹(L) 右子樹(R) ROOT(D)
LRD H F J |I|
左子樹(L) ROOT(D) 右子樹(R)
LDR H F |I| J

可得到 C
/ \
D B
/ \
A G
/
E
\
I
/ \
HF J



















此時以I為ROOT之右子樹只有J一個點
只對這棵binary tree之左子樹做切割
LRD之左子樹 H F
LDR之左子樹 H F

由LRD得知root(D)為F
再由LDR可得知左子樹為H 右子樹為空


左子樹(L) 右子樹(R) ROOT(D)
LRD H 空 |F|
左子樹(L) ROOT(D) 右子樹(R)
LDR H |F| 空



可得到 C
/ \
D B
/ \
A G
/
E
\
I
/ \
F J
/
H

此時每個點至多一個值 則完成

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.163.233.43
※ 編輯: seal0112 來自: 1.163.233.43 (03/17 14:01)