0

私はここ数日、バイナリ検索ツリーの実装をプラグインしていて、「insert（）」を使用してルートにデータが入力されていることがわかりました（デバッグすると、これを確認できます。 Eclipseを使用）。他のノードがツリーに追加されないのはなぜですか？

これが私のBSTクラスです：

package binarySearchTree;

public class BinarySearchTree<T extends Comparable<T>> {

@SuppressWarnings("hiding")
private class BinarySearchTreeNode<T>{
    public BinarySearchTreeNode left, right;
    private T data; //LINE 8

    private BinarySearchTreeNode (T data,BinarySearchTreeNode left, BinarySearchTreeNode right ) {
        this.left = left;
        this.right = right;
        this.data = data;
    }
}
private BinarySearchTreeNode<T> root;

@SuppressWarnings("unused")
private T search(T target, BinarySearchTreeNode<T> ptr) {
    //find target in subtree A ptr
    if (root == null || ptr == null) {
        return root; //target is not in tree
    }
    int compare = target.compareTo(ptr.data); //compareTo(ptr.data);
    if (compare == 0) {
        return ptr.data; //target is found
    }
    if (compare < 0) {
        return search(target, ptr.left);
    }
    if (compare > 0) {
        return search(target, ptr.right);
    }
    return target;
}
public T search(T target) {
    return search(target);
}
public boolean isEmpty() {
    return root == null;
} 
/* To insert a data into a BST, 1st search for the data, 
 * if the data is found = duplicate data error
 * if the data is NOT found = a null pointer
 * Make this null pointer point to a NewNode holding data
 * new values go into the BST as leaves
 * Using public boolean insert (T node) & 
 * private boolean insert (T Node, BSTNode<T> ptr) as a recursive method
 */
@SuppressWarnings("unchecked")
private boolean insert(T value, BinarySearchTreeNode<T> ptr) {
    //T data = null;
    //insert data in a child of ptr, return false if duplicate is found
    //Precondition: ptr must not be null
    int compare = value.compareTo(ptr.data); //LINE 55
    if (compare == 0) {
        return false;
    }
    if (compare < 0) {
        if (ptr.left == null) {
            //found insertion point
            BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value, null, null);
            ptr.left.data = node; //insert data in new node
            return true;
        } 
    } else {
        return insert(value, ptr.left); //LINE 67
    }
    if (compare > 0) {
        if (ptr.right == null) {
            BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value, null, null);
            ptr.right.data = node;
            return true;
        } else {
            return insert(value, ptr.right);                    
        }
    }
    return false;
}
public boolean insert(T value) {     
    if (isEmpty()) {              
        root = new BinarySearchTreeNode<T>(value, null, null);  
        return true;  
    }
    return insert(value, root); // LINE 85  
} 
}

これが私のMain（）です。最終的には、コンソールにBSTの値を出力したいのですが、最初に、それらをツリーに追加する必要があることがわかります。

package binarySearchTree;

パブリッククラスメイン{

public static void main(String[] args) {


    BinarySearchTree<String> bstStrings = new BinarySearchTree<String>();

    String s = "Hello";
    String s1 = "World";
    //String s2 = "This Morning";

    bstStrings.insert(s);
    bstStrings.insert(s1); //LINE 15
    //bstStrings.insert(s2);

    while (true){
        if (!bstStrings.isEmpty()){
            System.out.println(bstStrings + " ");
        }
        System.out.println();
        System.out.println("You should have values above this line!");break;
    }   
}
}
4

2 に答える 2

2

その結果、ルートのサブツリーに値を保存していませんroot。 これを 置き換えます:BinarySearchTree<T>T


return insert((T) value, node);

return insert((T) value, root);

コードを次のように置き換えます。 

public boolean insert(T value) {     
    if (isEmpty()) {              
        root = new BinarySearchTreeNode((T) value, null, null);  
        return true;  
    }
    return insert((T) value, root); // start recursion  
}

そうしないと、ツリーがなく、ノードが互いにリンクされません

更新:である最初の比較でルートの左の子
を渡すため、NPE を取得します。 あなたは戻ってはいけませんが。 あなたの方法は次のとおりです。 insertnull
booleanBinarySearchTreeNode

@SuppressWarnings("unchecked")
private BinarySearchTreeNode<T> insert(T value, BinarySearchTreeNode<T> ptr) {  
   if(ptr == null){  
        ptr = new BinarySearchTreeNode<T>(value,null,null);  
        return ptr;  
    }  
    //your code next but return the `ptr`  
}

次に、挿入で次のことを行う必要があります。 

public void insert(T value) {     

    root = insert(value, root); 
}
于 2013-03-12T18:05:37.463 に答える
0

最初の挿入後、新しいノードを作成しますが、何もしません。

于 2013-03-12T18:06:35.747 に答える