java 实现二叉搜索树 - 包含方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/26309481/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementing a Binary Search Tree - Contains method
提问by M0rty
I currently have 3 classes - DictionaryApp, BSTSet and BSTNode - both the BSTSet and BSTNode have contains methods.
我目前有 3 个类 - DictionaryApp、BSTSet 和 BSTNode - BSTSet 和 BSTNode 都有包含方法。
public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> {
// the root of the supporting binary search tree
private BSTNode<E> root;
// number of elements in the set
private int count = 0;
public boolean isEmpty() {
return count == 0;
}
public boolean contains(E item) throws ClassCastException {
if(root == null) return false;
return root.contains(item);
}
public boolean add(E item) {
if (item == null)
throw new IllegalArgumentException("Null cannot be added to a BSTSet");
if(contains(item))return false;
if(root == null){
root = new BSTNode(item);
count++;
return true;
}else{
root.add(item);
count++;
return true;
}
}
}
public class BSTNode <E extends Comparable<E>> {
private E value;
private BSTNode<E> left;
public BSTNode<E> right;
public BSTNode(E value) {
this.value = value;
}
public E getValue() {
return value;
}
public BSTNode<E> getLeft() {
return left;
}
public BSTNode<E> getRight() {
return right;
}
public boolean contains(E item) {
if(item.compareTo(value) == 0) return true;
if(left != null) left.contains(item);
if(right != null) right.contains(item);
// no matching node was found
return false;
}
public boolean add(E item) {
if(item.compareTo(value) < 0) {left = new BSTNode(item); return true;}
if(item.compareTo(value) > 0) {right = new BSTNode(item); return true;}
return false;
}
}
My issues is that the contains method in the BSTNode class never returns true and I can't understand why. If you would like to see anymore of my code or need anymore information please feel free to ask.
我的问题是 BSTNode 类中的 contains 方法永远不会返回 true，我不明白为什么。如果您想查看更多我的代码或需要更多信息，请随时询问。
回答by rgettman
In your BSTNode's containsmethod, you are ignoring the results of calling containson leftand right. If the child node found it, return trueimmediately. Also, use the result of the comparison to determine which child to search next.
在你BSTNode的contains方法，你都忽略调用的结果contains上left和right。如果子节点找到了，true立即返回。此外，使用比较结果来确定下一个要搜索的孩子。
public boolean contains(E item) {
int comp = item.compareTo(value);
if(comp == 0) return true;
if(comp < 0 && left != null && left.contains(item)) return true;
if(comp > 0 && right != null && right.contains(item)) return true;
// no matching node was found
return false;
}
Your addmethod ignores any child nodes that may already exist. Test for their presence first. If they don't exist, assign it as you are already doing. If they already exist, then call addrecursively on that child.
您的add方法会忽略可能已经存在的任何子节点。首先测试他们的存在。如果它们不存在，请像您已经在做的那样分配它。如果它们已经存在，则add递归调用那个孩子。
public boolean add(E item) {
if(item.compareTo(value) < 0) {
if (left == null) left = new BSTNode(item); return true;
else return left.add(item);
}
if(item.compareTo(value) > 0) {
if (right == null) right = new BSTNode(item); return true;
else return right.add(item);
}
return false;
}
