[理工] 資結 BST AdonisLam PTT批踢踢實業坊

作者: AdonisLam (Adonis) 2019-08-16 21:35:48

參考附圖（上課筆記）
左下計算full BST平均比較次數S
為什麼點數要乘上level?
https://imgur.com/a/tNUphxL

作者: DingDang827 (叮叮噹) 2019-08-16 21:58:00

要找到第k層的點要經過k次比較所以第一層的點比較1次第二層的點比較2次以此類推

作者: mathtsai (mathtsai) 2019-08-16 22:15:00

什麼叫做比較次數。。。是在問search某個node 所需要的比較次數嗎= =？

作者: jpg74568 (空你在哪?) 2019-08-16 23:05:00

https://i.imgur.com/nUxTB43.jpg你從程式碼去看會比較有印象，如果找不到T=Nill的話就不會列入比較次數，所以每次的比較的比較次數為level值

作者: mathtsai (mathtsai) 2019-08-17 00:05:00

樓上的程式碼真的能動嗎？return search(T,leftChild的值) 那原本傳入的X跑哪去了感覺function少傳參數 search(BST,node,X)類似這樣밠

作者: FXW11314 (soukai) 2019-08-17 02:31:00

他寫的是T->leftchild,x，不是T->leftchild.x

作者: jpg74568 (空你在哪?) 2019-08-17 08:33:00

感謝大大，我抄錯地方真多誤...

繼續閱讀