[问题] 二元搜寻树 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