La reconstrucción de los árboles de una “huella digital”

Question

He hecho mi investigación SO y Google, y no han encontrado a nadie que ha abordado este antes, o al menos, cualquier persona que ha escrito sobre él.

Mi pregunta es, dado un árbol "universal" de altura arbitraria, con cada nodo capaz de tener un número arbitrario de ramas, hay una manera de forma única (y eficiente) "huella digital" sub-árboles arbitrarias a partir de la " universal" de la raíz del árbol, de tal manera que da el árbol universal y la huella digital de un árbol, que puede reconstruir el árbol original?

Por ejemplo, tengo un árbol "universal" (valga mis pobres ilustraciones), que representa mi universo de posibilidades:

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

etc.

También tengo un árbol, un subárbol con raíz de mi universo

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

etc.

¿Hay una manera de "huella digital" del árbol, por lo que, dado que las huellas dactilares, y árbol universal, podría reconstruir una?

Estoy pensando en algo en la línea de un hash, una compresión, o tal vez una construcción funcional / declarativa? análisis Big-O (en tiempo o espacio) es una ventaja.

Como para-ejemplo, una expresión anidada como:? {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} que representa los nodos reales presentes en cada nivel en el árbol es probablemente válido, pero ¿Se puede hacer de manera más eficiente

Answer 1

Yo usaría una lista de listas, donde cada elemento de la lista de estados cuántos hijos tiene:

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

Es un árbol con dos nodos en el primer nivel y el hijo izquierdo ha un nodo hijo, y el nodo hijo derecho tiene 2 propia.

Ejecutar que la salida a través de un algoritmo de compresión sin pérdida de su elección.

También podría usar un recorrido en profundidad del árbol, o cualquier otro tipo de recorrido realmente. Lo que es más fácil para que usted pueda reconstruir a partir de.