Convertir un árbol n-ario a binario

Un árbol es una estructura de datos muy importante en programación, sin embargo el tipo de árbol que se usa comúnmente por sus propiedades es el árbol binario (árbol donde cada nodo tiene a lo máximo 2 nodos descendientes o nodos hijo). Es natural definir arboles n-arios (arboles donde los nodos pueden tener cualquier cantidad de hijos) pero para usar las propiedades de los arboles binarios debemos hacer la respectiva conversión.

Arboles

Si tenemos como inicio al siguiente árbol n-ario, el algoritmo de conversión es muy sencillo y se explicara gráficamente a continuación:

Arboles--1-

Empezamos por la raíz, la raíz sigue siendo la misma para el árbol binario, a continuación el hijo mas de la izquierda de la raíz para a ser hijo inmediato izquierdo de la raíz y los demás hijos de la raíz se van colocando por orden.
El segundo hijo de la raíz pasa a ser hijo derecho del primer hijo, y así sucesivamente con los demás hijos que pasan a ser hijos derechos siempre se su hermano anterior.

Arboles--2-

Luego pasamos a hacer lo mismo con los hijos de la raíz. Empezamos con el nodo B (en este ejemplo) y colocamos a su primer hijo de mas a la izquierda cono su hijo inmediato a la izquierda y los demás a la derecha de manera consecutiva.

Arboles--3-

Pasamos al siguiente nodo (Nodo F en este ejemplo) al otro hijo que tienes hijos, y hacemos lo mismo.

Arboles--4-

Terminado esto pasamos a los siguientes nodos hijo, culminando así y llegando al siguiente árbol binario.

Arboles--5-

El algoritmo es sencillo, solo falta implementarlo en un lenguaje de programación, esperamos sus comentarios para poder realizarlo en su lenguaje de programación favorito.

Daniel Alvarez

Software engineer, developer and producer of native mobile applications for Android and iOS, Angular, Firebase. Teacher. Speaker. Creating bots.