Reconstruindo árvores de uma "impressão digital"

Question

Já fiz a minha pesquisa de SO e o Google, e não encontrei ninguém que tenha abordado isso antes, ou pelo menos, qualquer um que tenha escrito sobre isso.

Minha pergunta é que, dada uma árvore "universal" de altura arbitrária, com cada nó capaz de ter um número arbitrário de galhos, existe uma maneira de sub-árvores arbitrárias de "impressão digital" de "impressão digital", a partir da árvore "universal" Raiz, de modo que, dada a árvore universal e a impressão digital de uma árvore, posso reconstruir a árvore original?

Por exemplo, eu tenho uma árvore "universal" (perdoe minhas pobres ilustrações), representando meu universo de possibilidades:

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

etc.

Eu também tenho a Árvore A, uma subárvore enraizada do meu universo

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

Etc.

Existe uma maneira de "imprimir" a árvore, para que, dada a impressão digital e a árvore universal, eu poderia reconstruir um?

Estou pensando em algo parecido com um hash, uma compressão ou talvez uma construção funcional/declarativa? A análise Big-O (no tempo ou no espaço) é uma vantagem.

Como uma instância, uma expressão aninhada como: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} Representando os nós reais presentes em cada nível na árvore provavelmente é válido, mas pode ser feito com mais eficiência?

Answer 1

Eu usaria uma lista de listas, onde cada elemento da lista afirma quantas crianças você tem:

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

É uma árvore com dois nós no primeiro nível e o filho esquerdo tem um nó filho, e o nó da criança certo tem 2.

Execute essa saída através de um algoritmo de compactação sem perdas de sua escolha.

Você também pode usar uma travessia de profundidade da árvore, ou qualquer outro tipo de travessia realmente. O que for mais fácil para você reconstruir.