SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: locazopro en Lunes 15 de Junio de 2009, 23:45

Título: Arboles: el camino hacia una hoja
Publicado por: locazopro en Lunes 15 de Junio de 2009, 23:45
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
  1.  
  2. typedef struct _arbol{
  3.    int dato;   /* dato asociado a cada nodo */
  4.    int peso;  /* peso del nodo */
  5.    struct _arbol *hijo[4];  /*hijos */
  6. }arbol;
  7.  
  8.  

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.
Título: Re: Arboles: el camino hacia una hoja
Publicado por: m0skit0 en Martes 16 de Junio de 2009, 12:40
Cita de: "locazopro"
pero no resulta pues para listar cada camino necesitaría pasar por algunos nodos (los nodos padres) mas de una vez
Me parece que no te hace falta eso...

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

Saludos
Título: Re: Arboles: el camino hacia una hoja
Publicado por: locazopro en Domingo 21 de Junio de 2009, 03:44
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!