我需要在任意键之后搜索下一个节点的实现方法例如,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:供讨论的图片
最佳答案
经过一段时间的研究,这个实现在最新版本中看起来是正确的评论中提到了这个错误:
`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
}