[理工] [資結] 決定唯一 binary tree 還有...

看板Grad-ProbAsk作者 ( )時間14年前 (2012/02/09 16:10), 編輯推噓0(0推 0噓 14→)
留言14則, 4人參與, 最新討論串1/1
1 http://imageshack.us/f/27/ds3ng.jpg/ 答案:ACDE 2 http://imageshack.us/f/259/2ds9.jpg/ 答案:ADE 上面這兩題我只知道中序配上前序或後序可以決定唯一binary tree 我想問各位 其他選項怎麼判斷??? 3 http://imageshack.us/f/402/2ds7c.jpg/ 這題是ture 但是我看不懂在算什麼... 4 http://imageshack.us/f/406/ds5e.jpg/ 這題是false 我覺得是因為找第i小的 最糟時間是O(N) 因為最糟狀況是第i小是skew BT的leaf 這個想法對嗎? 5 http://imageshack.us/f/197/2al1t.jpg/ 這題我看不懂score怎算... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.64.173.45
→
02/09 16:11, , 1F
1.BST的中序順序就是排序後的順序
02/09 16:11, 1F
→
02/09 16:12, , 2F
1.Complete Binary Tree所以除了葉子外都是滿的 照著填
02/09 16:12, 2F
→
02/09 16:42, , 3F
3.n個node的BT 有n-1個non-null link 及 n+1個null link
02/09 16:42, 3F
→
02/09 16:43, , 4F
因此 (n+1)-(n-1)=2
02/09 16:43, 4F
→
02/09 16:50, , 5F
第一題那種類型 如果是BST(包含高等BST) 已經可以推出
02/09 16:50, 5F
→
02/09 16:51, , 6F
inorder 所以只要再給其他traversal就可以 另外
02/09 16:51, 6F
→
02/09 16:53, , 7F
樹的架構如果被確定 就可以依traversal序對樹的node編號
02/09 16:53, 7F
→
02/09 16:53, , 8F
因此樹會唯一
02/09 16:53, 8F
→
02/09 23:36, , 9F
謝謝各位指教 但是我還是看不太懂w大您的判斷法...
02/09 23:36, 9F
→
02/09 23:43, , 10F
像是1的(C)沒給中序只給前序 架構也不確定卻可以決定唯一BST
02/09 23:43, 10F
→
02/10 14:44, , 11F
BST的中序其實就是由小到大排列
02/10 14:44, 11F
→
02/10 14:45, , 12F
因此給你bst的前序就可以推出中序
02/10 14:45, 12F
→
02/10 14:46, , 13F
架構就唯一
02/10 14:46, 13F
→
09/11 14:54, , 14F
1.BST的中序順序就 https://daxiv.com
09/11 14:54, 14F
‣ 更多 lexa 的文章
文章代碼(AID): #1FCt-D66 (Grad-ProbAsk)