[問題] 二元搜尋樹

看板Examination作者 (Yueh)時間8年前 (2016/04/18 23:09), 編輯推噓10(10推 0噓 9→)
留言19則, 5人參與, 最新討論串2/2 (看更多)
給予下列條件，何者可以決定唯一二元樹? (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，感謝各位! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.73.160 ※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1460992155.A.20D.html
推
04/19 00:20, , 1F
請問題目出處？我認為答案非唯一，是AB或BC或ACD
04/19 00:20, 1F
推
04/19 01:01, , 2F
一定要給予中序才能決定唯一二元樹
04/19 01:01, 2F
推
04/19 08:15, , 3F
原諒我，沒搞清楚Level-order原來就是BSF,所以只有AB, BC,
04/19 08:15, 3F
→
04/19 08:15, , 4F
BD才能有唯一BST,所以題目是否是→以下何者非唯一BST的必
04/19 08:15, 4F
→
04/19 08:15, , 5F
要條件，那就是ACD了
04/19 08:15, 5F
推
04/19 12:48, , 6F
04/19 12:48, 6F
→
04/19 12:48, , 7F
舉例子來反證，如果有錯各位指教
04/19 12:48, 7F
推
04/19 15:54, , 8F
題目bug很大 他沒有寫相異key，另外我想法因為中序是要
04/19 15:54, 8F
→
04/19 15:55, , 9F
跨左右子樹的演算法，所以基本上配上BST變化會比較多
04/19 15:55, 9F
推
04/19 23:36, , 10F
回op大，錯很大，呵呵，你的A, C, D都非唯一唷
04/19 23:36, 10F
推
04/20 01:41, , 11F
請教j大 op大的例子中A,C,D還有哪個二元樹符合? 想不到
04/20 01:41, 11F
推
04/20 08:17, , 12F
A. 3 3 3
04/20 08:17, 12F
→
04/20 08:17, , 13F
/ \ \ \
04/20 08:17, 13F
→
04/20 08:17, , 14F
2 1 2 2
04/20 08:17, 14F
→
04/20 08:17, , 15F
/ \
04/20 08:17, 15F
→
04/20 08:17, , 16F
1 1
04/20 08:17, 16F
→
04/20 08:17, , 17F
手機排版，抱歉，其他依此類推。另．．B也不止那三種BST唷
04/20 08:17, 17F
推
04/20 11:31, , 18F
回j大，你畫的樹不是BST耶
04/20 11:31, 18F
推
04/20 23:32, , 19F
懂了，謝謝op大指導，還沒看這樣的題型，完全會錯意（筆記
04/20 23:32, 19F
‣ 更多 hasuekee29 的文章
文章代碼(AID): #1N5FYR8D (Examination)
‣ 更多 hasuekee29 的文章
文章代碼(AID): #1N5FYR8D (Examination)