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

typedef enum { FALSE, TRUE } boolean;

typedef struct tarbol
{
  int clave;
  struct tarbol *izq;
  struct tarbol *der;
} tarbol;

void crear(tarbol **a);
boolean buscar(tarbol *a, int elem);
void insertar(tarbol **a, int elem);
void borrar(tarbol **a, int elem);


int main(void)
{
  tarbol *a;

  crear(&#038;a);
  insertar(&#038;a, 5);
  insertar(&#038;a, 2);
  insertar(&#038;a, 4);
  insertar(&#038;a, 3);
  insertar(&#038;a, 6);

  borrar(&#038;a, 5);
  borrar(&#038;a, 4);
  borrar(&#038;a, 3);

  return 0;
}

void crear(tarbol **a)
{
  *a = NULL;
}

boolean buscar(tarbol *a, int elem)
{
  if (a == NULL) return FALSE;
  else if (a->clave < elem) return buscar(a->der, elem);
  else if (a->clave > elem) return buscar(a->izq, elem);
  else return TRUE;
}

void insertar(tarbol **a, int elem)
{
  if (*a == NULL) {
    *a = (tarbol *) malloc(sizeof(tarbol));
    (*a)->clave = elem;
    (*a)->izq = (*a)->der = NULL;
  }
  else if ((*a)->clave < elem) insertar(&#038;(*a)->der, elem);
  else if ((*a)->clave > elem) insertar(&#038;(*a)->izq, elem);
}

void borrar(tarbol **a, int elem)
{
  void sustituir(tarbol **a, tarbol **aux);
  tarbol *aux;

  if (*a == NULL)   /* no existe la clave */
    return;

  if ((*a)->clave < elem) borrar(&#038;(*a)->der, elem);
  else if ((*a)->clave > elem) borrar(&#038;(*a)->izq, elem);
  else if ((*a)->clave == elem) {
    aux = *a;
    if ((*a)->izq == NULL) *a = (*a)->der;
    else if ((*a)->der == NULL) *a = (*a)->izq;
    else sustituir(&#038;(*a)->izq, &#038;aux); /* se sustituye por la mayor de las menores */

    free(aux);
  }
}

void sustituir(tarbol **a, tarbol **aux)
{
  if ((*a)->der != NULL) sustituir(&#038;(*a)->der, aux);
  else {
    (*aux)->clave = (*a)->clave;
    *aux = *a;
    *a = (*a)->izq;
  }
}