0

辞書順でソートされた 2 つの int 値と 1 つの文字列値を含むバイナリ ツリーを作成しようとしていますが、どうすればよいかわかりません。すでにソートされている配列リストを作成しましたが、バイナリツリーはソートされていない参照ベースでなければならず、作成中にリストをソートすることを考えています。誰でもこれを手伝うことができますか？簡単なアイデアをいただければ幸いです。

4

3 に答える 3

2

二分木は再帰的なものです。他の 2 つの BinaryTree (デフォルトでは null) への 2 つの参照を持つ BinaryTree というクラスを作成します (C++、.NET、または Java を使用していることを願っています)。次に、再帰的な挿入関数を作成します。

何を達成しようとしているのかはわかりませんが、バイナリ ツリーを構築する場合、通常、配列はどこにも見つかりません。

于 2010-06-04T13:14:35.783 に答える
0

2 つの int 値と文字列を格納するためのデータ構造が既にあるようです (配列リストでソートされているため)。このデータ構造を「ツリー ノード」に含めることができます。通常、ノードには、親ノード (ルート ノードでない場合) と 2 つの子ノードへの参照ポインターがあります。

ツリーをソートしたいので、実際に求めているのは、ヒープと呼ばれる特別な形式のバイナリ ツリーです。以下のバイナリ ヒープ ウィキペディア ページへのリンクには、バイナリ ヒープをソートする方法を示すアルゴリズムがあります。

http://en.wikipedia.org/wiki/Binary_heap

ヒープとツリーに関する一般的な情報を次に示します。

http://en.wikipedia.org/wiki/Binary_tree

http://en.wikipedia.org/wiki/Heap_(データ構造)

編集:データをツリー形式で保存するために、リテラル ツリー構造を使用する必要はありません。配列を使用してツリーを構築することはまったく問題ありません。参照ポインター (親ノードと 1 つまたは 2 つの子ノード) を使用する代わりに、配列へのインデックスを計算できます。子の各セットは、ツリー内の「行」と見なされます。ルート要素はゼロ行にあります。最前列に子供が2人います。ルートの子の子は 2 行目にあり、以下同様です。

このパターンを使用すると、array[2*n+1] および array[2*n+2] を使用して任意のノードの子を見つけることができます。n は親ノードの行です。任意のノードの親は、array[floor( (n-1)/2)] を使用して見つけることができます。

于 2010-06-04T13:15:44.617 に答える
0

まず、データを格納するクラスを作成しComparable、Comparator.

public class Data { // Implement Comparable...
    private String s;
    private int n1;
    private int n2;

    // Implement constructors, getters, setters based on what you need...

    // Implement compareTo (+ equals + hashCode) unless your going with Comparator
}

次に、データを格納するCollectionために実装する a を使用しSortedSetます。TreeSet は適切な選択です。のオブジェクトはSortedSet参照によって保存されるため、ローカル変数に設定された値を変更すると、コレクションでも変更されます。

編集：参照ベースのリストに関するあなたの質問を正しく理解していれば、Javaで次のことが可能です。

List<Data> dataList = // Create list and add data into it.
Data data = dataList.get(4);
data.setS(103); // Modifies S in the local data-object and in dataList because they are reference based.
于 2010-06-04T13:33:03.433 に答える