二叉搜索树搜索返回空值

Question

我用java编写了一个实用的二叉搜索树，除了一个关键的函数，搜索。我使用的逻辑是，我将检查根是否为空，然后我要搜索的术语是否等于根（所以返回根）或>根（所以搜索右子树）或 递归方法。通过调用searchbst（string）启动搜索。<>

使用printlns查看正在发生的事情，我发现如果值在那里，它将通过正确的if语句（包括将BNode n设置为找到的值），但随后由于某种原因将再次通过方法（返回null）。

这个方法唯一起作用的时候是在搜索根节点的时候，这对我来说没有任何意义。

    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

我想你漏掉了一些返回语句：

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