查找BST中任意key后的后继节点

Question

我需要实现在任意键之后搜索下一个节点的方法。例如 BST 有键 {0, 2, 4, 6, 8}。对于键 1，结果必须是 2，对于键 4，结果必须是 6.

经过 google 和 SO 的一些研究，我以这种方式实现它（类似 C# 的伪代码）：

class TreeNode
{
    int Key;
    TreeNode Left;
    TreeNode Right;
}

class Tree
{
    TreeNode Root;

    TreeNode FindNextNode(int key)
    {
        TreeNode node = Root;
        TreeNode succ = null;

        while (node != null) {

            if (key >= node.Key) {
                node = node.Right;
                continue;
            }

            succ = node;
            node = node.Left;
        }

        return succ;
    }
}

一切似乎都很好，甚至可以工作，但如此简单的实现让我觉得我错过了什么。

我的实现是否正确？

更新：图片供讨论

Answer 1

看了一会儿，最新版本的实现看起来是正确的。评论中提到了这个错误：

`if (key >= null) {`

左右边框似乎也被正确处理了。如果搜索关键字超出最大值，null 被 returned。低于最小值的搜索也应该 return 列表中的第一个元素。

我唯一担心的是没有 null 输入参数检查。也许一些输入参数检查会使这个实现更加健壮。

我也不想使用 continue 而是使用 else。

这是 Kotlin 中此方法的一个版本，它强制执行非空搜索参数并使用 else 而不是 continue：

fun next(key: Key): Key? {
    var node = root
    var succ: Node<Key, Value>? = null

    while (node != null) {
        if (key >= node.key) {
            node = node.right
        }
        else {
            succ = node
            node = node.left
        }
    }

    return succ?.key
}

查找BST中任意key后的后继节点

Find the successor node in the BST after any key

algorithm

binary-tree

binary-search-tree