Listar niveles Árbol n-ario

Iniciado por chinolaya, 3 Febrero 2015, 01:51 AM

0 Miembros y 1 Visitante están viendo este tema.

chinolaya

Hola a todos. Soy nuevo por el foro y este es mi primer mensaje.

Tengo problemas para lograr escribir el siguiente algoritmo.
Necesito un algoritmo que me liste o imprima los nodos por niveles de un árbol n-ario, finitario o general (lo he encontrado con cualquiera de los tres nombres por internet).

La estructura del árbol es la siguiente:

struct nodo{
   int dato;
   nodo * primerHijo;
   nodo * siguientehermano;
};


Cualquier tipo de ayuda sera bienvenida.

Gracias.

eferion

¿y qué tienes hecho hasta ahora?

¿Dónde te atascas?

No se hacen tareas... si no aportas nada no creo que ayude demasiado.

chinolaya

No pude editar el mensaje original, por lo tanto sigo por aquí.

No había puesto el código que hice porque no ayuda en nada, no hace lo que tiene que hacer por lo tanto no logre nada con el.

Dejo un ejemplo para ver si queda mas claro lo que necesito. Este es un ejemplo de un arbol general o n-ario que tengo:

               1
     2        7        8
  3    6            9     12
4 5             10 11

Lo que tendría que imprimir seria:

1
2 7 8
3 6 4 5 9 12
10 11

El problema esta cuando tengo que imprimir nodos que están en un mismo nivel pero son hijos de padres distintos. Ahí se me complica ya que tendría que saltar de una rama a otra para seguir imprimiendo.

Una idea bastante general de lo que venia haciendo es la siguiente:

void muestroNiveles(nodo *raiz){
   nodo *aux = raiz;
   if(raiz != NULL){
      cout<<aux->dato;
      muestroNiveles(aux->siguienteHermano);
      cout<<end; //Esto seria para imprimir el espacio cuando cambio de nivel
      muestroNiveles(aux->primerHijo);
   }
}

eferion

Para conseguir esa salida puedes optar por una función del tipo:

int mostrarNiveles(nodo *nodo_actual, int nivel );

La llamada principal debería ser algo del tipo:

int nivel = 0;
while( mostrarNiveles( raiz, nivel ) )
  nivel++;


Esto es, se llama a la función en bucle y, en cada iteración, se incrementa el valor de "nivel". Esta variable te debería permitir imprimir únicamente un nivel del árbol. Para ello puedes, por ejemplo, seguir la siguiente secuencia en "mostrarNiveles":

* si el nivel es 0, imprimo el valor actual y salgo de la función retornando 1
* decremento el valor de nivel
* Si tengo hijos, llamo a "mostrarNiveles" pasando como nodo actual mis dos hijos.
* Si no tengo hijos retorno "0"

Falta algún detalle por incluir para que funcione bien, como poner los saltos de línea, pero vale para un pseudocódigo.