Reconstruire des arbres à partir d'une «empreinte digitale»

Question

J'ai fait mes recherches sur SO et Google, et je n'ai trouvé personne qui s'y soit attaqué auparavant, ou du moins, quiconque a écrit à ce sujet. Ma question est, étant donné un arbre "universel" de hauteur arbitraire, avec chaque noeud capable d'avoir un nombre arbitraire de branches, y a-t-il un moyen de "marquer" de manière unique (et efficace) les sous-arbres arbitraires? La racine de l'arbre "universel", telle que, compte tenu de l'arbre universel et de l'empreinte d'un arbre, je peux reconstruire l'arbre d'origine?

Par exemple, j'ai un arbre "universel" (pardonnez mes pauvres illustrations), ce qui représente mon univers de possibilités:

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

etc.

j'ai aussi l'arbre A, un sous-arbre enraciné de mon univers

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

Etc

est-il un moyen de « f ingerprint "l'arbre, alors qu'avec cette empreinte, et l'arbre universel, je pourrais reconstruire A?

Je pense à quelque chose comme un hachage, une compression, ou peut-être une construction fonctionnelle/déclarative? L'analyse Big-O (dans le temps ou dans l'espace) est un plus. En tant qu'exemple imbriqué, une expression imbriquée comme: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} représentant les nœuds réels présents à chaque niveau dans l'arborescence est probablement valide, mais peut-elle être effectuée plus efficacement?

Answer 1

J'utiliser une liste de listes, où chaque élément dans la liste états combien d'enfants vous avez:

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

est un arbre avec deux nœuds sur le premier niveau et l'enfant gauche a un nœud enfant, et le nœud enfant droit a 2 de ses propres.

Exécutez cette sortie via un algorithme de compression sans perte de votre choix.

Vous pouvez également utiliser une traversée en profondeur de l'arbre, ou tout autre type de traversée. Tout ce qui est le plus facile à reconstruire.