如何在 AVL 树和 return 节点中查找特定值

Question

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

我需要创建一个方法来查找具有特定值“可搜索”的节点，并且 returns 节点“T”，当它包含它时。如果这样的值不存在，函数应该 return "null"。但是我遇到了麻烦，不知道如何用一种方法实现这一点。上面的函数是我写的。问题是该方法不能 return Node 和 null 以相同的方式。

不禁止使用外部函数来实现，但目前我不知道如何实现。

Answer 1

The problem is that the method can't return Node and null in the same way.

可以，但您需要调整代码以适应

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

return 将由 search_data_var2 递归方法调用 return 编辑的值。顺便说一句，你不应该使用 T 作为变量名，通常这样的名称（即，一个大写字母）用于泛型类型。此外，您应该使用 compareTo 方法（即 T.getInfo().compareTo(searchable) == 0）而不是 ==。

最后，您的代码可能会抛出 NPE，因为您首先要检查

if(T.getInfo()==searchable)

在实际检查 T.getInfo() 是否为 null 或 T 是否为 null 本身之前。因此，您需要重新排列条件，如下所示：

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

Answer 2

出于查找目的，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());
    }
}

如何在 AVL 树和 return 节点中查找特定值

How to find a specific value in the AVL tree and return the Node

java

algorithm

binary-tree

avl-tree