Supongamos que mi árbol genealógico se ve así:
Después de convertirlo a notación hermano-hijo, se ve así:
? Lo que debemos hacer es: en este momento, debemos calcular cuántas generaciones hay y finalmente salir como una generación.
? Si el álgebra es la altura del árbol según la primera imagen, entonces la última generación es el último nivel del árbol. Sin embargo, el método de la lista enlazada binaria no es tan intuitivo como la primera imagen, pero es tan largo como la esencia. Se comprende el método de la lista binaria enlazada, todavía está muy claro. De acuerdo con las características de la representación del hermano menor (consulte el diagrama esquemático del método de lista enlazada binaria), el subárbol izquierdo del nodo 3 guarda sus nodos secundarios y el subárbol derecho del nodo 3 guarda sus nodos primos (consulte el primer diagrama esquemático). . Supongamos que cada uno de nuestros nodos tiene una variable para almacenar qué generación es, luego, comenzando desde el nodo 1, si queremos encontrar qué generación es el nodo 10, debemos hacer esto: el nodo 1 es la primera generación, luego después del nodo 5 está la primera generación, la segunda generación, y luego vemos que el nodo 10 es la tercera generación. Debido a que el subárbol izquierdo del nodo I-ésimo es su hijo, dado que es hijo, el álgebra debe ser +1, y el subárbol derecho y el nodo I-ésimo (primo) son de la misma generación, por lo que 1 no puede ser agregado. Básicamente, el álgebra +1 va hacia la izquierda y el álgebra va hacia la derecha sin cambios. Esta es la idea de este tema. A través de este método se puede saber cuántas generaciones hay y cada nodo guarda información algebraica (guardada con variables). Simplemente recorra el árbol nuevamente y genere la última generación de nodos. ¿Está claro? Comencé a escribir programas tan pronto como lo supe.