我需要在任意键之后搜索下一个节点的实现方法例如,bst具有键{0, 2, 4, 6, 8}。对于key1结果必须2,对于key4结果必须6
经过google等公司的研究,我以这种方式实现了它(类似于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;
    }
}

一切看起来都很好,甚至可以工作,但是这么简单的实现让我觉得我错过了任何东西。
我的实施是否正确?
Upd:供讨论的图片
algorithm - 在任意键后在BST中找到后继节点-LMLPHP

最佳答案

经过一段时间的研究,这个实现在最新版本中看起来是正确的评论中提到了这个错误:

`if (key >= null) {`

同时,左边框和右边框的处理似乎也很正确。如果搜索关键字超出最大值,则返回null。低于最小值的搜索还应返回列表中的第一个元素。
我唯一关心的是没有检查输入参数也许一些输入参数检查会使这个实现更加健壮。
我也不希望使用null而使用else。
下面是Kotlin中此方法的一个版本,它强制使用非空搜索参数并使用continue而不是else
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
}

10-08 03:49