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 の 2 つの要素では使用できないと述べています。これを修正して、引き続きコンパレーターを実行できるようにするにはどうすればよいですか?

4

2 に答える 2

3

コンパレータは int を返します。

この int が 0 の場合、両方のオブジェクトの値は同じです。0 未満の場合は < に相当し、0 より大きい場合は > に相当します。

右側または左側のサブツリーをトラバースする必要があるかどうかを確認するには、コンパレータ呼び出しの結果を使用する必要があります。

また、左右の分岐が null の場合は null を返さず、false を返してください。これはアルゴリズムの正しいセマンティクスです。左の分岐がなく、値が現在のルートよりも小さい場合、項目がツリーにないため、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 に答える