1

わかりましたので、現在、各ノードにオブジェクトへの参照、左の子への参照、右の子への参照 (全部で 3 つの変数) を含む二分探索木を作成しようとしています。左の子は常に親よりも小さくなければならず、右の子は常に親よりも大きくなければなりません。2 つのメソッドを作成する必要があります。1 つのメソッド ( contains()) は要素がツリー内にあるかどうかをチェックし、もう 1 つのメソッドは要素をツリー内の適切な場所に追加します。

BinarySearchTree クラスは次のとおりです。

public class BinarySearchTree extends BinaryTree {

public BinarySearchTree(TreeNode t){
    super(t);
}

public boolean contains (Comparable obj){
    if (this.myRoot != null){
        return containshelper(obj, this.myRoot);
    }
    return false;

}

public static boolean containshelper(Comparable comp, TreeNode t){
    boolean flag = true;
    int x = comp.compareTo(t.myItem);
    if (x < 0 && t.myLeft != null){
        containshelper(comp,t.myLeft);
    }
    if (x > 0 && t.myRight != null){
        containshelper(comp,t.myRight);
    }
    if (x == 0){
        return true;
    }
    return false;
}


public void add(Comparable key) {
    if (!this.contains(key)){
        if (this.myRoot != null){
            add(myRoot, key);
        }
        System.out.print("Getting Here ");
    }
    else {
        System.out.print("Tree already contains item");
    }
}

private static TreeNode add(TreeNode t, Comparable key) {

    if (((Comparable) t.myItem).compareTo(key) < 0 && t.myLeft != null){
        add(t.myLeft,key);

    }
    if(((Comparable) t.myItem).compareTo(key) > 0 && t.myRight != null ) {
        add(t.myRight,key);

    }
    if (((Comparable) t.myItem).compareTo(key) < 0 && t.myLeft == null){
        TreeNode q = new TreeNode(key);
        t.myLeft = q;

    }
    if (((Comparable) t.myItem).compareTo(key) > 0 && t.myRight == null ){
        TreeNode w = new TreeNode(key);
        t.myRight = w;

    }
    return t;
}
}

次に、TreeNode クラス (BinaryTree に含まれる) を示します。

    public static class TreeNode {

    public Object myItem;
    public TreeNode myLeft;
    public TreeNode myRight;
    public int size;

    public TreeNode (Object obj) {
        size = size(this);
        myItem = obj;
        myLeft = myRight = null;
    }
    public int size(TreeNode t) { 
        return(sizehelper(t)); 
    }
    private int sizehelper(TreeNode node) { 
        if (node == null){ 
            return(0); 
        }
        else { 
            return(size(node.myLeft) + 1 + size(node.myRight)); 
        } 
    }


    public TreeNode (Object obj, TreeNode left, TreeNode right) {
        myItem = obj;
        myLeft = left;
        myRight = right;
    }
}
}

私のcontains（）メソッドが機能すると確信していますが、私の人生では、なぜadd（）が機能しないのかわかりません。どんな助けでも大歓迎です。

4

1 に答える 1

0

あなたはいくつかの間違いを持っ​​ていますcontainsHelper

public static boolean containshelper(Comparable comp, TreeNode t){

    // TreeNode.myItem should be declared of type `Comparable` instead of `Object`
    int x = comp.compareTo(t.myItem);
    if (x < 0 && t.myLeft != null){
        return containshelper(comp,t.myLeft); // where does result of this call go? We must return the result !!
    }
    if (x > 0 && t.myRight != null){
        return containshelper(comp,t.myRight); // this too ?
    }
    if (x == 0){
        return true;
    }
    return false;
}

ここでも同じ間違い：

private static TreeNode add(TreeNode t, Comparable key) {

if (t.myItem.compareTo(key) < 0 && t.myLeft != null){
    t = add(t.myLeft,key); // where does returned result go?
}
else if (t.myItem.compareTo(key) > 0 && t.myRight != null ) {
    t = add(t.myRight,key);
}
else if (t.myItem.compareTo(key) < 0 && t.myLeft == null){
    TreeNode q = new TreeNode(key);
    t.myLeft = q;
}
else if (t.myItem.compareTo(key) > 0 && t.myRight == null ){
    TreeNode w = new TreeNode(key);
    t.myRight = w;
}
return t;
}

TreeNode.myItemタイプを宣言しComparableて、すべてのクラスがバイナリ検索に適合してcompareToメソッドを提供するように強制する必要があります。Comparableオブジェクトが実装されていない可能性がComparableあり、ランタイムエラーが発生するため、これはオブジェクトをにキャストするよりも優れています。

于 2012-07-19T04:41:12.893 に答える