Java使用递归返回布尔值true

发布时间：2020-12-15 04:48:10 所属栏目：Java 来源：网络整理

导读：我试图看看我的二进制搜索树中是否包含一个值,并且我使用递归遍历树.问题是函数返回false作为调用堆栈上的最后一个值而不是true. 这是伪代码： public boolean containsValue(Node node,Value v) { if (node.value.equals(v)) { return true; } containsValu

我试图看看我的二进制搜索树中是否包含一个值,并且我使用递归遍历树.问题是函数返回false作为调用堆栈上的最后一个值而不是true.

这是伪代码：

public boolean containsValue(Node node,Value v) {

   if (node.value.equals(v)) {
     return true;
   } 
   containsValue(node.left,v); // <- search left tree
   containsValue(node.right,v); // <- search right tree

   return false;
}

这总是返回false.

但是我不能这样做,因为第二个return语句是死代码：

return containsValue(node.left,v);
 return containsValue(node.left,v);

那么我该如何解决这个问题呢？

解决方法

你去吧

public boolean containsValue(Node node,Value value){
    int result = node.value.compareTo(value);
    if(result == 0){
        return true;
    }else if(result < 0){
        if(node.left != null){
            return containsValue(node.left,v);
        }
        return false;
    }else{
        if(node.right != null){
            return containsValue(node.right,v);
        }
        return false;
    }
}

这将检查当前节点的值与参数值的比较方式.如果参数值较小,则返回左子项的结果(< 0),如果它们相同则返回true(== 0),如果pass by value较大则返回右子项的结果(大于0).这将继续,直到找到值或需要搜索的子项为空. 这种方法充分利用了二叉搜索树,因为它不检查所有变量并且平均效率为O(log(n)),而只是查看所有节点的平均效率为O(n),这是最差的. 边注：
获取具有该值的节点的方法基本上与您用node替换true,false替换为null,使用布尔替换Node

例：

public Node getNode(Node node,Value value){
    int result = node.value.compareTo(value);
    if(result == 0){
        return node;
    }else if(result < 0){
        if(node.left != null){
            return containsValue(node.left,v);
        }
        return null;
    }else{
        if(node.right != null){
            return containsValue(node.right,v);
        }
        return null;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!