Árbol Binario de Búsqueda

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct nodo
{
   int numero;
      struct nodo *derecho;
      struct nodo *izquierdo;
   }*ptr;

void Insertar(ptr *nodo, int dato);
void Eliminar_nodo(ptr *a, int dato);
int Buscar(ptr nodo, int dato);
int EsHoja(ptr h);
int Num_Nodos(ptr nodo, int* c);
int Altura_Arbol(ptr nodo, int *altura);
int Nivel_Nodo(ptr nodo, int dat);
void InOrden(ptr nodo, void (*func)(int*));
void PreOrden(ptr nodo, void (*func)(int*));
void PostOrden(ptr nodo, void (*func)(int*));
void Eliminar_Arbol(ptr *nodo);
void auxContador(ptr nodo, int*);
void auxAltura(ptr nodo, int, int*);
void Mostrar(int *a);                                                                                                                                                                                                                                                                                                          
 int Vacio(ptr r);                                                                                                                                                                                                                          
int main()
{
   ptr Arbol = NULL;
 
   int i, num, ndatos, opcion;
 
   do
    {
     printf("\n");
     printf("\n****** arbol ********");
     printf("\n1. Insertar arbol   *");
     printf("\n2. Nivel nodo       *");
     printf("\n3. Buscar nodo      *");
     printf("\n4. Eliminar nodo    *");
     printf("\n5. Eliminar árbol   *");
     printf("\n6. Salir            *");
     printf("\n*********************");
  printf("\n\n\n");
   printf(" Elija opción    ");
     scanf("%d",&opcion);
     switch (opcion)
        {
            case 1:   system("cls");
           
                      printf("\n Indique cuantos datos desea insertar      ");
                     
                      scanf("%d",&ndatos);
                     
                      system("cls");
                     
                      printf("\n Introduzca %d datos\n\n", ndatos);
                     
                      for(i=1; i<=ndatos; i++)
                        {
                          scanf("%d",&num);
                         
                          Insertar(&Arbol, num);
                        }
                      system("cls");
                      printf("\n Numero nodos ----> %d ", Num_Nodos(Arbol, &num));
                     
                      printf("\n\n Altura arbol ----> %d ", Altura_Arbol(Arbol, &num));
                      printf("\n\n InOrden      ----> ");
                      InOrden(Arbol, Mostrar);
                      printf("\n\n PreOrden     ----> ");
                      PreOrden(Arbol, Mostrar);
                      printf("\n\n PostOrden    ----> ");
                      PostOrden(Arbol, Mostrar);
                      printf("\n\n\n\n\n\n\n\n");
                      system("pause");
                     
                      system("cls");
                      break;                                                                                                        
           case 2:   system("cls");
            printf("\n\n Introduzca nodo      ");
                      scanf("%d", &num);
                     
                      system("cls");
                     
                      printf("\n\n Nivel de %d  ---->  %d\n",num, Nivel_Nodo(Arbol, num));
                     
                      printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
                    system("cls");
                    break;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
          case 3:   system("cls");
            printf("\n Introduzca dato a buscar      ");
                  scanf("%d", &num);
                    system("cls");
                    Buscar(Arbol, num);
                    printf("\n\n\n\n\n\n\n\n");
                    system("PAUSE");
                    system("cls");
                    break;
        case 4:  system("cls");
printf("\n Introduzca dato a eliminar      ");
                scanf("%d", &num);
                   system("cls");
                   Eliminar_nodo(&Arbol, num);
                   printf("\n\n Eliminado    ----> %d  ",num);
                   printf("\n\n InOrden      ----> ");
                   InOrden(Arbol, Mostrar);
                    printf("\n\n Número nodos ----> %d", Num_Nodos(Arbol, &num));
                    printf("\n\n Altura árbol ----> %d", Altura_Arbol(Arbol, &num));
                   printf("\n\n\n\n\n\n\n\n");
                    system("PAUSE");
                    system("cls");
                    break;
    case 5:  system("cls");
            Eliminar_Arbol(&Arbol);
                    printf("\n ARBOL ELIMINADO");
                    printf("\n\n\n\n\n\n\n\n");
                    system("PAUSE");
                    system("cls");
                    break;
        case 6:  break;
         
          default:  system("cls");
         
                    break;
           }
     } while (opcion!=6);
   
    return 0;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
  }
 int Vacio(ptr r)
{
   return r==NULL;
}
void Insertar(ptr *a, int dato){
   ptr padre = NULL;
   ptr actual = *a;
   while(!Vacio(actual) && dato != actual->numero) {
      padre = actual;
      if(dato < actual->numero)
      actual = actual->izquierdo;
      else if(dato > actual->numero)
      actual = actual->derecho;
   }
   if(!Vacio(actual))
   return;
   if(Vacio(padre)) {
      *a = (ptr)malloc(sizeof(struct nodo));
      (*a)->numero = dato;
      (*a)->izquierdo = (*a)->derecho = NULL;
   }
   else if(dato < padre->numero) {
      actual = (ptr)malloc(sizeof(struct nodo));
      padre->izquierdo = actual;
      actual->numero = dato;
      actual->izquierdo = actual->derecho = NULL;
   }
   else if(dato > padre->numero) {
      actual = (ptr)malloc(sizeof(struct nodo));
      padre->derecho = actual;
      actual->numero = dato;
      actual->izquierdo = NULL;
      actual->derecho = NULL;
  }
}
void Eliminar_nodo(ptr *a, int dato){
   ptr padre = NULL;
   ptr actual;
   ptr nodo;
   int aux;
   actual = *a;
   while(actual!=NULL) {
      if(dato == actual->numero) {
         if(EsHoja(actual)) {
            if(padre)
              if(padre->derecho == actual)
              padre->derecho = NULL;
              else if(padre->izquierdo == actual)
              padre->izquierdo = NULL;
            free(actual);
            actual = NULL;
           
         }else {
            padre = actual;
            if(actual->derecho) {
               nodo = actual->derecho;
               while(nodo->izquierdo) {
                  padre = nodo;
                  nodo = nodo->izquierdo;}
            }else {
               nodo = actual->izquierdo;
               while(nodo->derecho) {
                  padre = nodo;
                  nodo = nodo->derecho;}
            }
            aux = actual->numero;
            actual->numero = nodo->numero;
            nodo->numero = aux;
            actual = nodo;}
      }else {
         padre = actual;
         if(dato > actual->numero)
         actual = actual->derecho;
         else if(dato < actual->numero)
         actual = actual->izquierdo;}
   }
}
                                                                                                                 
void InOrden(ptr nodo, void (*func)(int*))
{
   if(nodo->izquierdo)
 
     InOrden(nodo->izquierdo, func);
   
   func(&(nodo->numero));
 
   if(nodo->derecho)
 
     InOrden(nodo->derecho, func);
}
void PreOrden(ptr nodo, void (*func)(int*))
{
   func(&nodo->numero);
 
   if(nodo->izquierdo)
 
     PreOrden(nodo->izquierdo, func);
   
   if(nodo->derecho)
 
     PreOrden(nodo->derecho, func);
}
void PostOrden(ptr nodo, void (*func)(int*))
{
   if(nodo->izquierdo)
 
     PostOrden(nodo->izquierdo, func);
   
   if(nodo->derecho)
 
     PostOrden(nodo->derecho, func);
   
   func(&nodo->numero);
}                                                                                      

int Buscar(ptr nodo, int dato)
{
   ptr actual = nodo;
 
   while(actual!= NULL)
   {
      if(dato == actual->numero)
      {
        printf("\n %d  EXISTE", dato);
     
        return TRUE;
      }
      else if(dato < actual->numero)
     
        actual = actual->izquierdo;
       
      else if(dato > actual->numero)
     
        actual = actual->derecho;
   }
    printf("\n %d  NO EXISTE", dato);
   
    return FALSE;                                                                                          
}

int Nivel_Nodo(ptr nodo, int dato)
{
   int altura = 0;
 
   ptr actual = nodo;
 
   while(actual != NULL)
     {
      if(dato == actual->numero)
     
        return altura;
       
      else {
         altura++;
         
         if(dato < actual->numero)
       
           actual = actual->izquierdo;
         
         else if(dato > actual->numero)
       
           actual = actual->derecho;
      }
   }
   return -1;                                                                                                                                                                            
}                                                                                                          

void auxContador(ptr nodo, int *c)
{
   (*c)++;
 
   if(nodo->izquierdo)
 
     auxContador(nodo->izquierdo, c);
   
   if(nodo->derecho)
 
     auxContador(nodo->derecho, c);
}

int Num_Nodos(ptr nodo, int *cont)
{
   *cont = 0;
 
   auxContador(nodo, cont);
 
   return *cont;
}
void auxAltura(ptr nodo, int a, int *altura)
{
   if(nodo->izquierdo)
 
     auxAltura(nodo->izquierdo, a+1, altura);
   
   if(nodo->derecho)  
 
     auxAltura(nodo->derecho, a+1, altura);
   
   if(EsHoja(nodo) && a > *altura)
 
     *altura = a;
}


int Altura_Arbol(ptr nodo, int *altura)
{
   *altura = 0;
 
    auxAltura(nodo, 0, altura);
   
    return *altura;
}                                                                                                          


void Eliminar_Arbol(ptr *nodo)
{
   if(*nodo)
   {
      Eliminar_Arbol(&(*nodo)->izquierdo);
     
      Eliminar_Arbol(&(*nodo)->derecho);
     
      free(*nodo);  
     
      *nodo = NULL;
   }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
}                                                                                                                                                              
                                                                                                             
int EsHoja(ptr nodo)
{
   return !nodo->derecho && !nodo->izquierdo;
}
int comparar(int a,int b)
{
    if(a > b)
   
        return 1;
       
    if(a < b)
   
        return -1;
       
    return 0;
}
void Mostrar(int *a)
{
   printf("%d, ", *a);
}

Árbol Binario de Búsqueda Ejercicios

1) En base al proceso descrito con anterioridad, inserte en un ABB los números: 9, 18, 10, 2, 6, 21, 8, 1, 7.

2) Construir un ABB con las claves 50, 25, 75, 10, 40, 60, 90, 35, 45, 70, 42. 

3) Construir un ABB a partir de las claves 10, 75, 34, 22, 64, 53, 41, 5, 25, 74, 20, 15, 90.

4) El recorrido en postorden de un ABB que contiene caracteres es:       DMLCTAISRUNOKB    Y en inorden es:       DMATLCBIKUSRON   

A) Dibujar el árbol binario. 

 B) Dar el recorrido en preorden.

Árboles Binarios de Búsqueda

Árboles binarios de búsqueda

La principal característica es que la información se almacena en los nodos cuidando de mantener cierto orden.

Formalmente se define un árbol binario de búsqueda de la siguiente manera:
Para todo nodo T del árbol se debe cumplir que todos los valores almacenados en el subárbol izquierdo de T sean menores o iguales a la información guardada en el nodo T. De forma similar, todos los valores almacenados en el subárbol derecho de T deben ser mayores a iguales a la información guardada en el nodo T.

El árbol binario de búsqueda es una estructura de datos sobre la cual se puede realizar eficientemente las operaciones de búsqueda, insercion y eliminación. Comparando esta estructura con otras, se pueden observar ciertas ventajas.
Por ejemplo, en un arreglo es posible localizar datos eficientemente si estos se encuentran ordenados, pero las operaciones de insercion y eliminación resultan costosas, porque involucran movimiento de los elementos dentro del arreglo.
En las listas, por otra parte, dichas operaciones se pueden llevar a cabo con facilidad, pero la operación de búsqueda, en este caso es una operación que demanda recursos, pudiendo incluso requerir recorrer todos los elementos de ella para llegar a uno en particular.






ESPACIO PARA IMAGEN DE UN ÁRBOL





Búsqueda
La operación de búsqueda en un árbol binario de búsqueda es mucho mas eficiente que en un árbol binario general, ya que al comparar el valor buscado con la información  del nodo visitado, si no es igual, se debe continuar solo por alguno de los dos subárboles.

Inserción en un árbol binario de búsqueda es una operación que se puede realizar eficientemente en este tipo de estructura de datos. La estructura crece conforme se insertan elementos al árbol. Los pasos que se deben realizar para agregar un nuevo nodo de un árbol de búsqueda son las siguientes:

1.- Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el subárbol derecho. Si es menor, se continua con el subárbol izquierdo.
2.- Repetir sucesivamente el paso 1 hasta que se cumpla algunas de las siguientes condiciones:
2.1 .- El subárbol derecho, o el subárbol izquierdo, es igual a vació, en cuyo caso procederá a insertar el elemento en el lugar que le corresponde.
2.2 La clave que se quiere insertar esta en el nodo analizado, por lo tanto no se lleva a cabo la insercion. Este caso es valido solo cuando la aplicación exige que no se repitan elementos.


ELIMINACIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA.
La operación de eliminación en un árbol binario de búsqueda es un poco mas complicada que la de inserción. Esta consiste en eliminar un nodo sin violar los principios que define un árbol binario de búsqueda. se deben distinguir los siguientes casos:
1.- Si el elemento es terminal u hoja, simplemente se suprime redefiniendo el puntero de su predecesor.
2.- Si el elemento a eliminar tiene un solo descendiente, entonces tiene que sustituirse por ese descendiente.
3.- Si el elemento a eliminar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra mas a la derecha en el subárbol izquierdo.
Cabe destacar que antes de eliminar un nodo, se debe localizar este en el árbol. Para esto se utiliza el algoritmo de búsqueda presentado anteriormente.