Ricostruire alberi da una “impronta digitale”

Question

ho fatto la mia ricerca SO e Google, e non hanno trovato nessuno che abbia affrontato questo prima, o per lo meno, chi ha scritto su di esso.

La mia domanda è, dato un albero "universale" di altezza arbitraria, con ogni nodo in grado di avere un numero arbitrario di rami, c'è un modo per univoco (ed efficiente) "impronta" sottoalberi arbitrari partire dalla " universale" radice di albero, in modo tale che dato l'albero universale e impronta digitale di un albero, posso ricostruire l'albero originale?

Per esempio, ho un albero "universale" (perdonate le mie povere illustrazioni), che rappresenta il mio universo di possibilità:

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

ecc.

Ho anche albero A, un sottoalbero radicato del mio universo

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

Etc.

C'è un modo per "impronta digitale" l'albero, in modo che dal momento che le impronte digitali, e l'albero universale, ho potuto ricostruire un?

sto pensando qualcosa lungo le linee di un hash, una compressione, o forse una costruzione funzionale / dichiarativa? Analisi Big-O (nel tempo o nello spazio) è un plus.

Come per-esempio, un'espressione nidificato come:? {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} che rappresentano i nodi effettivi presenti ad ogni livello nella struttura è probabilmente valido, ma può essere fatto in modo più efficiente

Answer 1

I userebbe una lista di liste, dove ogni elemento negli stati della lista quanti figli si hanno:

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

E 'un albero con due nodi al primo livello e il bambino sinistra ha un nodo figlio, e il nodo figlio destro ha 2 propria.

Esegui che uscita attraverso un algoritmo di compressione senza perdita di vostra scelta.

Si potrebbe anche usare un attraversamento in profondità dell'albero, o qualsiasi altro tipo di attraversamento davvero. Tutto ciò che è più facile per voi di ricostruire da.