[問題] 二元搜尋樹 hasuekee29 PTT批踢踢實業坊

[問題] 二元搜尋樹

作者: hasuekee29 (Yueh) 2016-04-18 23:09:12

給予下列條件，何者可以決定唯一二元樹?
(A)Binary Search Tree + Preorder
(B)Binary Search Tree + Inorder
(C)Binary Search Tree + Postorder
(D)Binary Search Tree + Level-order
Ans:ACD
問題:
二元搜尋樹的形狀固定，給予任何追蹤序應該都可以決定唯一二元樹，
我認為答案是ABCD，想請教為何沒有B，感謝各位!

作者: jachin (火腿哥) 2016-04-19 00:20:00

請問題目出處？我認為答案非唯一，是AB或BC或ACD

作者: asd51052000 (sky) 2016-04-19 01:01:00

一定要給予中序才能決定唯一二元樹

作者: jachin (火腿哥) 2016-04-19 08:15:00

原諒我，沒搞清楚Level-order原來就是BSF,所以只有AB, BC,BD才能有唯一BST,所以題目是否是→以下何者非唯一BST的必要條件，那就是ACD了

作者: opop4350 (小捲) 2016-04-19 12:48:00

http://i.imgur.com/ARDv1N7.jpg舉例子來反證，如果有錯各位指教

作者: max60716 (Brady) 2016-04-19 15:54:00

題目bug很大他沒有寫相異key，另外我想法因為中序是要跨左右子樹的演算法，所以基本上配上BST變化會比較多

作者: jachin (火腿哥) 2016-04-19 23:36:00

回op大，錯很大，呵呵，你的A, C, D都非唯一唷

作者: bochange 2016-04-20 01:41:00

請教j大 op大的例子中A,C,D還有哪個二元樹符合? 想不到

作者: jachin (火腿哥) 2016-04-20 08:17:00

A. 3 3 3/ \ \ \2 1 2 2/ \1 1手機排版，抱歉，其他依此類推。另．．B也不止那三種BST唷

作者: opop4350 (小捲) 2016-04-20 11:31:00

回j大，你畫的樹不是BST耶

作者: jachin (火腿哥) 2016-04-20 23:32:00

懂了，謝謝op大指導，還沒看這樣的題型，完全會錯意（筆記

繼續閱讀

[補習] 地特行政類之補習選擇？ellen1215 [問題] 法學緒論 Fisher0 [贈送] 2B鉛筆45枝 (已額滿）grace33336 [課業] 電力電子semmy214 [閒聊] 學校成績vs考試成績dosandonts [問題] 郵局vs初考avonc1017 Re: [課業] 消滅時效期間之起算Zyth [問題] 關於今天補習班跟我的分析是否可以參考?tok892xt7 聊聊今年的關務電機類吧！success18 郝強的郝語特報caca7