二进制搜索树搜索返回空

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