1

我正在尝试创建一种方法，该方法允许我检查 BST 是否包含项目。这是我到目前为止所拥有的：

public boolean contains(Object item) {
    // YOUR CODE HERE

    //changes item to E so it can be used in the comparator
    E value1 = (E) item;

    if (root.value.equals(item)){
        return true;
    }

    comp.compare(value1,root.value);
    if(value1<root.value){
        if (left == null)
            return null;
        else
            return left.contains(item);
    }

    else if(item >= value){
        if (right == null)
            return null;
        else
            return right.contains(item);
    }
}

这些是我的领域：

// Data fields
private BSTNode root;
private int count = 0;
private Comparator<E> comp;   // default comparator

/** Private class for the nodes.
 *  Has public fields so methods in BSTSet can access fields directly. 
 */
private class BSTNode {

    // Data fields

    public E value;
    public BSTNode left = null;
    public BSTNode right = null;

    // Constructor

    public BSTNode(E v) {
        value = v;
    }

}


public BSTSet() {
    comp = new ComparableComparator();      // Declared below
}

public BSTSet(Comparator <E> c) {
    comp = c;
}

我的问题是如何修复我的 contains 方法以使其正常工作。到目前为止，它到达了 comp.compare(value1.root.value)) 下的行，并说 '<' 不能用于 E 类型的两个元素。我该如何解决这个问题，以便我可以继续运行比较器？

4

2 回答 2

3

您的比较器返回一个 int。

如果这个int为0，那么两个对象的值是一样的，如果小于0，就等价于你的<，如果大于0，就等价于你的>。

您需要使用比较器调用的结果来检查是否应该遍历右子树或左子树。

另外，如果左/右分支为null，请不要返回null，返回false。这是算法的正确语义，如果没有左分支并且值小于当前根，则该项目不在树中，因此为假。

于 2012-10-08T11:44:01.433 回答
0

你可以有如下的东西：

public boolean containsItem(int i) {
    Node<Integer> t = new Node<Integer>(i);
    Node<Integer> r = (Node<Integer>) root;
    while(r != null){
        int cmp = t.compareTo((Node<Integer>) r);
        if(cmp == 0)
            return true;
        if(cmp >0 ) r = r.getRight();
        else r = r.getLeft();
    }
    return false;
}

您可以查看我的博客，了解如何为BST实现 compareTo 方法。

于 2014-04-20T11:21:36.647 回答