4

私はこのような二分木を持っています

ここに画像の説明を入力

それを表すオブジェクトは次のようになります (java)

 public class node {
   private String value = "";
   private TreeNode aChild;
   private TreeNode bChild;
 ....
 }

データを読み取り、文字列からツリーを構築したいと考えています。
だから私はそれをシリアル化するためのいくつかの小さなメソッドを書きました、そして私はそれを次のようにしています
(parent-left-right
) E@4、右、F@1、右、B@

それから私はそれを読んで、それをリストとして持っています-オブジェクトはこの順序でO、A、C、D、E、F、Bです

そして今、私の質問は - どうやってツリーを構築するのですか?
反復してスタック、キューに入れますか?
別の順序でシリアル化する必要がありますか?

(基本的に、文字列データからツリーを構築するためのベスト プラクティスを学びたいのですが)
その件に関するリンクを参照してもらえますか?

4

2 に答える 2

0

特に欠落しているノードをどのように表すかに関して、シリアライゼーションは十分に説明されていません。ツリー構造を () で表現したり、バイナリ ツリーを配列手法で使用したりするなど、いくつかの方法があります。これらは両方とも簡単にシリアライズできます。詳細については、バイナリ ツリーの効率的な配列ストレージを参照してください。

于 2012-07-21T23:59:36.853 に答える
0

2 番目の文字列表現を考えると、元のツリーを取得する方法はありません。したがって、そのシーケンスを持つツリーが受け入れられない限り文字列に mor 情報を含める必要があります。null考えられる 1 つの方法は、何らかの方法で参照を表すことです。もう 1 つは、括弧などを使用することです。

最初の表現を考えると、データを復元することはまだ可能です。レベル情報を活用する 1 つのアルゴリズムは次のようになります。

  • ツリー内の現在の位置への参照xを維持します
  • 追加するすべてのノードnについて、 xのレベルがnのレベル以上である限り、その参照xをツリー内で上に移動します。
  • xのレベルがnのレベルよりも正確に 1 小さいことを確認します
  • xをnの親にし、nxの次の子にする
  • xnに移動

これは、ノードに親リンクがある場合に機能します。そうでない場合は、各レベルの最新ノードのリストを維持できます。xはそのリストの最後の要素に対応し、xをツリーの上に移動すると、リストから最後の要素が削除されます。xのレベルは、リストの長さになります。

于 2012-07-21T23:44:44.013 に答える