二進制搜索樹搜索返回空

Question

我已經寫了一個功能二進制搜索樹在Java中除了一個關鍵功能，搜索。我正在使用邏輯，我將檢查根是否爲空，然後如果我想搜索的術語等於根（所以返回根）或>根（所以搜索右子樹）或<根（搜索右子樹）使用遞歸方法。搜索通過調用searchBST（String）開始。

使用printlns來查看發生了什麼我發現如果值在那裏，它會通過正確的if語句（包括將nbn設置爲找到的值），但會因爲某種原因再次通過該方法（返回空值）。

這種方法唯一的工作是搜索根節點，這對我來說沒有意義。

public BNode search(BNode par, String k){ 
    BNode n = null; 

    if (par != null){ 
     if ((k.compareTo(par.obj.getKey()) < 0) && (par.left != null)){ 
      search(par.left, k); 
     } 

     if ((k.compareTo(par.obj.getKey()) > 0) && (par.right != null)){ 
      search(par.right, k); 
     } 

     if (k.compareTo(par.obj.getKey()) == 0){ 
      n = par;  
     } 
    } 

    return n; 

} 

public AnyClass searchBST(String k){ 
    if (search(root, k) != null) 
    return search(root, k).obj; 

    return null; 
} 

Answer 1

我想你錯過了一些return語句：

public BNode search(BNode par, String k){ 
    BNode n = null; 

    if (par != null){ 
     if ((k.compareTo(par.obj.getKey()) < 0) && (par.left != null)){ 
      return search(par.left, k); 
     } 

     if ((k.compareTo(par.obj.getKey()) > 0) && (par.right != null)){ 
      return search(par.right, k); 
     } 

     if (k.compareTo(par.obj.getKey()) == 0){ 
      n = par;  
     } 
    } 

    return n; 
}