algorithm - 如何在二叉搜索树中设置下界？

Question

当我在二叉搜索树中给出一些整数时，我得到了最近的下界

  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。

Answer 1

作业？

然后只是一些提示:

• 只有使用t.key == x才能成功退出循环，所以除非x在树中，否则无法成功返回。听起来不对。
• 如果在某个时候您选择向右走，那么您就知道树中至少有一个值小于 x。所以在你至少走对一次之后，就有了一个解决方案，你不应该失败。这不会出现在您的代码中。
• 当您选择向右走时，那里可能没有数据，您应该检查一下。
• 画一个小的 BST 并在图上检查你的想法，这应该会有很大帮助。

还有

• 确定你计算的是什么。小于或等于 x，或严格小于 x 的最大元素？
• 也许你可以尝试递归实现。