0

insert() を使用してバイナリ検索ツリーにデータを入力しようとしていますが、BST の内容を「印刷」するたびに、BST に挿入された最後の項目しか取得しません。すべての価値が BST に保持されるようにするには、何を修正する必要がありますか?

debuggin から、私の問題は、呼び出されるたびに public void insert() が新しい値を root に設定していることだと思います。私はそれを修正する方法がわかりませんか？

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

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

private class BinarySearchTreeNode<E>{
    public BinarySearchTreeNode<E> left, right;
    private E data;

    private BinarySearchTreeNode (E data) {
        this.data = data;
    }
}

private BinarySearchTreeNode<T> root;

public boolean isEmpty() {
    return root == null;
} 
private BinarySearchTreeNode<T> insert(T value, BinarySearchTreeNode<T> ptr) {
            if (ptr == null){ 
        ptr = new BinarySearchTreeNode<>(value); 
        return ptr; 
    }
    int compare = value.compareTo(ptr.data); //when ptr != null, this line and below should execute for each bstStrings.inster(x)
    /* pass the value (s1...sN) when compared to (ptr.data) to compare
     * when value and ptr.data == 0 re
     */
    if (compare == 0) {
        return ptr;
    }
    if (compare < 0) {
        while (ptr.left != null){
            ptr = ptr.left;
            if (ptr.left == null) {//found insertion point
                BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value);
                ptr = ptr.left;
                ptr = node;
                return ptr;
            }
        }
    }
    else {
        return insert(value, ptr.left);
    }
    if (compare > 0) {              
        if (ptr.right == null) {
            BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value);
            ptr = ptr.right;
            ptr = node;
            return ptr;
        } 
    }
    else {
        return insert(value, ptr.right);                    
    }
    return ptr;
}
public void insert(T value) {
    root = insert(value, root);  //****Where I believe the problem is******
} 
private void printTree(BinarySearchTreeNode<T>node){
    if(node != null){
        printTree(node.left);
        System.out.println(" " + node.data);
        printTree(node.right);
    }
}
public void printTree(){
    printTree(root);
    System.out.println();
}    
}

追加のコンテキストについては、ここに私の Main() を示します。ここで、insert() を呼び出して、文字列を BST に挿入しようとしています。

public class Main {

public static void main(String[] args) {

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

    String s = "Hello";
    String s1 = "World";
    String s2 = "This Morning";
    String s3 = "It's";

    bstStrings.insert(s);
    bstStrings.insert(s1);
    bstStrings.insert(s2);
    bstStrings.insert(s3);   //the only inserted value that is printed below

    bstStrings.printTree();

        System.out.println();
        System.out.println("You should have values above this line!");
}
}

最後に私のコンソール出力:

It's


You should have values above this line!
4

1 に答える 1

4

いくつかのヒント:

  • 内部に再帰呼び出しは見られませんinsert。適切な再帰呼び出しを行わずに (値に基づいて現在のノードの左または右のサブツリーに) BST をどのようにトラバースしますか? これらの呼び出しを実行するように見えるコメントアウトされたコードがいくつか見られます。なぜコメントアウトされているのですか？
  • 新しく挿入されたノードを返し、これを として設定しrootます。これにより、 が毎回root新しいノードを指すように設定されます。私はそれがあなたが望むものだとは思わない。
  • ツリーが空であるという特殊なケースを処理しようとしている場合rootはnull、 is かどうかを確認してから、新しいノードをそれに設定するだけです。
  • 本当に返す必要はありませんptr。BST は への参照を保持しているためroot、常にツリーのルートへの参照があります。挿入するたびに、 から開始しroot、新しいノードを挿入する適切な場所が見つかるまでツリーを再帰的にトラバースします。本当に参照を返す必要がある場合は、rootその新しいノードに設定しないでください。

ここにあなたを助けるためのいくつかの疑似コードがあります:

// Recursive function that inserts a value into a BST
function insert(node, value):

    //Handles the case where you have no nodes in the tree, so root is null
    if node is null:
        node = new Node(value)

    // If the value is lesser than the current node's value, we need to insert it
    // somewhere in the right subtree
    else if value < node.value:
        if node.right is null:
           // This node doesn't have a right child, so let's insert the new node here
           node.right = new Node(value)
        else:
           // This node has a right child, so let's go further into this subtree to
           // find the right place to insert the new node
           insert(node.right, value)

    // If the value is greater than the current node's value, we need to insert it
    // somewhere in the left subtree
    else if value > node.value:
        if node.left is null:
           // This node doesn't have a left child, so let's insert the new node here
           node.left = new Node(value)
        else:
           // This node has a left child, so let's go further into this subtree to 
           // find the right place to insert the new node
           insert(node.left, value)
    else:
        // A node with this value already exists so let's print out an erro
        error("Node with that value already exists")

end function
于 2013-03-13T16:34:56.447 に答える