0

私は SO と Google の調査を行いましたが、以前にこれに取り組んだ人、または少なくともそれについて書いた人を見つけていません。

私の質問は、任意の高さの「ユニバーサル」ツリーがあり、各ノードが任意の数のブランチを持つことができる場合、「ユニバーサル」ツリーから始まる任意のサブツリーを一意に (そして効率的に) 「フィンガープリント」する方法があるかどうかです。ユニバーサル ツリーとツリーのフィンガープリントが与えられた場合、元のツリーを再構築できますか?

たとえば、私は可能性の宇宙を表す「普遍的な」ツリーを持っています (下手なイラストを許してください):

                根
        / / / | \ \ ... \
       ああああああ (レベル 1)
      /|\/|\.................\ (レベル 2)

等

私はまた、私の宇宙のルートサブツリーであるツリーAを持っています

        根
      / /|\ \
     うおおお
    /

等。

ツリーを「フィンガープリント」する方法はありますか? そのフィンガープリントとユニバーサル ツリーがあれば、A を再構築できますか?

ハッシュ、圧縮、またはおそらく機能的/宣言的な構造に沿って何かを考えていますか? Big-O 分析 (時間または空間) はプラスです。

たとえば、次のようなネストされた式:{{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...}ツリーの各レベルに存在する実際のノードを表すことはおそらく有効ですが、より効率的に行うことはできますか?

4

1 に答える 1

0

リストのリストを使用します。リスト内の各要素には、子供の数が示されています。

[[2][1,2][0,0,0]]

最初のレベルに 2 つのノードを持つツリーで、左側の子ノードには 1 つの子ノードがあり、右側の子ノードには 2 つの子ノードがあります。

選択したロスレス圧縮アルゴリズムを介してその出力を実行します。

ツリーの深さ優先トラバーサル、または他のタイプのトラバーサルを実際に使用することもできます。再構築するのが最も簡単なものは何でも。

于 2010-04-12T18:59:48.327 に答える