Codificación de árboles n-arios como árboles binarios

Codificación de árboles n-arios como árboles binarios


Hay un mapeo uno a uno entre los árboles generales y árboles binarios, el cual en particular es usado en Lisp para representar árboles generales como árboles binarios. Cada nodo N ordenado en el árbol corresponde a un nodo N 'en el árbol binario; el hijo de la izquierda de N’ es el nodo correspondiente al primer hijo de N, y el hijo derecho de N' es el nodo correspondiente al siguiente hermano de N, es decir, el próximo nodo en orden entre los hijos de los padres de N.
Esta representación como árbol binario de un árbol general, se conoce a veces como un árbol binario primer hijo/siguiente hermano, o un árbol doblemente encadenado.
Una manera de pensar acerca de esto es que los hijos de cada nodo estén en una lista enlazada, encadenados junto con el campo derecho, y el nodo sólo tiene un puntero al comienzo o la cabeza de esta lista, a través de su campo izquierdo.
Por ejemplo, en el árbol de la izquierda, la A tiene 6 hijos (B, C, D, E, F, G). Puede ser convertido en el árbol binario de la derecha.
Un ejemplo de transformar el árbol n-ario a un árbol binario Cómo pasar de árboles n-arios a árboles FLOFO.