时间戳

首页 > 解决方案 > 如何编写一个函数来检查给定的二叉搜索树是否包含给定的值？

java - 如何编写一个函数来检查给定的二叉搜索树是否包含给定的值？

问题描述

例如，对于以下树：

n1（值：1，左：null，右：null） n2（值：2，左：n1，右：n3） n3（值：3，左：null，右：null）调用 contains(n2, 3)应该返回 true，因为根在 n2 的树包含数字 3。

我是编程新手，并试图解决理解编程概念的挑战。这不是家庭作业问题。

我已经编写了下面的代码，但它总是返回 false。

class Node {
   public int value;
   public Node left, right;

   public Node(int value, Node left, Node right) {
     this.value = value;
     this.left = left;
     this.right = right;
   }
  }

 public class BinaryTree {

   public static boolean contains(Node root, int value){
        if(root == null) return false;
        else
            return
                    contains(root.left, value) ||
                    contains(root.right, value);
    }

  public static void main(String[] args) {

        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        System.out.println(contains(n2,3));
    }
 }

标签： javarecursionbinary-tree

解决方案

如果节点上的值对应于您搜索的值，您将错过检查。因此，您基本上总是返回 false，因为在某一时刻 root 将等于 null。为避免这种情况，您需要一个 else if 子句，在该子句中检查节点的值和搜索的值，如果这两者相等则返回 true。

public static boolean contains(Node root, int value){
    if(root == null) return false;
    else if (root.value==value) return true;
    else
        return
                contains(root.left, value) ||contains(root.right, value);
}

推荐阅读