问二叉树查找比键更近和更大的数字

EN

假设您指的是“二进制搜索树”而不是“二叉树”，则不需要进行任何修改就可以在树中找到最小元素y，从而使y >= x。

search(n, x, best_so_far) ::=
    if n == nil { return best_so_far }
    if n.value == x { return x }
    if n.value > x { return search(n.left, x, min(best_so_far, n.value) }
    if n.value < x { return search(n.right, x, best_so_far) }

您可以将此函数称为search(root, x, +infinity)。

这样做的想法是，如果您在节点n处探索左分支，则不需要考虑n右侧的任何东西: n.value大于x，右边的所有东西都大于n.value。类似地，如果您正在探索节点n的右分支，那么您可以丢弃n左边的所有东西: n.value小于x，而n左边的所有东西都小于n.value。

代码运行时以树的高度为界，如果树是平衡的，O(log )也是如此。