java - 二分查找 树查找返回 Null

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