4

要するに、私は二分木をディスク（一般的な木、必ずしもBSTではない）に保存するための洗練された方法を学び/開発したいと思います。これが私の問題の説明です：

「二十の質問」のゲームを実装しています。内部ノードが質問で、葉が回答である二分木を作成しました。ノードの左側の子は、誰かが現在の質問に「はい」と答えた場合にたどるパスであり、右側の子は「いいえ」の答えです。これは二分探索木ではなく、左の子が「はい」で右の子が「いいえ」の二分木であることに注意してください。

プログラムは、ユーザーに自分の答えをコンピューターが考えていたものと区別するように求めることによって、nullの葉に遭遇した場合に、ツリーにノードを追加します。

ユーザーがプレイするとツリーが構築されるため、これは適切です。きちんとしていないのは、ツリーをディスクに保存する良い方法がないということです。

ツリーを配列表現として保存することを考えました（ノードiの場合、左の子は2i + 1、右の2i + 2、親の場合は（i-1）/ 2）が、クリーンではなく、最終的には無駄なスペースがたくさん。

スパースバイナリツリーをディスクに保存するためのエレガントなソリューションのアイデアはありますか？

4

8 に答える 8

9

レベル順のトラバーサルを行います。つまり、基本的に幅優先探索アルゴリズムを実行しているということです。

あなたが持っている：

  1. ルート要素が挿入されたキューを作成する
  2. キューから要素を取り出し、それを E と呼ぶ
  3. E の左右の子をキューに追加します。左または右がない場合は、null ノード表現を配置します。
  4. ノード E をディスクに書き込みます。
  5. 手順 2 から繰り返します。

代替テキスト

レベル順走査シーケンス: F、B、G、A、D、I、C、E、H

ディスクに保存するもの: F、B、G、A、D、NullNode、I、NullNode、NullNode、C、E、H、NullNode

ディスクからロードするのはさらに簡単です。ディスクに保存したノードを左から右に読み取るだけです。これにより、各レベルの左右のノードが得られます。つまり、ツリーは上から下、左から右に塗りつぶされます。

ステップ 1 読み取り:

F

ステップ 2 読み込み:

  F 
B

ステップ 3 読み込み:

  F 
 B  G

ステップ 4 読み込み:

   F 
 B  G
A

等々 ...

注: NULL ノード表現を取得したら、その子をディスクにリストする必要はなくなります。ロードバックするときは、次のノードにスキップする必要があることがわかります。したがって、非常に深いツリーの場合でも、このソリューションは効率的です。

于 2008-12-03T16:55:20.143 に答える
9

再帰的に保存できます：

 void encodeState(OutputStream out,Node n) {
        if(n==null) {
            out.write("[null]");
        } else {
           out.write("{");
           out.write(n.nodeDetails());
           encodeState(out, n.yesNode());
           encodeState(out, n.noNode());
           out.write("}");
        }
  }

テキストの少ない独自の出力形式を考案します。結果の出力を読み取る方法を説明する必要はないと確信しています。

これが深さ優先トラバーサルです。幅優先も機能します。

于 2008-12-03T17:11:50.173 に答える
1

これを実現する簡単な方法は、各要素を出力するツリーをトラバースすることです。次に、ツリーをロードして戻すには、リストを反復処理して、各要素をツリーに挿入し直します。ツリーのバランスが自己調整されていない場合は、最終的なツリーのバランスが適切になるようにリストの順序を変更することをお勧めします。

于 2008-12-03T17:06:54.597 に答える
1

洗練されているかどうかはわかりませんが、シンプルで説明できます: 幹であれ葉であれ、各ノードに一意の ID を割り当てます。単純なカウント整数で十分です。

ディスクに保存するときは、ツリーをトラバースして、各ノード ID、「はい」のリンク ID、「いいえ」のリンク ID、および質問または回答のテキストを格納します。null リンクの場合、null 値としてゼロを使用します。質問か回答かを示すフラグを追加するか、より簡単に、両方のリンクが null かどうかを確認することができます。次のようなものを取得する必要があります。

1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"

連続整数アプローチを使用する場合、ここに示すように、ノードの ID を保存することは冗長になる可能性があることに注意してください。ID順に並べればいいだけです。

ディスクから復元するには、行を読み取り、それをツリーに追加します。おそらく、前方参照ノードを保持するためにテーブルまたは配列が必要になるでしょう。たとえば、ノード 1 を処理する場合、それらの値を入力できるようになるまで、ノード 2 と 3 を追跡する必要があります。

于 2008-12-03T17:23:35.157 に答える
0

Javaでは、クラスをシリアル化可能にする場合は、クラスオブジェクトをディスクに書き込み、入出力ストリームを使用して読み戻すことができます。

于 2009-12-09T05:54:33.557 に答える
0

ツリーを次のように保存します。

<node identifier>
node data
[<yes child identfier>
  yes child]
[<no child identifier>
  no child]
<end of node identifier>

ここで、子ノードは上記の再帰的なインスタンスにすぎません。[] 内のビットはオプションで、4 つの識別子は単なる定数/列挙値です。

于 2008-12-03T17:09:34.030 に答える
0

最も任意の単純な方法は、任意のグラフを表すために使用できる単なる基本的な形式です。

<parent>,<relation>,<child>

すなわち:

"Is it Red", "yes", "does it have wings" 
"Is it Red", "no" , "does it swim"

ここにはあまり冗長性はなく、フォーマットはほとんど人間が読めるものであり、唯一のデータの重複は、直接の子ごとに親のコピーが必要なことです。

本当に注意しなければならない唯一のことは、誤ってサイクルを生成しないことです;)

それがあなたが望むものでない限り。

ここでの問題は、後でツリーを再構築することです。最初の行を読んで「翼はありますか」オブジェクトを作成した場合、後で「翼がありますか」、「はい」、「くちばしはありますか?」という行に出くわしたときに、どうにかしてその位置を特定する必要があります。

これが、私が伝統的にメモリ内のグラフ構造を使用して、ポインターがどこにでも移動するようなことをする理由です。

[0x1111111 "Is It Red"           => [ 'yes' => 0xF752347 , 'no' => 0xFF6F664 ], 
 0xF752347 "does it have wings"  => [ 'yes' => 0xFFFFFFF , 'no' => 0x2222222 ], 
 0xFF6F664 "does it swim"        => [ 'yes' => "I Dont KNOW :( " , ... etc etc ]

その場合、「子/親」接続は単なるメタデータです。

于 2008-12-03T17:12:05.460 に答える