2

Binary Search Tree で小さな Java 作業を行っていますが、ノードの再帰的な挿入をツリーに実装して表示すると、何も得られません。私はしばらくそれを続けてきましたが、確かなことはわかりませんが、参照渡しの問題だと思います。

これが私のコードです：

public class BST {

    private BSTNode root; 

    public BST() {
        root = null;
    }

    public BSTNode getRoot() {
        return root;
    }

    public void insertR( BSTNode root, Comparable elem ) {

        if ( root == null ) {
            root = new BSTNode( elem );
        }
        else {
            if ( elem.compareTo( root.element ) < 0 ) {
                insertR( root.left, elem );
            } else {
                insertR( root.right, elem );
            }
        }

    }

    public void printInOrder (BSTNode root) {
        if (root != null) {

            printInOrder(root.left);
            System.out.println(root.element);
            printInOrder(root.right);

        }
    }
}

class BSTNode {

    protected Comparable element;
    protected BSTNode left;
    protected BSTNode right;

    protected BSTNode ( Comparable elem ) {

        element = elem;
        left = null;
        right = null;

    }

}

ルートが挿入先のノードであり、elem が文字列である一連の insertR を実行しましたが、ツリーがまったく入力されていないかのように、何も出力されません。再帰挿入に問題があると確信していますが、どこにあるのかわかりません。不可能だと思われるものを何も返さない再帰挿入メソッドを使用する必要があります。

どんな助けでも素晴らしいでしょう。

4

3 に答える 3

2

BSTNodes の左右の要素が null です。挿入する前にそれらを作成する必要があります。それ以外の場合、空のぶら下がっている BSTNode() を作成して挿入し、ツリーの残りの部分には接続しません。

ラインを変えることができ、

            if ( elem.compareTo( root.element ) < 0 ) {
                insertR( root.left, elem );
            } else {
                insertR( root.right, elem );
            }

に

 if ( elem.compareTo( root.element ) < 0 ) {
        if ( root.left == null )
             root.left = new BSTNode( elem );
        else
            insertR( root.left, elem );
    } else {
        if ( root.right == null )
             root.right = new BSTNode( elem );
        else
             insertR( root.right, elem );
    }
于 2012-12-06T04:24:35.410 に答える
0

これにより、BSTルートが設定され、クラスが正しく機能し、変更できるようになります。

    if ( root == null ) {
        root = new BSTNode( elem );
    }

に

    if ( root == null ) {
        root = new BSTNode( elem );
        if ( root.element != null ) {
            this.root = root;
        }
    }
于 2012-12-06T05:33:03.697 に答える