Un Árbol Eneario es una estructura de datos que se caracterizan porque cada nodo tiene un número indeterminado de hijos: Por ejemplo:

El Nodo A tiene 4 hijos, los Nodos B, C y E no tienen hijos, y el Nodo D tiene 3 hijos. Esta circunstancia exige que cada Nodo guarde una Lista de apuntadores para almacenar el número de hijos. El árbol anterior en la memoria dinámica se puede ver así:

Al igual que en los TDAs estudiados con anterioridad, la forma de implementar un árbol n-ario dependerá del problema a resolver y de la capacidad del diseñador. No obstante, existen 3 Implementaciones básicas:

– Implementación matricial. El árbol se representa en un vector de enteros, donde cada componente contiene el índice de su nodo padre.
– Implementación con listas. Se representa mediante un vector de listas. Cada índice de las componentes del vector se asocia con un nodo del árbol, y cada componente es una lista con los Hijos del nodo.
– Implementación con celdas enlazadas. Cada nodo del árbol es una celda enlazada con un puntero a su padre, a su hijo izquierda y a su hermano derecha.
– El tipo Nodo del árbol es entero.
– La relación padre-hijo se representa en un vector P, donde P[i] indica cuál es el nodo padre de i. Si el nodo no tiene padre (es la raíz), P[i] tomará valor -1.
– Las etiquetas de los nodos se representan en otro vector de etiquetas.

Esta implementación es relativamente sencilla y con bajo coste de memoria. Facilita las operaciones de acceso a los ancestros de un nodo (eficiencia O(log(n)) para viajar desde un nodo hoja hasta la raíz), pero resulta difícil gestionar operaciones con los hijos (conocer la altura, determinar los hijos, establecer hijo izquierda y hermano derecha…).

De acuerdo con la definición anterior, la estructura de cada Nodo será:

El apuntador hijo , direcciona al primer hijo, al hijo más a la izquierda y el apuntador hermano, se utiliza para formar la lista de hermanos. Para el ejemplo, los hijos de A están en la Lista:

Los hijos de D se encuentran en la Lista:


Veamos otro ejemplo:

En la memoria dinámica este Árbol se puede ver así:

Recorridos para Arboles Enearios
Lo mismo que los Árboles Binarios, los Arboles Enearios pueden recorrerse de 4 formas: Inorden, Preorden, Posorden y por niveles. Veamos cada uno de ellos.

Recorrido Inorden:
Observemos el siguiente Árbol:


El recorrido Inorden es: 2, 1, 5, 3, 6, 10, 7, 4, 11, 8, 12, 13, 9.

El Orden del recorrido es:
– Primer Hijo en Inorden.
– Padre
– Hermano en Inorden.

Recorrido Preorden:
Vemos el siguiente Árbol:

Un Árbol se recorre el Preorden, así:
– Padre
– Primer hijo en Preorden
– Hermano en Preorden
Siguiendo este orden, el recorrido es: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Recorrido en Posorden:
Observemos el siguiente Árbol:

El recorrido en Posorden del anterior Arbol es:
– Hijo en Posorden
– Hermano en Posorden
– Padrea
Con lo cual el árbol anterior en Posorden es: 2, 10, 13, 14, 15, 11, 12, 3, 9, 1.

Implementación de Árbol Eneario en SEED

Descripción
La estructura Árbol Eneario General consiste en un conjunto de elementos fundamentales denominados nodos enearios, estos poseen cuántos hijos se desee este elemento fundamental se implemento en la clase NodoEneario este elemento contiene la información del nodo, referencia a un nodo denominado hijo, el cual es el hijo más cercando y otra al nodo hermano más cercano.

Esta estructura se implementó en la clase NodoEneario que se origina con la creación de un NodoEneario de nominado “raíz”, de donde se toma referencia para el desarrollo de los diferentes procesos básicos de la estructura. Cabe mencionar que esta estructura no almacena los datos de manera ordenada, para la inserción de datos se debe indicar el padre del nuevo nodo a insertar, si el padre posee ya un hijo este pasa automáticamente a ser el hermano del nuevo nodo.j

Para la eliminar un dato de la estructura solo se debe indicar la información que posea el nodo.

Requerimientos funcionales implementados para Arboles Enearios:
RF1 – Crear un nuevo Árbol Eneario.
RF2 – Conocer y editar la raíz del Árbol Eneario.
RF3 – Insertar nuevos datos en un Árbol Eneario.
RF4 – Eliminar datos de un Árbol Eneario.
RF5 – Consultar la existencia de objetos dentro del Árbol Eneario.
RF6 – Conocer el listado de Hijos de un determinado objeto.
RF7 – Consultar el listado de hojas de un Árbol Eneario.
RF8 – Conocer el número de hojas del Árbol Eneario.
RF9 – Recorrer un Árbol Eneario en Preorden.
RF10 – Recorrer un Árbol Eneario en Inorden.
RF11 – Recorrer un Árbol Eneario en PostOrden.
RF12 – Recorrer un Árbol Eneario por niveles.
RF13 – Conocer el peso de un Árbol Eneario.
RF14 – Consultar la altura de un Árbol Eneario.
RF15 – Consultar la gordura de un Árbol Eneario.

Implementación de un Simulador para Árbol Eneario:
El Simulador para Árbol Eneario posee las operaciones indicadas por su menú de opciones dentro del mismo: