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

感谢大大，我抄错地方真多误...

继续阅读