• Miércoles 19 de Enero de 2022, 11:02

Autor Tema:  Arboles: el camino hacia una hoja  (Leído 681 veces)

locazopro

  • Miembro activo
  • **
  • Mensajes: 51
    • Ver Perfil
Arboles: el camino hacia una hoja
« en: Lunes 15 de Junio de 2009, 23:45 »
0
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.

m0skit0

  • Miembro de PLATA
  • *****
  • Mensajes: 2337
  • Nacionalidad: ma
    • Ver Perfil
    • http://fr33kk0mpu73r.blogspot.com/
Re: Arboles: el camino hacia una hoja
« Respuesta #1 en: Martes 16 de Junio de 2009, 12:40 »
0
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

locazopro

  • Miembro activo
  • **
  • Mensajes: 51
    • Ver Perfil
Re: Arboles: el camino hacia una hoja
« Respuesta #2 en: Domingo 21 de Junio de 2009, 03:44 »
0
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!