时间戳

首页 > 解决方案 > 如何在 AVL 树中查找特定值并返回 Node

java - 如何在 AVL 树中查找特定值并返回 Node

问题描述

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

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

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

标签： javaalgorithmbinary-treeavl-tree

解决方案

出于查找目的，AVL 树与普通的二叉搜索树相同。

您的代码几乎就在那里！大多数情况下，您只需要return在递归调用之前添加关键字。

以下是我还将进行的其他一些更改：

  1. 按照 Java 中T的约定，用于泛型类型。我会将节点重命名为更具描述性的名称（例如node）。
  2. 我不会检查引用相等 ( ==)，而是使用该方法检查值相等，因为无论如何compareTo您都在使用。compareTo这使您无需参考即可找到所需的值。
  3. 我会将 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());
    }
}

推荐阅读