Horario

Mañana la clase de 12:00 a 13:00 Hrs en el lab-07 cualquier cambio les aviso

Á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.

Código para Grafo

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct nodo{
            char nombre[2];//nombre del vertice o nodo
            struct nodo *sgte;
            struct arista *ady;//puntero hacia la primera arista del nodo
            };
struct nodo *primero=NULL, *ultimo=NULL;
struct arista{
              struct nodo *destino;//puntero al nodo de llegada
              struct arista *sgte;
              };
void insertar_nodo();
void insertar_arista();
void vaciar_aristas();
void eliminar_nodo();
void eliminar_arista();
void mostrar_grafo();
void mostrar_aristas();
void visualizar();

main  (){
 int opcion;
 do{

  printf("\n\n\n");
  printf("\n****************************************");
  printf("\n*******************GRAFO****************");
  printf("\n\n");
  printf("\n1. Insertar un nodo");
  printf("\n2. Insertar un arista");
  printf("\n3. Eliminar un nodo");
  printf("\n4. Eliminar una arista");
  printf("\n5. Mostrar grafo");
  printf("\n6. Mostrar aristas de un nodo");
  printf("\n7. Salir");
  printf("\n8. visualizar nodo");
  printf("\n****************************************\n");
  printf("Ingresar opcion");
  scanf("%d", &opcion);

 
     switch(opcion){
    case 1: insertar_nodo();
                    break;
            case 2: insertar_arista();
                    break;
            case 3: eliminar_nodo();
                    break;
            case 4: eliminar_arista();
                    break;
            case 5: mostrar_grafo();
                    break;
            case 6: mostrar_aristas();
                    break;
            case 7: printf("Salir");
break;
case 8: visualizar ();
break;
default: system("pause");
break;
 
   }
  }
   while (opcion !=8);
}
void insertar_nodo(){
struct nodo *nuevo;
nuevo=(struct nodo*)malloc(sizeof(struct nodo));
if (nuevo == NULL)
printf("\n Memoria insuficiente");
else{
printf("\nINGRESE NODO: ");
    scanf("%s", nuevo->nombre);
       nuevo->sgte = NULL;
    nuevo->ady=NULL;}
 
    if(primero==NULL)
     {
        printf("PRIMER NODO...!!!");
primero = nuevo;
        ultimo = nuevo;
       
      }
    else
     {
      nuevo->sgte=NULL;
ultimo->sgte=nuevo;
ultimo=nuevo;
           while(ultimo->sgte!=NULL)
         {
            ultimo = ultimo->sgte;
          }
     
        printf("NODO INGRESADO...!!!");
      }

 }

 void visualizar(){

struct nodo *actual;
actual=primero;
if(actual==NULL){
printf("\nGrafo vacio");}
else{

while(actual!=NULL){
printf("%s\n",actual->nombre);
actual=actual->sgte;
}}
printf("\n\n\n");
system("pause");
}


/*INSERTAR ARISTA---------------------------------------------------------------------*/
void insertar_arista()
{   char ini[2], fin[2];
    struct arista *nuevo, *q;
    struct nodo *aux, *aux2;
 nuevo=(struct arista*)malloc(sizeof(struct arista));
    if(primero==NULL)
     {
         printf("GRAFO VACIO...!!!!");
         return;
     }else{

    nuevo->sgte=NULL;
    printf("\nINGRESE NODO DE INICIO:");
    scanf("%s", &ini);
    printf("\nINGRESE NODO FINAL:");
    scanf("%s", &fin);
    aux=primero;
    aux2=primero;
    }
    while(aux2!=NULL){
    if(strcmp(fin, aux2->nombre)==0)
        {
          break;
        }else{
         aux2=aux2->sgte;}
    }
    while(aux!=NULL)
    {
   
        if(strcmp(ini, aux->nombre)==0)
        {
    if(aux->ady==NULL)
    {   aux->ady=nuevo;
        nuevo->destino=aux2;
        printf("PRIMERA ARISTA....!");
}
    else
    {  
q=aux->ady;
  while(q->sgte!=NULL)
            q=q->sgte;
        nuevo->destino=aux2;
        q->sgte=nuevo;
        printf("ARISTA AGREGADA...!!!!");
             
    }
    return;
        }

        aux = aux->sgte;
    }
}
 
void eliminar_nodo(){
char var[2];
    struct nodo *aux,*ant;
    aux=primero;
    printf("ELIMINAR UN NODO\n");
    if(primero==NULL)
     {
         printf("GRAFO VACIO...!!!!");
         return;
     }
    printf("INGRESE NOMBRE DE VARIABLE:");
    scanf("%s",var);

    while(aux!=NULL)
    {
        if(strcmp(var, aux->nombre)==0)
        {
            if(aux->ady!=NULL)
                vaciar_aristas();

            if(aux==primero)
            {

                    primero=primero->sgte;
                    free(aux);
                    printf("NODO ELIMINADO...!!!!");
                    return;
             }
            else
            {
                ant->sgte = aux->sgte;
                free(aux);
                printf("NODO ELIMINADO...!!!!");
                return;
            }
        }
        else
        {
            ant=aux;
            aux=aux->sgte;
         }
    }
}
void eliminar_arista(){
char ini[2], fin[2];
    struct nodo *aux, *aux2;
    struct arista *q,*r;
    printf("\n ELIMINAR ARISTA\n");
    printf("INGRESE NODO DE INICIO:");
    scanf("%s",ini);
    printf("INGRESE NODO FINAL:");
    scanf("%s", fin);
    aux=primero;
    aux2=primero;
    while(aux2!=NULL)
    {
        if(strcmp(fin, aux2->nombre)==0)
        {
            break;
        }
        else
        aux2=aux2->sgte;
    }
     while(aux!=NULL)
    {
        if(strcmp(ini, aux->nombre)==0)
        {
            q=aux->ady;
            while(q!=NULL)
            {
                if(q->destino==aux2)
                {
                    if(q==aux->ady)
                        aux->ady=aux->ady->sgte;
                    else
                        r->sgte=q->sgte;
                    free(q);
                    printf("ARISTA  ", aux->nombre, "----->", aux2->nombre, " ELIMINADA.....!!!!");
                    return;
                }
            }
            r=q;
            q=q->sgte;
        }
        aux = aux->sgte;
    }
}
void mostrar_grafo(){
struct nodo *ap;
    struct arista *ca;
    ap=primero;
    printf("NODO|LISTA DE ADYACENCIA\n");
   while(ap!=NULL){
printf("%s| ", ap->nombre);
if(ap->ady!=NULL)
        {
ca=ap->ady;
while(ca!=NULL)
            {  
printf("%s ",ca->destino->nombre);
                ca=ca->sgte; }        }
        ap=ap->sgte;
        printf("\n");}
}
void mostrar_aristas(){
struct nodo *aux;
    struct arista *ar;
    char var[2];
    printf("MOSTRAR ARISTAS DE NODO\n");
    printf("INGRESE NODO:");
    scanf("%s",var);
  aux=primero;
    while(aux!=NULL)
    {
        if(strcmp(var, aux->nombre)==0)
        {
            if(aux->ady==NULL)
            {   printf("EL NODO NO TIENE ARISTAS...!!!!");
                return;
             }
            else
            {
                printf("NODO|LISTA DE ADYACENCIA\n");
                printf("%s  | ",aux->nombre);
                ar=aux->ady;
                while(ar!=NULL)
                {
                    printf(ar->destino->nombre,"  ");
                    ar=ar->sgte;
                                  }
             
                return;
            }
        }
        else
        aux=aux->sgte;
    }
}
void vaciar_aristas(){
struct arista *q,*r;
struct nodo *aux;
aux=primero;
    q=aux->ady;
    while(q->sgte!=NULL)
    {
        r=q;
        q=q->sgte;
        free(r);
    }

Apuntes Arboles

Realizar un resumen del Capitulo 6 Arboles desde la Pág. 176  hasta la pág. 179

Algoritmo de Floyd

#include<stdio.h>
#include<conio.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
 int i,j,k;
 for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    if(i==j)
     p[i][j]=0;
    else
     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
 if(a<b)
  return(a);
 else
  return(b);
}
main()
{
 int p[10][10],w,n,e,u,v,i,j;;
 //clrscr();
 printf("\n Introduce el numero de vertices:");
 scanf("%d",&n);
 printf("\n Introduce el número de aristas:\n");
 scanf("%d",&e);
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   p[i][j]=999;
 }
 for(i=1;i<=e;i++)
 {
  printf("\n Introduzca los vértices finales de primera línea %d con suetiqueta de costo \n",i);
  scanf("%d%d%d",&u,&v,&w);
  p[u][v]=w;
 }
 printf("\n Matriz de datos de entrada:\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d \t",p[i][j]);
  printf("\n");
 }
 floyds(p,n);
 printf("\nClausura transitiva:\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d \t",p[i][j]);
  printf("\n");
 }
 printf("\nLas rutas más cortas son:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
   if(i!=j)
    printf("\n <%d,%d>=%d",i,j,p[i][j]);
  }
 getch();
}