推 koehie:Thanks. 01/30 17:31
※ 引述《koehie (開喜烏龍茶)》之銘言：
: 請問下面這一題(99成大電機)是否有辦法求出唯一解 ?
: Assume the preorder t raversal of a binary tree is "L, J, B, A, C, G, D, E, K,
: I, F, H" and the postorder traversal of the same tree is "A, C, B, D, E, G, J
: F, H, I, K, L". Also, assume that the subtree with J as root is a full binary
: tree and J is the root of L's left subtree. Hence, K is the root of L's right
: subtree and I the root of K's right subtree. Will you be able to uniquely
: define the tree ? If yes, please draw the binary tree. If no, please indicate
: how many distinct binary trees can be derived.
這題的node也太多了吧...
還有就是full binary不知道是要用哪個定義
我假設是這個定義:
A binary tree in which each node has exactly zero or two children.
首先,我先把題目比較明確的部份畫出來:
L
/ \
J K
/\ \
(ABCDEG) I
/\
(FH)
然後其實FH那邊 稍微思考一下就會發現只有一種可能,所以變這樣:
L
/ \
J K
/\ \
(ABCDEG) I
/ \
F H
剩下的就是左邊J的子樹部份了
這坨子樹的前序: BACGDE
後序: ACBDEG
又其實不管full binary tree定義是哪個 J必定要有左右子樹
=>J的左節點為B (從前序看出) 右節點為G (從後序看出)
由前序DE在G後面可以知道 DE必接在G 並且一左一右 (如果G下方沒點 那G應該要在最後)
同理AC一定在B下 而且一左一右
現在:
L
/ \
J K
/ \ \
B G I
/\ /\ / \
(AC) (DE) F H
接下來同剛剛IFH那三個節點看過的問題
就會發現只有唯一一種可能了=> 最後:
L
/ \
J K
/ \ \
B G I
/\ /\ /\
A C D E F H
所以以我的看法只有一組解
而且不論full binary tree的定義是哪一個都只有這一組解
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.76.214
※ 編輯: jameschou 來自: 218.167.76.214 (01/30 02:07)