BST:返回第一个大于键的条目

Question

我正在编写一个Java方法，该方法使用二进制搜索树（BST）T和关键字k，并返回在有序遍历中出现的第一个大于k的条目。如果不存在k或者不存在大于k的密钥，则返回null。例如，当应用于下图中的BST时，如果k=23，则应返回29；如果k=32，则应返回null。

https://i.stack.imgur.com/ydiBv.jpg

伪代码是：

findFirstEntryLargerThanKey(BSTNode t, int key)
// go left
findFirstEntryLargerThanKey(t.left, key);
// visit the node
if t.nodeValue == key 
key exists, set a boolean value to true
else if t.nodeValue > key
check if this node value is the first entry larger than key
// go right
findFirstEntryLargerThanKey(t.right, key);

我现在写的代码是：

boolean found = false;
int x = 0;
public Integer findFirstEntryLargerThanKey(BSTNode t, int key) { 
    // the scan terminates on an empty subtree
    if (t != null) {

        // descend left 
        findFirstEntryLargerThanKey(t.left, key); 
        // visit the node
        if (t.nodeValue == key){
            found = true;
        }
        else if (t.nodeValue > key && found == true && ? && ?){
        x = t.nodeValue;
        }
        // descend right
        findFirstEntryLargerThanKey(t.right, key);
        return x;
    } 
    return null;
}

关于我必须使用的条件，我需要帮助。

Answer 1

按顺序遍历，按升序打印树键。同时不断比较密钥并打印第一个大于密钥的密钥。。时间复杂度将小于O（n）

Answer 2

您可以在找到答案时直接返回，因为x是全局声明的。

你的功能应该是这样的：

boolean found = false;
int x = 0;
public Integer findFirstEntryLargerThanKey(BSTNode t, int key) { 
    // the scan terminates on an empty subtree
    if (t != null) {

        // descend left 
        findFirstEntryLargerThanKey(t.left, key); 
        // visit the node
        if (t.nodeValue == key){
            found = true;
        }
        else if (t.nodeValue > key && found == true){
            x = t.nodeValue;
            return x;
        }
        // descend right
        findFirstEntryLargerThanKey(t.right, key);
        return x;
    } 
    return null;
}

或者，做一些类似的事情：

int x = 0;
public Integer findFirstEntryLargerThanKey(BSTNode t, int key) { 
    // the scan terminates on an empty subtree
    if (t != null) {

        // descend left 
        findFirstEntryLargerThanKey(t.left, key); 
        // visit the node
        if (t.nodeValue > key){
            x = t.nodevalue;
            return x;
        }
        // descend right
        findFirstEntryLargerThanKey(t.right, key);
        return x;
    } 
    return null;
}

Answer 3

让我们用两个额外的步骤来尝试通常的关键字搜索：

 * Whenever we go left from a parent to a child, 
   remember the parent as a potential answer.
 * If the key is found and it has a right subtree, 
   then the answer is left-most (smallest) node of that subtree.
FindFirstEntryLargerThanKey(BSTNode t, int key) {
  BSTNode result_so_far = null;
  for (BSTNode cur = t; cur; ) {
    if (key < cur->key) {
      result_so_far = cur;
      cur = cur->left;
    }
    else if (key == cur->key) {
      if (cur->right) {
        result_so_far = LeftMostNode(cur->right);
      }
      break;
    }
    else {
      cur = cur->right;
    }
  }
  return result_so_far;
}

Answer 4

    try this out

    public Integer findFirstEntryLargerThanKey(BSTNode t, int key) { 
Integer x =null;
        // the scan terminates on an empty subtree
        if (t != null && x!=null) {

            // descend left 
            findFirstEntryLargerThanKey(t.left, key); 
            // visit the node

             if (t.nodeValue > key  ||t.nodeValue==key){
                x = t.nodeValue;

            }
            // descend right
            findFirstEntryLargerThanKey(t.right, key);
        } 
        return x;
    }