[理工] 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