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

#ifdef PALINUX
#include <curses.h> 
#define  gotoxy(A,B)   (move(B,A))
#define  putch(A)      (addch(A), refresh()) 
#define  cprintf       printw
#define  cscanf        scanw
#define  clrscr        erase
#else
#include <conio.h>
#include <alloc.h>
#endif

typedef int TipoDato;
typedef enum {FALSO,CIERTO} logico;

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

typedef struct sarb Elemento;

Elemento *Raiz;

// Muestra gráficamente el contenido de un árbol binario
void     VerArbolH    ( Elemento *parbol, int nivel, char letra);
void     VerArbolV    ( Elemento *parbol, int x, int y ,int varx, char letra);


// Insertar y Borrar
Elemento *  Insertar     ( 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 );
logico EstaEquilibrado ( Elemento *parbol );
logico EstaOrdenado    ( Elemento *parbol );


/*
 * 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;
}


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

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

}

void VerArbolV ( Elemento *parbol, int x, int y, int varx ,char letra)
{
 int i;

 if ( parbol != NULL )
    {
    gotoxy(x,y),putch(letra);
    if ( letra == '/') /* Pinto los /--------- */
       {
       for (i=x+1;i<(x+varx);i++ ) {gotoxy(i,y); putch('-');}
       }
    if ( letra == '\\') /* Pinto ----------\  */
       {
       for (i=x-1;i>(x-varx);i-- ) {gotoxy(i,y); putch('-');}
       }
    /* Pinto el valor del nodo */
    gotoxy(x,y+1),putch('|');
    gotoxy(x-1,y+2);cprintf("(%d)",parbol->valor);

    /* Si no es una hoja  pinto el + */
    if ( (parbol->dcha != NULL) || (parbol->izda != NULL))
       {
       gotoxy(x,y+3),putch('+');
       }
    /* Pinto cada uno de los subarboles */
    VerArbolV(parbol->izda,x-varx/2,y+3,varx/2,'/');
    VerArbolV(parbol->dcha,x+varx/2,y+3,varx/2,'\\');
    }
}


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


/*
 * 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);
       }
     }
}


/*
 * 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);
}


/* ------------------------------------------- */
/* 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 */
/* ------------------------------------------- */

logico EstaEquilibrado ( Elemento *parbol )
{
  int diff; // Diferencia entre el número de nodos de subarbol izda y dcha
  if ( parbol == NULL )
     {
     return CIERTO;
     }
  else
     {
     diff = ContarNodos(parbol->dcha) - ContarNodos (parbol->izda);
     if ( abs(diff ) > 1 )
        {
        return FALSO;
        }
     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    */
/* ------------------------------------------- */

logico EstaOrdenado    ( Elemento *parbol )
{
   if (parbol == NULL )
      {
      return CIERTO;
      }
   // Pregunto por la izda
   if ( parbol->izda != NULL)
      {
      if (parbol->valor < parbol->izda->valor )
         return FALSO;
      }
    // Pregunto por la dcha
    if ( parbol->dcha != NULL )
        {
        if (parbol->valor > parbol->dcha->valor )
           return FALSO;
        }
      // 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                    */
/* -------------------------------------------------- */

int main ()
{

  Elemento *Raiz;
  TipoDato dato;
  char letra;

  

  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,  38);
  Raiz = Insertar(Raiz,   2);
  Raiz = Insertar(Raiz, 130);
  Raiz = Insertar(Raiz,  20);
  Raiz = Insertar(Raiz,  14);
  Raiz = Insertar(Raiz,  17);
  Raiz = Insertar(Raiz,  27);
  Raiz = Insertar(Raiz, 150);

#ifdef PALINUX
  initscr(); // Inicio de la curses
#endif


  // Borro hasta que el árbol esté vacio.
  
  do
    {
      clrscr();
      VerArbolV(Raiz,40,1,40,'+');
      gotoxy(1,18);
      cprintf("N. de Nodos = %d \n", ContarNodos(Raiz));
      cprintf(" N.de Hojas  = %d \n", ContarHojas(Raiz));
      cprintf(" Profundidad = %d \n", Profundidad(Raiz));
      cprintf(" Equibrado (%s) \n", (EstaEquilibrado(Raiz))?"SI":"NO" );
      cprintf(" Ordenado  (%s) \n", (EstaOrdenado(Raiz))?"SI":"NO");
      cprintf(" Diferencia entre Max - Min: %d\n", DifMaxMin(Raiz) );
      gotoxy(1,1);
      cprintf(" (I)nsertar  (B)orrar   (F)in  :"); letra=toupper(getch());
      if (letra == 'B')
	   {
            cprintf("\n  Nodo a borrar:"); cscanf("%d",&dato);
            Raiz = BorrarNodo(Raiz, dato);
	   }
      if (letra == 'I')
	   {
            cprintf("\n  Nodo a insertar:"); cscanf("%d",&dato);
            Raiz = Insertar(Raiz, dato);
	   }
      }
  while ( letra != 'F');

  clrscr();
#ifdef PALINUX
  endwin();
#endif

}