3

学校のプロジェクトでは、BSTツリーがあり、ツリーからのすべてのintをBSTarrayと呼ばれるint配列に配置する必要があります。
これは私がこれまでに持っているものです:

public int [] toBSTArray() {
    int size = 20;
    int [] BSTarray = new int [size];
    for(int i = 0; i <size; i++) {
        makeArray(root);
        BSTarray[i] = root.getValue();
}

    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node) {
    if (node != null) {
        makeArray(node.getLeft());
        makeArray(node.getRight());
        // System.out.print(node.getValue() + " ");
    }
}

このメソッドはツリーを調べて、見つけた値を BSTarray のさまざまなインデックスに追加するものだと思っていましたが、配列内のすべてのインデックスに同じ数値を追加しているだけです。再帰で何か間違っていますか？

4

2 に答える 2

6

これを試して：

Integer[] values = extractValues(n).toArray(new Integer[] {});

そのメソッド定義で：

private static List<Integer> extractValues(Node n) {
    List<Integer> result = new ArrayList<>();
    if (n.getLeft() != null) {
        result.addAll(extractValues(n.getLeft()));
    }

    if (n.getRight() != null) {
        result.addAll(extractValues(n.getRight()));
    }

    result.add(n.getValue());

    return result;
}

あなたに似たノード構造を想定しました。もちろん、静的な方法で使用しない場合、メソッドは静的である必要はありません。

リスト変換のため、この方法は最も効率的ではないかもしれませんが、配列のサイズを気にする必要はありません。関数が配列を返す必要がある場合は、それを別の関数にラップするか、提案された関数が配列を返すようにします (これにより、各戻り値の前にリストを配列に変換する必要があります)。

コードに関しては、配列全体を埋めるために を反復処理しますiが (サイズがどこからわかっていても)、値は常にルート ノードの値に設定します。だからこそ、常に同じ価値観を持っています。関数は自分makeArray自身を再帰的に呼び出しますが、何もしません (sysout ステートメントを追加しても ;) )

アップデート：

また、リストを使用しないという制約のために、配列のみを使用する別のバージョンを次に示します。

int size = 20;
int[] results = new int[size];
extractValues(n, results, 0);

メソッド定義で：

private static int extractValues(Node n, int[] results, int index) {
    if (n.getLeft() != null) {
        index = extractValues(n.getLeft(), results, index);
    }

    if (n.getRight() != null) {
        index = extractValues(n.getRight(), results, index);
    }

    results[index] = n.getValue();

    return index + 1;
}

結果が になることに注意してくださいresults。サイズは、ノードの数よりも大きいと想定するか、事前にツリーをたどってカウントする必要があります。

于 2012-12-13T23:24:27.067 に答える
3

これはどうですか：（再帰は配列に変更を加えません）

public int [] toBSTArray() {
    int size = 20; //ASSUMING THIS IS LESS THAN OR EQUAL TO NUMBER OF NODES IN THE TREE
    int [] BSTarray = new int [size];
    makeArray(root, 0, BSTarray);
    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node, int i, int [] BSTarray ) {
    if (node != null) {
        BSTarray[i] = root.getValue();   
        makeArray(node.getLeft(), 2*i+1, BSTarray);
        makeArray(node.getRight(), 2*i+2, BSTarray);
   }
}
于 2012-12-13T23:53:08.287 に答える