Programación General > C/C++

 Arboles: el camino hacia una hoja

(1/1)

locazopro:
Haciendo un programa me encontré con este problema y no se me ha ocurrido la solución, les cuento:

tengo un árbol (en este caso es 4-ario) y necesito conocer el camino desde la raíz a cada una de las hojas del árbol. Cuando me refiero a la raíz es que cada nodo pues puede tener 4 hijos (0, 1 , 2 y 3). Entonces lo que necesito es conocer el camino de la raíz a la hoja, por ejemplo un camino podría ser   0-0-1 (la raíz tiene un hijo 0 el cual a su vez tiene otro hijo 0 el cual tiene un hijo 1 el cual es hoja). Espero se halla entendido.

Dejo para mas claridad la estructura correspondiente a los nodos del árbol.


--- Código: C --- typedef struct _arbol{   int dato;   /* dato asociado a cada nodo */   int peso;  /* peso del nodo */   struct _arbol *hijo[4];  /*hijos */}arbol;  
hay algún algoritmo creado para hacerlo?? o alguna ayuda?.  Resulta que he tratado de hacerlo de manera recursiva como es el caso de casi todos los listamientos en árboles, pero no resulta pues para listar cada camino necesitaría pasar por algunos nodos (los nodos padres) mas de una vez y recursivamente no creo que se pueda.

Desde ya gracias.

m0skit0:

--- Cita de: "locazopro" ---pero no resulta pues para listar cada camino necesitaría pasar por algunos nodos (los nodos padres) mas de una vez
--- Fin de la cita ---
Me parece que no te hace falta eso...


--- Código: C ---void recorrer_arbol(_arbol *arbol){    if (arbol)        for (i=0;i<4;i++)            if(arbol->hijo[i])                recorrer_arbol(arbol->hijo[i]);} No lo he probado, ya me cuentas.

Saludos

locazopro:
disculpa la demora, no había podido entrar al foro últimamente.

Respecto al código, ya había escrito uno similar, te cuento, si se tienen muchos niveles entonces un nodo nieto por ejemplo o bisnieto no sería capaz de conocer información alguna de su abuelo o tatarabuelo puesto que esa información solo la van a conocer los hijos. No se si me explico, creo que si echas a andar el código queda mas claro.

De todas maneras ya lo resolví, de una forma muy complicada creo. Tiene que ver con orden por nivel e ir guardando en distintas colas por cada nivel...

Gracias por tu interés.

Saludos!

Navegación

[0] Índice de Mensajes