BST：返回大於關鍵字的第一個條目

Question

我在寫一個Java方法，它採用二叉搜索樹（BST）T和一個關鍵字k，並返回大於k的第一個條目，該條目將出現在inorder遍歷。如果k不存在或者沒有大於k的密鑰，則返回null。例如，當應用於下圖中的BST時，如果k = 23，則應該返回29;如果k = 32，則應該返回null。

http://imgur.com/fpNk9fT

的僞代碼爲：

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); 

我寫uptil現在的代碼：

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

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; 
    } 

Answer 4

讓我們試着用兩個額外的步驟通常鍵搜索：

* 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; 
}