19/09/2019, 10:09:12 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Arbol Binario  (Leído 3126 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Marcelo
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 35


Ver Perfil
« : 09/10/2012, 11:34:14 pm »

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.
En línea
Phicar
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 514



Ver Perfil WWW
« Respuesta #1 : 09/10/2012, 11:48:42 pm »

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 :sonrisa:
En línea

redinfocol.org
Marcelo
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 35


Ver Perfil
« Respuesta #2 : 10/10/2012, 12:29:08 am »

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  :indeciso:
En línea
Phicar
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 514



Ver Perfil WWW
« Respuesta #3 : 10/10/2012, 12:44:29 am »

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á

En línea

redinfocol.org
Marcelo
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 35


Ver Perfil
« Respuesta #4 : 10/10/2012, 01:44:19 am »

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.
En línea
Phicar
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 514



Ver Perfil WWW
« Respuesta #5 : 10/10/2012, 02:01:57 am »

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 :sonrisa:
En línea

redinfocol.org
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.348


Ver Perfil
« Respuesta #6 : 10/10/2012, 09:01:39 am »

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;
}
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Marcelo
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 35


Ver Perfil
« Respuesta #7 : 11/10/2012, 08:45:17 pm »

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

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!