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