我正在为所上的课解决一个问题。它涉及向二进制搜索树中添加一种方法,该方法在此处找到:http://algs4.cs.princeton.edu/32bst/BST.java.html
我需要开发一种迭代的上限方法,该方法可以找到给定键的上限。它不能递归。
到目前为止,这是我的代码。我了解我应该实现的算法的基础知识,但是我发现实际上很难做到。
预先感谢您可能提供的任何帮助。
public Key ceiling_i(Key key)
{
Node t = root;
for(int i = 0; i < size(); i++){
int cmp = key.compareTo(t.key);
if(cmp == 0) return t.key;
else if(cmp < 0) t = t.left;
else if(cmp > 0) t = t.right;
}
return null;
}
编辑:我遇到的主要问题是如何处理第一个迭代之后的迭代。根据我的书,“如果给定的密钥大于BST根的密钥,
然后键的上限(BST中的最大键更大
等于或等于key)必须在正确的子树中。如果键是
小于根的键,则键的上限可以
在左子树中;如果不是(或者密钥等于密钥
在根处),则根处的密钥就是密钥的上限。”我不确定如何在循环中处理该问题。
最佳答案
您的代码是一个好的开始。但是您的for循环对我来说没有意义。
public Key ceiling_i(Key key)
{
Node t = root;
Node t largestVisited = null;
while(t != null) {
int cmp = key.compareTo(t.key);
if(cmp == 0) return t.key;
else if(cmp < 0) { largestVisited = Min(t, largestVisited); t = t.left; }
else if(cmp > 0) { t = t.right; largestVisited = Min(t, largestVisited); }
}
return largestVisited;
}
Node Min(Node a, Node b) { return the node with the smaller key; }
提示:您可以通过首先编写递归解决方案并注意到它是尾递归来派生此代码。仅通过重用已经存在的局部变量,尾部递归函数就可以简单地变为非递归。如果您再也不会使用旧的堆栈框架,则无需打开另一个堆栈框架。