[Marcelo]

Hola, estoy tratando de realizar un ejercicio en donde me pide que encuentre el número de nodos que hay en el camino mas corto desde la raíz a un nodo hoja en un árbol binario no vacío . Lo quiero implementar en el lenguaje c una función recursiva que no utilice ninguna estructura auxiliar:

La función incompleta es la siguiente:

int cantnodos(Arbol a)
{
 if ( (a->hi == NULL) && (a->hd == NULL) )
    return 1;

 else
   if ( (a->hi != NULL) && (a->hd == NULL) )
    x=(1+cantnodos(a->hi))
   else
     if ( (a->hi == NULL) && (a->hd != NULL) )
      y=(1+cantnodos(a->hd))

return (min(x,y));
 
}

Donde min es una función que compara el valor de los camino obtenidos por los subarboles y devuelve el mínimo

Obviamente esta función no funciona , lo que nose como hacer para ir manteniendo los valores de los caminos cuando la recursión llame al sub-árbol izquierdo y el sub-árbol derecho con las variables x e y que son globales.

De antemano les agradezco su ayuda.

[Phicar]

Hola, ten una variable global que sea min y reescribe la funcion con otro parametro que sea el entero que llevas por camino....osea

int min = 1<<30;
int cantnodos(Arbol a,int b){

}

cuando llames la funcion la llamas como cantnodos(a->hd,b+1)

y para comparar lo haces en el if en el que sabes que llego a una hoja

Me hago entender?

Pd: Ya no necesitas que cantNodos sea tipo entero, void funciona

[Marcelo]

Hola Phicar!! Muchas gracias por responder! El ejercicio me pide implementar una función , el tema es que cuando la recursión entra por ejemplo si a->hi != NULL  sucede que  llama x=(1+cantnodos(a->hi)) , y en ese llamado sucede que a->hd != NULL por lo que llama ahora y=(1+cantnodos(a->hi)) , y esa suma tendría que realizarse en la variable x , estoy perdiendo la suma de ese sub-árbol , no se me ocurre como solucionarlo 

[Phicar]

Hola, como te digo..es que así no la vas a poder guardar..la solución que te doy es:
int min = 1<<20;
void cantnodos(Arbol a,int b)
{
 if ( (a->hi == NULL) && (a->hd == NULL) ){
    if(b<min)min = b;
return;
}
 else
   if ( (a->hi != NULL) && (a->hd == NULL) )
    return cantnodos(a->hi,b+1);
   else
     if ( (a->hi == NULL) && (a->hd != NULL) )
      return cantnodos(a->hd,b+1);

 
}

y en la variable min te quedará el resultado.

BtW, ahora que veo el código..creo que está mal...considera un nodo que tenga los dos hijos. creo que no entrará

[Marcelo]

Disculpame Phicar , con este  código:


void cantnodos(Arbol a,int b)
{
 if ((a->hi==NULL)&&(a->hd==NULL))
  {if (b<min)
      min=b;
   return;   
  }
 else
   {
    if ((a->hi!=NULL)&& (a->hd!=NULL))
     return(cantnodos(a->hi,b+1)); 
    else
     if((a->hd!=NULL)&& (a->hi==NULL))
       return(cantnodos(arbol->hd,b+1));
     else
       if((a->hi!=NULL)&& (a->hd==NULL))
       return(cantnodos(a->hi,b+1));   
   }
}

Me resuelve siempre el sub-árbol izquierdo de la raíz ya que si la raíz tiene dos hijos va entrar por el condicional

if ((a->hi!=NULL)&& (a->hd!=NULL))
     return(cantnodos(a->hi,b+1));

que pasa si el camino mínimo esta en el sub-árbol derecho? No lo supervisa.

[Phicar]

Hola..no deberías hacer esos condicionales...simplemente verificar que no sea null y mandarte
o sea:

void cantnodos(Arbol a,int b)
{
 if ((a->hi==NULL)&&(a->hd==NULL))
  {if (b<min)
      min=b;
   return;   
  }
 
     if((a->hd!=NULL))
       return(cantnodos(arbol->hd,b+1));

       if((a->hi!=NULL)
       return(cantnodos(a->hi,b+1));   
}

Eso debería funcionar

[pierrot]

Hola Marcelo.

Esencialmente tu idea estaba bien, sólo que te has comido algunos casos base. O sea, una función así debería funcionar:

int cantNodos(ABB abb){
// Devuelve el numero de nodos del camino mas corto, de la raiz a una hoja.
// Precondicion: !esVacioABB(abb)

     int res;

     if((abb->izq==NULL)&&(abb->der==NULL))
          res=1;
     else if((abb->izq==NULL)&&(abb->der!=NULL))
          res=1+cantNodos(abb->der);
     else if((abb->izq!=NULL)&&(abb->der==NULL))
          res=1+cantNodos(abb->izq);
     else
          res=1+min(cantNodos(abb->izq),cantNodos(abb->der));

     return res;
}

[Marcelo]

Así es PabloN , la función funciona correctamente! Les agradezco a los dos por su AYUDA!

Saludos.