/*
 * FUNCIONES BÁSICAS DE MANEJO DE UN ARBOL BINARIO ORDENADO
 *
 *  Buscar, Anotar, Borrar, Rango, Recorridos
 *
 */

#include <stdio.h>
#include <stdlib.h>  // abs ( Valor absoluto )

typedef enum { FALSE, TRUE } boolean;
typedef short TipoDato;

// Estructura autoreferenciada
struct sarb {
       TipoDato valor;
       struct sarb *dcha;
       struct sarb *izda;
       };

typedef struct sarb Elemento;

Elemento *Raiz;

/* Funciones básicas */
// Busqueda Ordenada Interactiva, Recursiva, Si tener encuenta el orden
boolean  BuscarI  ( Elemento *parbol , TipoDato dato );
boolean  BuscarR  ( Elemento *parbol, TipoDato dato );
boolean  BuscarNoOrden ( Elemento *parbol, TipoDato dato );

// Recorridos
void     EnPreOrden  ( Elemento *parbol );
void     EnInOrden   ( Elemento *parbol );
void     EnPostOrden ( Elemento *parbol );

// Recorrido en InOrden pero mostrando el árbol gráficamente
void     VerArbol    ( Elemento *parbol, int nivel, char letra );


// Insertar y Borrar
Elemento *  Insertar     ( Elemento *parbol, TipoDato dato );
Elemento *  BorrarHoja   ( Elemento *parbol, TipoDato dato );
Elemento *  BorrarNodo   ( Elemento *parbol, TipoDato dato );

// Varios
TipoDato DifMaxMin ( Elemento *parbol );
int ContarNodos( Elemento *parbol );
int ContarHojas( Elemento *parbol );
int Profundidad( Elemento *Parbol );
boolean EstaEquilibrado ( Elemento *parbol );
boolean EstaOrdenado    ( Elemento *parbol );

/*
 * Busqueda de un elemento iterativamente
 */

boolean BuscarI ( Elemento *parbol , TipoDato dato )
{
  Elemento *paux;
  boolean encontrado = FALSE;

  paux = parbol;

  while (( paux != NULL ) && ( !encontrado ) )
    {
    if ( dato == paux->valor )
      {
      encontrado = TRUE;
      }
    else
      {
      if ( dato > paux->valor )
        {
        paux = paux->dcha;
        }
      else
        {
        paux = paux->izda;
        }
      }
    }

  return encontrado;
}

/*
 * Busqueda de un elemento de forma recursiva
 */

boolean BuscarR  ( Elemento *parbol, TipoDato dato )
{
  if ( parbol == NULL )
     {
     return FALSE;
     }
  else
     {
     if ( dato == parbol->valor )
       {
       return TRUE;
       }
     else
       {
        if ( dato > parbol->valor )
          {
           return  BuscarR(parbol->dcha,dato);
           }
         else
          {
          return  BuscarR(parbol->izda,dato);
         }
       }
     }
}

// Busca recursiva de un elemento sin tener en cuenta que
// el árbol está ordenado

boolean BuscarNoOrden ( Elemento *parbol, TipoDato dato )
{
  if ( parbol == NULL )
     {
     return FALSE;
     }
  else
     {
     if ( parbol->valor == dato )
        {
        return TRUE;
        }
     else
        {
        return BuscarNoOrden(parbol->dcha, dato ) ||
               BuscarNoOrden(parbol->izda, dato );
        }
     }
}

/*
 * Inserta ordenadamente un nuevo elemento en el árbol
 */

Elemento *  Insertar ( Elemento *parbol, TipoDato dato )
{
  Elemento *paux;

  paux = parbol;

  if ( paux == NULL )
    {
    paux = malloc ( sizeof ( Elemento ) );
    if ( paux != NULL )
        {
        paux->valor = dato;
        paux->dcha = NULL;
        paux->izda = NULL;
        }
     }
  else
     {
     if ( dato > paux->valor )
        {
        paux->dcha =  Insertar( paux->dcha,dato);
        }
     else
        {
        paux->izda = Insertar (paux->izda,dato);
        }
     }
  return paux;
}


/*
 * Devuelve el diferencia entre el valor máximo del arbol ( Más a la derecha)
 * y el  mínimo ( Más a la izquierda )
 */

TipoDato DifMaxMin ( Elemento *parbol )
{
  Elemento *pmax,*pmin;
  if ( parbol == NULL )
     {
     return 0;
     }
  pmax = parbol;
  while ( pmax->dcha != NULL )
  {
  pmax = pmax->dcha;
  }
  pmin = parbol;
  while ( pmin->izda != NULL )
  {
  pmin = pmin->izda;
  }
  return ( pmax->valor - pmin->valor);
}

/*
 Ejemplos de recorridos recursivos
 */

void EnPreOrden ( Elemento *parbol )
{
  if ( parbol != NULL )
     {
     printf( " %d,", parbol->valor);
     EnPreOrden(parbol->izda);
     EnPreOrden(parbol->dcha);
     }
}
/* ------------------------------------------- */
void EnInOrden ( Elemento *parbol )
{

  if ( parbol != NULL )
     {
     EnInOrden(parbol->izda);
     printf( " %d,", parbol->valor);
     EnInOrden(parbol->dcha);
     }
}
/* ------------------------------------------- */
void EnPostOrden ( Elemento *parbol )
{
  if ( parbol != NULL )
     {
     EnPostOrden(parbol->izda);
     EnPostOrden(parbol->dcha);
     printf( " %d,", parbol->valor);
     }
}

/*
 Orden central pero pasando el nivel para que
   quede bonito
 */
void VerArbol ( Elemento *parbol, int nivel , char letra)
{
  int i;

  if ( parbol != NULL )
     {
     VerArbol(parbol->dcha,nivel + 1,'/');
     for (i=0; i<nivel; i++)putchar('\t');
     printf( "%c----(%d)\n", letra, parbol->valor);
     VerArbol(parbol->izda,nivel + 1,'\\');
     }

}

/* ------------------------------------------- */

/*
 * Borra un elemento de un árbol
 SOLO SI ES UNA HOJA ( No tiene sucesores )
 */

Elemento * BorrarHoja ( Elemento *parbol, TipoDato dato )
{
  Elemento *paux;

  paux = parbol;
  if ( paux != NULL )
     {
     if ( paux->valor == dato )
       {
       if (( paux->dcha == NULL ) && ( paux->izda == NULL ))
          {
          free(paux);
          paux = NULL;
          }
        // Si no es una hoja no hace nada
        }
      else
        {
        // No es igual al valor busco por Dcha o Izda
        if ( dato > paux->valor )
           {
           paux->dcha = BorrarHoja(paux->dcha,dato);
           }
        else
           {
           paux->izda = BorrarHoja(paux->izda,dato);
           }
        }
     }
     // Devuelve paux si no lo encuentra o no puede borrarlo
   return paux;
}

/*
 * Borra cualquier nodo del arbol ( Solución poco optimizada )
 */

Elemento * BorrarNodo ( Elemento *parbol, TipoDato dato )
{
  Elemento *paux,*p,*pant;


  paux = parbol;

  // Si no esta vacio
  if ( paux != NULL )
     {
     // Si es el elemento a Borrar
     if ( paux->valor == dato )
       {
       p = paux;
       // Si es una hoja
       if (( paux->dcha == NULL ) && ( paux->izda == NULL ))
          {
          paux = NULL;
          }
       else // Si no es una hoja
          {
          if ( paux->dcha == NULL )
             {
             paux = paux->izda; // Si no hay nada por la dcha
             }
          else
             {
             if ( paux->izda == NULL )
                {
                paux = paux->dcha; // Si no hay nada por la izda
                }
             else
                { // Hay algo por la Izquierda y por la derecha
                // Busco el más grande de la izquierda
                pant = paux;
		p = paux->izda;
                while ( p->dcha != NULL )
                     {
                     pant = p;
                     p = p->dcha;
                     }
                // Cambio el valor del nodo para no reasignar punteros
                paux->valor = p->valor;
                if ( pant != paux )
                   {
                   pant->dcha = p->izda; // El anterior al resto por la izda
                   }
                else
                   {
                   paux->izda = p->izda; // Guardo la parte izquierda
                   }

                }
             }
           }
           free(p); // En cualquier caso elimino el Nodo

        }
      else
        {
        // No es igual al valor busco por Dcha o Izda
        if ( dato > paux->valor )
           {
           paux->dcha = BorrarNodo(paux->dcha,dato);
           }
        else
           {
           paux->izda = BorrarNodo(paux->izda,dato);
           }
        }
     }
     // Devuelve paux si no lo encuentra o no puede borrarlo
   return paux;
}

/* ------------------------------------------- */
/* Cuenta cuantas hojas tiene el árbol        */
/* ------------------------------------------- */
int ContarHojas ( Elemento *parbol )
{
  if ( parbol == NULL )
     {
     return 0;
     }
  else
     {
     if ( ( parbol->dcha == NULL ) &&
          ( parbol->izda == NULL ) )
       {
       return 1; // Es una hoja
       }
     else
       {
       return ContarHojas(parbol->dcha) +
              ContarHojas(parbol->izda);
       }
     }
}

/* ------------------------------------------- */
/* Cuenta cuantos nodos tiene el árbol         */
/* ------------------------------------------- */
int ContarNodos ( Elemento *parbol )
{
   if ( parbol == NULL )
      {
      return 0;
      }
   else
      {
      return 1 + ContarNodos(parbol->dcha)
               + ContarNodos(parbol->izda);
      }
}

/* ------------------------------------------- */
/* Calcula la profundidad que tiene el árbol   */
/* ------------------------------------------- */

int Profundidad ( Elemento *parbol )
{
  int prodcha, proizda;
  if ( parbol == NULL )
      {
      return 0;
      }
  prodcha = 1 + Profundidad(parbol->dcha);
  proizda = 1 + Profundidad(parbol->izda);
  // Devuelvo la mayor profundidad
  return ( prodcha > proizda )? prodcha:proizda;

}

/* ------------------------------------------- */
/* Comprueba si el árbol está o no equilibrado */
/* ------------------------------------------- */

boolean EstaEquilibrado ( Elemento *parbol )
{
  int diff; // Diferencia entre el número de nodos de subarbol izda y dcha
  if ( parbol == NULL )
     {
     return TRUE;
     }
  else
     {
     diff = ContarNodos(parbol->dcha) - ContarNodos (parbol->izda);
     if ( abs(diff ) > 1 )
        {
        return FALSE;
        }
     else
        { // Esta equilibrado si lo esta el subarbol dcho y el izdo
        return EstaEquilibrado(parbol->dcha) &&
               EstaEquilibrado(parbol->izda);
        }
     }
}

/* ------------------------------------------- */
/* Comprueba si el árbol está o no ordenado    */
/* ------------------------------------------- */

boolean EstaOrdenado    ( Elemento *parbol )
{
   if (parbol == NULL )
      {
      return TRUE;
      }
   // Pregunto por la izda
   if ( parbol->izda != NULL)
      {
      if (parbol->valor < parbol->izda->valor )
         return FALSE;
      }
    // Pregunto por la dcha
    if ( parbol->dcha != NULL )
        {
        if (parbol->valor > parbol->dcha->valor )
           return FALSE;
        }
      // Esta Ordenado si lo está el subárbol dcho y el izdo
      return EstaOrdenado(parbol->dcha) &&
             EstaOrdenado(parbol->izda);
}


/* -------------------------------------------------- */
/*  Prueba de las funciones básicas                    */
/* -------------------------------------------------- */

void main ()
{

  Elemento *Raiz;
  TipoDato dato;


  Raiz = NULL; // Inicializa el árbol

  Raiz = Insertar(Raiz,  20);
  Raiz = Insertar(Raiz,  28);
  Raiz = Insertar(Raiz,  16);
  Raiz = Insertar(Raiz,  18);
  Raiz = Insertar(Raiz,  12);
  Raiz = Insertar(Raiz, 140);
  Raiz = Insertar(Raiz,  25);
  Raiz = Insertar(Raiz,  15);
  Raiz = Insertar(Raiz,  75);
  Raiz = Insertar(Raiz, 130);
  Raiz = Insertar(Raiz,  22);
  Raiz = Insertar(Raiz,  17);
  Raiz = Insertar(Raiz,  79);

  puts("Arbol:");
  VerArbol(Raiz,0,'+');
  printf(" Número de Nodos = %d \n", ContarNodos(Raiz));
  printf(" Número de Hojas = %d \n", ContarHojas(Raiz));
  printf(" Profundidad     = %d \n", Profundidad(Raiz));
  printf(" Equibrado (%s) \n", (EstaEquilibrado(Raiz))?"SI":"NO" );
  printf(" Ordenado  (%s) \n", (EstaOrdenado(Raiz))?"SI":"NO");
  printf(" Difencia entre Max - Min: %d\n", DifMaxMin(Raiz) );
  getchar();


  puts("\nOrden Central:");
  EnInOrden(Raiz);
  puts("\nPost Orden :");
  EnPostOrden(Raiz);
  puts("\nPre Orden  :");
  EnPreOrden(Raiz);
  putchar('\n');

  if ( BuscarI (Raiz,28) ) puts (" Encontrado el 18 (I)");
  if ( BuscarI (Raiz,89) ) puts (" Encontrado el 89 ?? (I)");
  if ( BuscarR (Raiz,28) ) puts (" Encontrado el 18 (R)");
  if ( BuscarR (Raiz,89) ) puts (" Encontrado el 89 (R)??");
  if ( BuscarNoOrden (Raiz,28) ) puts (" Encontrado el 18 (Sin Orden)");
  if ( BuscarNoOrden (Raiz,89) ) puts (" Encontrado el 89 (Sin Orden)??");


  VerArbol(Raiz,0,'+');
  // Borro hasta que el árbol esté vacio.
  do {
      printf(" Nodo a borrar:"); scanf("%d",&dato);
      Raiz = BorrarNodo(Raiz, dato);
      VerArbol(Raiz,0,'+');
      }
  while ( Raiz != NULL );

}