Funcion Listar de un Arbol N-Ario (representado como Arbol Binario)

[ElPatoGarrido]

Hola, vengo a plantear una duda que tengo, ojala que me entiendan bien por que (por lo menos yo) encuentro que es un problema mas o menos complejo xD.

En una tarea me piden usar un arbol N-Ario para ingresar elementos arbitrarios de tipo string, y bueno, pense hacer el codigo con listas de listas (arbol binario) basandome en lo que sale en esta pagina: http://blog.mozilla.org/nnethercote/...ry-trees-in-c/, en donde cada nodo tiene un puntero a su nodo hijo y a su nodo hermano, bueno.

Por si no se entiende bien hay trate de explicar con un dibujo como se representa el arbol n-ario a un arbol binario.



Primero tenemos un arbol n-ario normal, despues eso lo representamos con un struct con doble puntero, en resumidas cuentas lo podemos ver como que cada nodo puede apuntar a una sublista, y esto finalmente lo podemos ver como un arbol binario.

El codigo para insertar los elementos lo tengo hecho y la estructura de mi nodo lo tengo asi.

Código C++:

struct nodo {
    string paquete;
    nodo *Hermano;
    nodo *Hijo;
};
 

Lo cual no es muy importante, pero bueno xD.

El tema de como ingreso los nodos es por ejemplo, me piden ingresarle un 'x' como hijo al nodo 'y', pues recorro el arbol hasta encontrar 'y' (con postorden, preorde, da igual, el tema es llegar al nodo 'y') y si el puntero hijo de 'y' es null simplemente ingreso 'x', como su hijo si no pues recorro la lista de los "hermanos de los hijos de y" e ingreso 'x' al final, eso seria mas o menos mi metodologia de ingreso.

Ahora viene mi duda

El problema que tengo es que no se como hacer la funcion listar, por que si me dicen que liste el nodo que contiene el 12 en la imagen anterior, por ejemplo, tendria que lanzar por pantalla 1 -> 4 -> 9 -> 12 (se lista con respecto al arbol n-ario, por que eso es lo que se supone que es, yo lo transformo a uno binario para trabajar mas facil con el), pero en el arbol binario, que es como finalmente se comporta mi arbol n-ario, para mi es mas dificil pensar el algorimto para mostrar el listado, es decir, tengo que escribir el 1, despues ignorar el 2 y el 3 y llegar hasta el 4, escribir el 4, despues escribir el 9, saltarme el 11, llegar al 12 y escribirlo finalmente.

La traba que tengo es que creo que se hace con una funcion recursiva, pero no se me ocurre como discriminar que nodos escribir y cuales no (los algoritmos recursivos me elevan al cuadrado el nivel de dificultad para pensar xD), como que encuentro que ese trabajo se complico haciendo que el arbol n-ario se transformara en un arbol binario xD.

¿Alguien me ayuda?, ¿Se entendio el problma?, si no me dicen para tratar de explicarlo mejor.

Saludos.

[Malenko]

Mirate la parte de algoritmos de arboles, en concreto la parte de como recorrerlos. Ahí hayarás tu respuesta ;)

[razpeitia]

Usa BFS para eso vas a necesitar implementarte un queue.

Checate este post http://www.forosdelweb.com/f96/funci...0/#post4432952

[ElPatoGarrido]

Gracias, creo que se me ocurrio una forma usando el BFS, aun que igual tendria que hacer algunas discriminaciones ademas, pero bueno, gracias.

[ElPatoGarrido]

Mmmmm, como que igual quede atrapado xD.



Al listar un elemento me los lista como el arbol de la derecha (binario), pero necesito que me los liste como si se tratara del arbol de la izquierda (n-ario).

Por ejemplo: Si me piden listar 'I' tengo que escribir: A -> B -> I, pero como mi arbol n-ario esta transformado como uno binario me lista la 'I' asi: A -> B -> G -> H -> I

Trato de hacer la discriminacion para que me lo liste como si se tratase del arbol de la izquierda, pero no me sale, ¿alguien que me ayude?.