Arbres à partir d'une reconstruction « empreinte digitale »

Question

Je l'ai fait ma SO et Google recherche et n'a pas trouvé quelqu'un qui a abordé auparavant, ou du moins, toute personne qui a écrit à son sujet.

Ma question est, étant donné un « universel » arbre de hauteur arbitraire, chaque nœud en mesure d'avoir un nombre arbitraire de branches, est-il possible de manière unique (et efficace) « empreinte digitale » sous-arbres arbitraires à partir de la " universel » la racine de l'arbre, de sorte que l'arbre universel donné et l'empreinte digitale d'un arbre, je peux reconstruire l'arbre original?

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.

Y at-il un moyen de « empreinte digitale » l'arbre, de sorte que, étant donné que les empreintes digitales, et l'arbre universel, je pouvais reconstruire A?

Je pense quelque chose le long des lignes d'un hachage, une compression, ou peut-être une construction fonctionnelle / déclarative? analyse Big-O (dans le temps ou dans l'espace) est un plus.

En instance pour une expression imbriquée comme: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} représentant les nœuds réels présentent à chaque niveau de l'arbre est probablement valable, mais qu'il peut être fait plus efficacement

Answer 1

J'utiliser une liste de listes, où chaque élément dans les états de liste 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 a droit 2 lui-même.

Exécuter cette sortie par un algorithme de compression sans perte de votre choix.

Vous pouvez également utiliser un parcours en profondeur d'abord de l'arbre, ou tout autre type de traversal vraiment. Quel que soit le plus facile pour vous de reconstruire à partir.