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

Question

我正在尝试使用递归来搜索二叉树并根据二叉树是否包含字符串返回真或假。这是我的代码

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

所以，我的问题在于包含方法，因为它一直给我一个堆栈溢出错误。我希望我能提前得到这方面的帮助。

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

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

boolean found = tree.contains(candidate)

右？

您的代码将其扩展为

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

其中 LEFT 是

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

然后你的树将是一个根节点，搜索可能是递归的。

Answer 3

在每次递归调用中，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());
}

主(公共)contains需要将要搜索的字符串和根传递给上述方法。