「指紋」から木を再構築

Question

私はSOとGoogleの研究を行ってきた、とこの前に取り組んできた人を発見していない、あるいは少なくとも、それについて書かれたことのある人。

は私の質問は、分岐の任意の数を有することができ、各ノードで、任意の高さの「ユニバーサル」ツリーが与えられ、 "から始まる一意（及び効率）「指紋」の任意の部分木への道がありますユニバーサル」ツリーのルート、ユニバーサル木と木の指紋を考えると、私はオリジナルのツリーを再構築することができるように？

たとえば、私は可能性の私の宇宙を表現する、（私の貧しい人々のイラストを許す）「ユニバーサル」ツリーを持っています：

                Root
        /  /  /  |  \  \ ... \
       O  O  O   O   O  O     O  (Level 1)
      /|\/|\...................\ (Level 2)

など。

私は、ツリーAを持って、私の宇宙のサブツリー

        Root
      / /|\ \
     O O O O O
    /

など

ツリー「指紋」への道は、その指紋を与えられたように、あり、そして普遍的な木が、私はAを再構築することができるか。

私は、ハッシュ、圧縮、またはおそらく機能/宣言型建設の線に沿って何かを考えていますか？ （時間や空間での）ビッグOの分析がプラスされます。

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

Answer 1

私は、リスト内の各要素は、あなたが持っているどのように多くの子供たち述べリストのリストを、使用します

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

は最初のレベル及び左の子上の2つのノードを持つツリーの子ノードを有している、と右の子ノードは、独自の2持っています。

実行することをお好みのロスレス圧縮アルゴリズムを介して出力ます。

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