Rekonstruieren Bäume von einem „Fingerabdruck“

Question

Ich habe meine SO und Google Forschung getan, und habe niemanden gefunden, der diese vor in Angriff genommen hat, oder zumindest jeder, der über sie geschrieben hat.

Meine Frage ist, da einen „universellen“ Baum beliebiger Höhe, wobei jeder Knoten in der Lage, eine beliebige Anzahl von Filialen haben, ist es eine Möglichkeit, eindeutig (und effizient) „Fingerabdruck“ willkürliche Unterbäume ausgehend von den " universal“Wurzel des Baumes, so dass die universal-Baum und ein Baum Fingerabdruck gegeben, ich kann den ursprünglichen Baum rekonstruieren?

Zum Beispiel, ich habe einen „universellen“ Baum (meine armen Abbildungen vergeben), was mein Universum der Möglichkeiten:

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

etc.

ich auch Baum A, ein verwurzelter Unterbaum meines Universums

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

Etc.

Gibt es eine Möglichkeit, „Fingerabdruck“ der Baum, so dass dieser Fingerabdruck gegeben, und die Universal-Baum, konnte ich A rekonstruieren?

Ich denke, etwas entlang der Linien eines Hash, eine Kompression, oder vielleicht eine funktionale / deklarative Konstruktion? Big-O-Analyse (in Zeit oder Raum) ist ein Plus.

Als for-Instanz, ein verschachtelter Ausdruck wie: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} repräsentiert die tatsächlichen Knoten auf jeder Ebene in dem Baum präsentieren, ist wahrscheinlich gültig, aber es kann effizienter durchgeführt werden

Answer 1

würde ich eine Liste von Listen verwenden, wobei jedes Element in der Liste gibt an, wie viele Kinder Sie haben:

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

Ist ein Baum mit zwei Knoten auf der ersten Ebene und dem linken Kind ein Kind-Knoten hat, und das rechte Kind-Knoten hat zwei seiner eigenen.

Ausführen, dass die Ausgabe durch einen verlustfreien Komprimierungsalgorithmus Ihrer Wahl.

Sie können auch einen depth-first Traversal des Baumes, oder jede andere Art von Traversal wirklich verwenden. Was auch immer am einfachsten für Sie zu rekonstruieren.