java使用递归搜索二叉树并检查它是否包含字符串

Question

我试图使用递归搜索二叉树，并根据二叉树是否包含字符串返回true或false。这是我的密码

public class BinaryTree {
private String data;
private BinaryTree leftChild;
private BinaryTree rightChild;

public BinaryTree() {
    data = null;
    leftChild = null;
    rightChild = null;
}

public BinaryTree(String d) {
    data = d;
    leftChild = new BinaryTree();
    rightChild = new BinaryTree();
}

// This constructor is unchanged
public BinaryTree(String d, BinaryTree left, BinaryTree right) {
    data = d;
    leftChild = left;
    rightChild = right;
}

// Get methods
public String getData() {
    return data;
}

public BinaryTree getLeftChild() {
    return leftChild;
}

public BinaryTree getRightChild() {
    return rightChild;
}

// Set methods
public void setData(String d) {
    data = d;
}

public void setLeftChild(BinaryTree left) {
    leftChild = left;
}

public void setRightChild(BinaryTree right) {
    rightChild = right;
}

 public boolean contains(String d) {
    return d != null && (this.getData().equals(d) ||
            contains(this.getLeftChild().getData()) ||
            contains(this.getRightChild().getData()));
}

所以，我的问题是contains方法，因为它一直给我一个stackoverflow。错误我希望我能提前得到这方面的帮助

Answer 1

你可以试试这个：

public boolean contains(String d)
{
  // Not contained if specified string is null
  if (d == null)
    return (false);

  // OK if specified string equals our data
  if ((data != null) && data.equals(d))
    return (true);

  // OK if contained in left tree
  if ((leftChild != null) && leftChild.contains(d))
    return (true);

  // OK if contained in right tree
  if ((rightChild != null) && rightChild.contains(d))
    return (true);

  // Otherwise, it's not OK
  return (false);

} // contains

Answer 2

在每次递归调用中this引用同一对象，因此您不断地反复传递相同的值。您需要将BinaryTree引用作为参数传递

private boolean contains(String data, BinaryTree node) {
    if (node == null) {
        return false;
    }

    return node.getData().equals(data) || contains(data, node.getLeftChild())
         || contains(data, node.getRightChild());

}

main（public）contains需要将要搜索的字符串和根传递给上述方法

Answer 3

你在那里做的不是递归。你在问：

boolean found = tree.contains(candidate)

对吧?

您的代码将其扩展为

boolean found = candidate != null && (tree.getData.equals(d) || LEFT || RIGHT)

左边是哪里

contains(tree.getLeftChild().getData())

它根本没有将候选字符串与左侧数据进行比较，而是扩展到

candidate != null && (tree.getData.equals(candidate) || LEFT || RIGHT)

这会导致无止境的循环，导致堆栈溢出

你应该把这门课改成

public class Node {
    Node left, right;
    String data
    public boolean contains(String d);
}

然后，您的树将成为根节点，搜索可以是递归的