lunes, 31 de marzo de 2014

Examen parcial de Programación de Sistemas y Concurrencia. Curso 2011/2012.

Al igual que ayer os dejaba el ejercicio del parcial del curso pasado, hoy os dejo mi solución al ejercicio de C del primer parcial de Programación de Sistemas y Concurrencia del curso 2011/2012. Como ayer, digo que mi solución puede no ser correcta pero al menos podéis tomarla como guía y hacerle las modificaciones que veáis necesarias. Yo he usado la recursividad en los métodos que nos piden ya que no se me ocurría la forma iterativa de hacerlo, así que si encontráis diferentes formas de hacerlo podéis comentar ;). Aquí tenéis el enunciado para descargar.

Un árbol binario de búsqueda es un árbol binario en el que para cualquier nodo el subárbol izquierdo
(si no está vacío) contiene valores menores que el valor que contiene dicho nodo, y el subárbol derecho
(si no está vacío) contiene valores mayores. Así, por ejemplo, para la lista de números introducidos por
este orden:
21, 5, 78, 1, 7, 45, 90,4,6,15,77,80,99
Se crearía un árbol binario de búsqueda con la siguiente distribución:
Definir el tipo TArbol e implementar las siguientes operaciones:
void CrearABB (TArbol *arb)
Este procedimiento construye un árbol binario de búsqueda vacio.
void InsertarEnABB (TArbol *arb, int elem)
Este procedimiento inserta elem en un árbol binario de búsqueda. Después de la inserción el árbol
DEBE seguir siendo un árbol binario de búsqueda.
void RecorrerABB (TArbol arb)
Dado un árbol binario de búsqueda, este procedimiento muestra en pantalla los elementos del árbol
ordenados de menor a mayor. Para el dibujo de la figura la salida sería:
1,4,5,6,7,15,21,45,77,78,80,90,99
void DestruirABB(TArbol *arb)
Este procedimiento libera la memoria de todos los nodos del árbol.

#include <stdio.h>
#include <stdlib.h>

typedef struct TNodo* TArbol;
struct TNodo {
 int valor;
 TArbol hijoizquierdo;
 TArbol hijoderecho;
};

void CrearABB (TArbol *arb){//Este procedimiento construye un árbol binario de búsqueda vacio.
 *arb = NULL;
}

void InsertarEnABB (TArbol *arb, int elem){
 //Este procedimiento inserta elem en un árbol binario de búsqueda. Después de la inserción el árbol
 //DEBE seguir siendo un árbol binario de búsqueda.
 TArbol ptr = *arb;
 TArbol nuevo = malloc(sizeof(struct TNodo));
 int insertado = 0;
 nuevo ->valor = elem;
 nuevo -> hijoderecho = NULL;
 nuevo -> hijoizquierdo = NULL;

 if(ptr == NULL){ //árbol vacío
  *arb = nuevo;
 }
 while(ptr != NULL && !insertado){
  if(ptr->valor < nuevo ->valor  ){

   if(ptr -> hijoderecho == NULL){
    ptr -> hijoderecho = nuevo;
    insertado = 1;
   }
   ptr = ptr -> hijoderecho;


  }else if (ptr->valor > nuevo ->valor ){
   if(ptr -> hijoizquierdo == NULL){
    ptr -> hijoizquierdo = nuevo;

    insertado = 1;
   }
   ptr = ptr -> hijoizquierdo;
  }
 }
}

void RecorrerABB (TArbol arb){
 /*Para el dibujo de la figura la salida sería:1,4,5,6,7,15,21,45,77,78,80,90,99 */
  if(arb -> hijoizquierdo != NULL){
   RecorrerABB(arb ->hijoizquierdo);
  }

  printf(" %d ", arb -> valor);

  if(arb -> hijoderecho != NULL){
   RecorrerABB(arb -> hijoderecho);
  }

}


void DestruirABB(TArbol *arb){
 //Este procedimiento libera la memoria de todos los nodos del árbol.

 if((*arb) -> hijoizquierdo != NULL){
  DestruirABB(&((*arb) ->hijoizquierdo));
 }
 if((*arb) -> hijoderecho != NULL){
  DestruirABB(&((*arb) -> hijoderecho));
 }

 free(*arb);

}

Para ver que el árbol se forma correctamente he implementado un método en el que se representa el árbol pero girado 90º, pues así era más sencillo. Tenemos que pasarle como argumentos el árbol y el número de nodos de éste. Os lo dejo por si queréis probarlo.

void verABB(TArbol arbol, int n){
     if(arbol!=NULL){

     verABB(arbol->hijoderecho, n+1);
     int i;

     for(i=0; i<n; i++)
           printf("    ");

     printf("%d\n", arbol->valor);

     verABB(arbol->hijoizquierdo, n+1);
    }
}
Por último sólo quedaría hacer un main para probar los distintos métodos y el ejercicio quedaría terminado ;). Recomiendo probar con los nodos que da el ejercicio para ver que queda como la figura. Un saludo :)

No hay comentarios:

Publicar un comentario