Tema: Interrogante ante un árbol binario
Ver Mensaje Individual
  #1 (permalink)  
Antiguo 29/05/2012, 16:42
Javieer-G
 
Fecha de Ingreso: diciembre-2008
Mensajes: 50
Antigüedad: 15 años, 11 meses
Puntos: 0
Interrogante ante un árbol binario
Esta tarde he estado trabajando sobre la interfaz de un árbol binario de búsqueda.

El caso es que en principio funciona, con la excepción de que no busca el dato que le pida (Vamos, que no funciona).

En Linux no tengo depurador, por lo que no he podido seguir los valores de las variables, pero en cualquier caso, si alguno que tenga tiempo puede echarle un vistazo y decirme si ve algún error, estaría encantado.

De primeras, a mi juicio, el error tiene que estar, o en la función anadir, o en la función buscar... pero vaya, que nunca se sabe :/

Código C: 
Ver original
  1. /*Este programa crea un árbol binario de búsqueda y permite añadir datos
  2. y buscarlos. Está basado en funciones recursivas.*/
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. /*Declaraciones globales*/
  8. typedef struct nodo{
  9. int clave;
  10. struct nodo *derecho;
  11. struct nodo *izquierdo;
  12. }nodo;
  13.  
  14. nodo *raiz; //Raiz del arbol, externa al programa.
  15.  
  16. /*Prototipo de funciones*/
  17. void crear_arbol(void);
  18. nodo *anadir(int clave, nodo *r);
  19. void borrar_arbol(nodo *r);
  20. nodo *buscar(int clave, nodo *r);
  21. void flush_stdin(void);
  22.  
  23. /*Programa principal*/
  24. main()
  25. {
  26. int opcion, dato, c;
  27. nodo *p;
  28. puts("\tMenu");
  29. puts("\t1. Crear arbol");
  30. puts("\t2. Anyadir dato");
  31. puts("\t3. Buscar dato");
  32. puts("\t4. Borrar arbol y salir\n");
  33.  
  34. while(1){
  35. printf("Seleccion: ");
  36. while(1){
  37.     c = scanf("%d", &opcion);
  38.     flush_stdin();
  39.     if(c == 1) break; //Cuando el usuario pulse Ctrl+Z
  40. }
  41.  
  42. if(opcion == 1)
  43.   crear_arbol();
  44.  
  45. if(opcion == 2){
  46.   printf("Introduzca el dato: ");
  47.   scanf("%d", &dato);
  48.   flush_stdin();
  49.   p = anadir(dato, raiz);}
  50.  
  51. if(opcion == 3){
  52.   printf("Dato deseado: ");
  53.   scanf("%d", &dato);
  54.   flush_stdin();
  55.   p = buscar(dato, raiz);
  56.   if(p == NULL)
  57.     puts("\tNo existe ese dato");
  58.   else
  59.     printf("\t\nLa clave %d existe", p->clave);}
  60.  
  61. if(opcion == 4){
  62.   borrar_arbol(raiz);
  63.   exit(1);}
  64. }
  65. }
  66.  
  67. /*Limpiar el buffer de entrada*/
  68. void flush_stdin(void)
  69. {
  70.   int ch;
  71.   while( ((ch = getchar()) != '\n') && (ch != EOF) );
  72. }
  73.  
  74. /*Añadir un nodo. Nótese que es una función recursiva*/
  75. nodo *anadir(int clave, nodo *r)
  76. {
  77.   int num;
  78.  
  79.   if(r == NULL){
  80.      r = (nodo *)malloc(sizeof(nodo));
  81.      if(r == NULL)
  82.         puts("\tFalta Memoria");
  83.      else
  84.         {r->clave = num; r->izquierdo = r->derecho = NULL;}}
  85.   
  86.   else{
  87.      if(num < r->clave)
  88.         r->izquierdo = anadir(num, r->izquierdo);
  89.      if(num > r->clave)
  90.         r->derecho = anadir(num, r->derecho);}
  91.  
  92.   return r;
  93. }
  94.  
  95. /*Crear arbol*/
  96. void crear_arbol(void)
  97. {
  98.   int numero, c;
  99.   while(1){
  100.      printf("Introduzca el dato de la raiz: ");
  101.      c=scanf("%d", &numero);
  102.      if(c==0) continue;
  103.      if(c==1) break;}
  104.   raiz = anadir(numero, raiz);
  105. }
  106.  
  107. /*Buscar datos. Nótese que es una función recursiva*/
  108. nodo *buscar(int dato, nodo *r)
  109. {
  110.   if(r == NULL)  /*Dato no existe*/
  111.      return r;
  112.  
  113.   else if(dato > r->clave)
  114.      return buscar(dato, r->derecho); /*Buscar en subarbol derecho*/
  115.  
  116.   else if(dato < r->clave)
  117.      return buscar(dato, r->izquierdo); /*Buscar en subarbol izquierdo*/
  118.   else
  119.      return r; /*Dato no encontrado*/
  120. }
  121.  
  122. /*Borrar arbol. De nuevo, una función recursiva*/
  123. void borrar_arbol(nodo *r)
  124. {
  125.   if(r != NULL){
  126.      borrar_arbol(r->izquierdo);
  127.      borrar_arbol(r->derecho);
  128.      free(r);}
  129. }