Ir al contenido principal

Entradas

Mostrando entradas de mayo, 2012

Convertir un árbol n-ario a binario

Un árbol es una estructura de datos muy importante en el mundo de la 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 muy natural definir arboles n-arios (arboles donde los nodos pueden tener cualquier cantidad de hijos) y para usar las propiedades de los arboles binarios hacer la respectiva conversión. Ver en nuevo sitio 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: 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 asi sucesivamente con los demás hijos que pasan a ser hijos derechos siempr