当我在二叉搜索树中给出一些整数时,我得到了最近的下界
def lowerBound(x : Int) : Int = {
var t = root
var result : Int = 0
while(t.key != x) {
if(x == t.key) {
result = t.left.key
}
else{
if(x < t.key) {
t = t.left
if(t == null) {
throw new NoSuchElementException
}
else {
result = t.key
}
}
else {
t = t.right
}
}
}
result
}
我就是这样做的。但它不打印任何结果。 T T .... 我的算法中有反例吗?
如果有 {2, 3, 5, 7 ,8, 10, 99} lowerBound(6) 为 5。
最佳答案
作业?
然后只是一些提示:
- 只有使用
t.key == x
才能成功退出循环,所以除非x在树中,否则无法成功返回。听起来不对。 - 如果在某个时候您选择向右走,那么您就知道树中至少有一个值小于 x。所以在你至少走对一次之后,就有了一个解决方案,你不应该失败。这不会出现在您的代码中。
- 当您选择向右走时,那里可能没有数据,您应该检查一下。
- 画一个小的 BST 并在图上检查你的想法,这应该会有很大帮助。
还有
- 确定你计算的是什么。小于或等于 x,或严格小于 x 的最大元素?
- 也许你可以尝试递归实现。
关于algorithm - 如何在二叉搜索树中设置下界?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8314405/