「20の質問」ゲームのためにバイナリツリーをディスクに保存したい

StackOverflow https://stackoverflow.com/questions/337868

質問

要するに、私はバイナリツリーをディスク（一般的なツリー、必ずしもBSTではない）に保存するためのエレガントな方法を学び/開発したいと思います。これが私の問題の説明です：

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

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

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

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

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

役に立ちましたか？

解決

再帰的に保存できます： ジェネラコディセタグプレ

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

これは深さ優先探索です。幅優先も機能します。

他のヒント

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

あなたが持っているもの：

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

    alt text

    レベル順トラバーサルシーケンス：F、B、G、A、D、I、C、E、H

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

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

    ステップ1の読み込み： ジェネラコディセタグプレ

    ステップ2の読み込み： ジェネラコディセタグプレ

    ステップ3の読み込み： ジェネラコディセタグプレ

    ステップ4の読み込み： ジェネラコディセタグプレ

    など...

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

これを実現する簡単な方法は、ツリーをトラバースして各要素を出力することです。次に、ツリーを再度ロードするには、リストを繰り返し処理して、各要素をツリーに挿入し直します。ツリーが自己バランスをとっていない場合は、最終的なツリーが適度にバランスが取れるようにリストを並べ替えることができます。

それがエレガントかどうかはわかりませんが、シンプルで説明可能です。 茎か葉かに関係なく、各ノードに一意のIDを割り当てます。単純な整数のカウントで十分です。

ディスクに保存するときは、ツリーをトラバースして、各ノードID、「はい」のリンクID、「いいえ」のリンクID、および質問または回答のテキストを保存します。nullリンクの場合、null値としてゼロを使用します。質問か回答かを示すフラグを追加するか、もっと簡単に言えば、両方のリンクがnullかどうかを確認することができます。次のようなものが表示されます： ジェネラコディセタグプレ

シーケンシャル整数アプローチを使用する場合、ここに示すように、ノードのIDの保存が冗長になる可能性があることに注意してください。IDで並べ替えることができます。

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

最も恣意的な簡単な方法は、任意のグラフを表すために使用できる基本的な形式です。 ジェネラコディセタグプレ

つまり： ジェネラコディセタグプレ

ここには冗長性はあまりありません。フォーマットはほとんど人間が読める形式です。データの重複は、直接の子を持つすべての親のコピーが必要なことだけです。

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

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

ここでの問題は、 その後ツリー。私が作成した場合 を読んだときに「翼がある」オブジェクト 最初の行、私はどういうわけか見つける必要があります 後でラインに遭遇したとき 「持っていますか 翼」、「はい」、「くちばしはありますか？」

これが、私が伝統的にメモリ内のグラフ構造を使用して、ポインタがいたるところにあるようなものである理由です。 ジェネラコディセタグプレ

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

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

次のようにツリーを保存します： ジェネラコディセタグプレ

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

PreOrderDFSを使用したC ++コードは次のとおりです。 ジェネラコディセタグプレ

main()では、次のことができます。 ジェネラコディセタグプレ

DFSは理解しやすいです。 ジェネラコディセタグプレ

ただし、キューを使用してレベルスキャンBFSを使用できます ジェネラコディセタグプレ

main()では、次のことができます。 ジェネラコディセタグプレ

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top