java—如何在avl树中找到特定值并返回节点

aoyhnmkz  于 2021-06-29  发布在  Java
关注(0)|答案(2)|浏览(405)
public Node search_data_var2(Comparable searchable, Node T){
        if(T.getInfo()==searchable){
            return(T);
        }
        else{
            if(T.getInfo()==null){
                return null;
            }
            if(T.getInfo().compareTo(searchable)>0){
                search_data_var2(searchable,T.getLeft());
            }
            if(T.getInfo().compareTo(searchable)<0){
                search_data_var2(searchable,T.getRight());
            }
        }
}

我需要创建一个方法,找到一个具有特定值“searchable”的节点,并在包含它时返回节点“t”。如果这样的值不存在,函数应该返回“null”。我有麻烦,但不知道如何实现这个单一的方法。上面的函数就是我写的。问题是该方法不能以相同的方式返回node和null。
不禁止使用外部函数来实现这一点,但目前我还不知道如何实现这一点。

jk9hmnmh

jk9hmnmh1#

问题是该方法不能以相同的方式返回node和null。
是的,您可以,但是您需要调整您的代码以适应

public Node search_data_var2(Comparable searchable, Node T){
       ....
            if(T.getInfo().compareTo(searchable) > 0){
                return search_data_var2(searchable,T.getLeft()); // <-- add return
            }
            if(T.getInfo().compareTo(searchable) < 0){
                return search_data_var2(searchable,T.getRight()); // <-- add return
            }
       ...
    }

返回将由 search_data_var2 递归方法调用。顺便说一句,你不应该使用 T 作为变量名,通常这样的名称(即一个大写字母)用于泛型类型。而且 == 你应该使用 compareTo 方法(即。, T.getInfo().compareTo(searchable) == 0 ).
最后,您的代码可能会抛出 NPE 因为你是第一个检查的

if(T.getInfo()==searchable)

在实际检查是否 T.getInfo()null 或者如果 Tnull 它自己。因此,您需要重新排列条件,如下所示:

public Node search_data_var2(Comparable searchable, Node node){
        if(node == null || node.getInfo() == null){
            return null;
        }
        else{
            if(node.getInfo().compareTo(searchable) == 0){
                return node;
            }
            else if(node.getInfo().compareTo(searchable) > 0 ){
                return search_data_var2(searchable, node.getLeft());
            }
            else{
                return search_data_var2(searchable, node.getRight());
            }
        }
    }
ltskdhd1

ltskdhd12#

出于查找目的,avl树与普通的二叉搜索树是相同的。
你的代码快到了!大多数情况下,你只需要添加 return 递归调用之前的关键字。
以下是我还将做的一些其他更改:
按照 java 的惯例, T 用于泛型类型。我会将节点重命名为更具描述性的名称(如 node ).
而不是检查引用的相等性( == ),我将使用 compareTo 方法,因为您正在使用 compareTo 不管怎样。这允许您在没有引用的情况下找到所需的值。
我会将null检查移到方法的顶部,以避免出现错误 NullPointerException .

public Node search_data_var2(Comparable searchable, Node node) {
    // If node is null, we've run off the end of the tree
    // Therefore, the value is not contained in the tree - return null
    if (node == null || node.getInfo() == null) {
        return null;
    }

    if (node.getInfo().compareTo(searchable) == 0) {
        // This node has info equal to the search condition - return it!
        return node;
    } else if (node.getInfo().compareTo(searchable) > 0) {
        // The sought value must be in the left subtree - start the search again there
        return search_data_var2(searchable, node.getLeft());
    } else if (node.getInfo().compareTo(searchable) < 0) {
        // The sought value must be in the right subtree - start the search again there
        return search_data_var2(searchable, node.getRight());
    }
}

相关问题