[理工] OBST問題 AAQ8 PTT批踢踢實業坊

[理工] OBST問題

作者: AAQ8 (不要就是要) 2019-02-10 19:41:07

https://i.imgur.com/YVKnQ1R.jpg
https://i.imgur.com/64mPnlX.jpg
想問這題最後在建樹的時候
a2要怎麼知道是a1的左兒子還是右兒子

作者: skyHuan (Huan) 2019-02-10 19:47:00

看root表格，root[1,4]=3表示v1到v4樹要以v3當root，所以左邊就是v1到v2子樹，右邊就是v4到v4子樹，要分別去看root[1,2]跟root[4,4]是多少決定誰要當子樹的root

作者: MumiMumi5566 (姆咪56) 2019-02-10 19:48:00

他是BST,如果a1是root的時候a2只能放在右子樹

作者: skyHuan (Huan) 2019-02-10 19:51:00

乾抱歉XD 我發現我答非所問...我以為是問誰當root

作者: rockieloser (友善大隊長) 2019-02-10 19:52:00

放左右答案總和會不一樣？有道理他是BST==

作者: MumiMumi5566 (姆咪56) 2019-02-10 20:00:00

主要他是BST,而且如果今天a1a2下面不是nil還有其他node的話，總合就有可能不一樣吧～

作者: anonimo (unknown) 2019-02-10 21:18:00

做inorder traversal a1~4的順序不會變吧所以2一定在1的右邊

作者: AAQ8 (不要就是要) 2019-02-10 23:32:00

哦哦那我明白了感謝各位

繼續閱讀

[理工] 105交大資演AAQ8 [理工] 105 電機丙數haniwang [離散] 命題lionccc [理工] 離散 pseudo graph表示ncdonalds123 [理工] 104台大資工計系TonyXIAO [理工] 計系問題求救beatssola 107清大計組kaidi620 [理工] 107交大數學kaidi620 [理工] 107台科數學Marcolod [理工] 台聯大106 電子Rexasto

Contact Us: admin [ a t ] ucptt.com