[解決済み] バイナリサーチツリーの実装 - Containsメソッド

質問

現在、DictionaryApp、BSTSet、BSTNodeの3つのクラスがあり、BSTSetとBSTNodeの両方がcontainsメソッドを持っています。

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

私の問題は、BSTNodeクラスのcontainsメソッドが決してtrueを返さないことで、その理由が理解できません。もし、私のコードをもっと見たい、あるいはもっと情報が必要であれば、遠慮なく質問してください。

解決方法は？

あなたの BSTNode 's 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;
}

あなたの 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;
}