[理工] OBST問題

看板Grad-ProbAsk作者時間5年前 (2019/02/10 19:41), 編輯推噓3(3推 0噓 9→)
留言12則, 5人參與, 5年前最新討論串1/1
https://i.imgur.com/YVKnQ1R.jpg
https://i.imgur.com/64mPnlX.jpg
想問這題最後在建樹的時候 a2要怎麼知道是a1的左兒子還是右兒子 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.65.175 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549798869.A.039.html
推
02/10 19:47, 5年前 , 1F
看root表格，root[1,4]=3表示v1到v4樹要以v3當root，所以
02/10 19:47, 1F
→
02/10 19:47, 5年前 , 2F
左邊就是v1到v2子樹，右邊就是v4到v4子樹，要分別去看roo
02/10 19:47, 2F
→
02/10 19:47, 5年前 , 3F
t[1,2]跟root[4,4]是多少決定誰要當子樹的root
02/10 19:47, 3F
→
02/10 19:48, 5年前 , 4F
他是BST,如果a1是root的時候a2只能放在右子樹
02/10 19:48, 4F
推
02/10 19:51, 5年前 , 5F
乾抱歉XD 我發現我答非所問...我以為是問誰當root
02/10 19:51, 5F
→
02/10 19:52, 5年前 , 6F
放左右答案總和會不一樣？
02/10 19:52, 6F
→
02/10 19:58, 5年前 , 7F
有道理 他是BST==
02/10 19:58, 7F
→
02/10 20:00, 5年前 , 8F
主要他是BST,而且如果今天a1a2下面不是nil還有其他n
02/10 20:00, 8F
→
02/10 20:00, 5年前 , 9F
ode的話，總合就有可能不一樣吧～
02/10 20:00, 9F
推
02/10 21:18, 5年前 , 10F
做inorder traversal a1~4的順序不會變吧
02/10 21:18, 10F
→
02/10 21:19, 5年前 , 11F
所以2一定在1的右邊
02/10 21:19, 11F
→
02/10 23:32, 5年前 , 12F
哦哦那我明白了 感謝各位
02/10 23:32, 12F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SO0tL0v (Grad-ProbAsk)