#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <iostream.h>
#include <alloc.h>
#include <stdlib.h>

struct nodo {
    int dato;
    struct nodo *padre;
    struct nodo *hi;
    struct nodo *hd;
};

int ARBOL_VACIO (struct nodo *);
void INI_ARBOL (struct nodo **);
void INS_ARBOL (struct nodo **, int);
int PROFUNDIDAD (struct nodo *);
void ELIMINAR_NODO (struct nodo **, struct nodo *);
void LISTAR_IRD(struct nodo *);
struct nodo* BUSCAR_NODO(struct nodo*,int);

void main (void) {

  int d;

  struct nodo *arbol;

  INI_ARBOL(&arbol);


    clrscr();

    while (d!=0){
      printf ("\nNumero: ");
      cin >> d;
      if (d!=0)
	INS_ARBOL(&arbol, d);
    }
    printf("Presione ENTER para continuar, ESC finaliza.\n");
    printf ("\nListado del  rbol:");
    printf ("\n------------------\n");
    LISTAR_IRD(arbol);
    printf ("\n------------------\n");
    cout << "\nLa profundidad del  rbol es " << PROFUNDIDAD(arbol);
    printf("\nLado Izquierdo-> %d", PROFUNDIDAD(arbol->hi));
    printf("\tLado Derecho-> %d", PROFUNDIDAD(arbol->hd));
    printf("\n Raiz: %d",arbol->dato);getch();
    getch();
    int victima;
    while (!ARBOL_VACIO(arbol)) {
    printf("\nIntroduce un nodo a eliminar: ");

    cin >> victima;
    ELIMINAR_NODO(&arbol,BUSCAR_NODO(arbol,victima));
    printf ("\nListado del  rbol:");
    printf ("\n------------------\n");
    LISTAR_IRD(arbol);
    printf ("\n------------------\n");
    cout << "\nLa profundidad del  rbol es " << PROFUNDIDAD(arbol);
    printf("\nLado Izquierdo-> %d", PROFUNDIDAD(arbol->hi));
    printf("\tLado Derecho-> %d", PROFUNDIDAD(arbol->hd));

    if (arbol!=NULL)
      printf("\n Raiz: %d",(arbol->dato));getch();



    getch();
    }

  free (arbol);
}




int ARBOL_VACIO(struct nodo *p) {
  return (p == NULL);
  }

void INI_ARBOL(struct nodo **p) { *p = NULL; }

void INS_ARBOL(struct nodo **p, int n) {
  struct nodo *aux;
  struct nodo **q;
  int sw;

  if ((aux = (struct nodo*) malloc (sizeof (struct nodo)))== NULL)
    exit(1);
  aux->dato = n;

  if (ARBOL_VACIO(*p)) {
    aux->hi = NULL;
    aux->hd = NULL;
    aux->padre = aux;
    *p = aux;
  }
  else {
    sw = 1;
    q = p;
    while (sw) {
      sw = 0;
      if ((*q)->dato <= n && (*q)->hd != NULL) {
	  q = &(*q)->hd;
	  sw = 1;
      }
      if ((*q)->dato >= n && (*q)->hi != NULL) {
	  q = &(*q)->hi;
	  sw = 1;
      }
    }
    aux->hi = aux->hd = NULL;
    aux->padre = (*q);
    ((*q)->dato < n) ? (*q)->hd = aux : (*q)->hi = aux;
 }
}


int PROFUNDIDAD(struct nodo *p) {
  int nivelhi=0;
  int nivelhd=0;
  if (p != NULL) {
     nivelhi++;
     nivelhi+=PROFUNDIDAD(p -> hi);
     nivelhd++;
     nivelhd+=PROFUNDIDAD(p -> hd);
  }
     return (nivelhd > nivelhi) ? nivelhd : nivelhi;
}


void ELIMINAR_NODO (struct nodo **p, struct nodo *q) {
  if (q==NULL)
    printf("Error. Se ha intentado eliminar un nodo NO EXISTENTE.");
  else {
    if (q->hd == NULL && q->hi == NULL && q->padre != q) { // ES HOJA
      if ((q->padre)->hd == q)
	(q->padre)->hd = NULL; // ES UN HD
      else
	(q->padre)->hi = NULL; // ES UN HI
    } // fin del if si es hoja
    else {
      if ((q->padre) == q && q->hd == NULL && q->hi == NULL)// RAIZ SIN HIJOS
	*p = NULL;
      else {
	if (q->hd != NULL && q->hi == NULL) {// NO TIENE HI
	  if (q->padre==q)
	      *p=q->hd;
	  else
	    if ((q->padre)->hd == q) // ES UN HD
	      (q->padre)->hd = q->hd;
	    else
	      (q->padre)->hi = q->hd; // ES UN HI
	} // fin del if no tiene HI
	else {
	  if (q->hd == NULL && q->hi != NULL) {// NO TIENE HD
	    if (q->padre==q)
	      *p=q->hi;
	    else
	      if ((q->padre)->hd == q)
		(q->padre)->hd = q->hi;
	      else
		(q->padre)->hi = q->hi;
	  } // fin del if no tiene hd
	  else {
	    if (q->hd != NULL && q->hi != NULL){ //TIENE 2 HIJOS
	      struct nodo *aux = NULL;
	      if (PROFUNDIDAD(q->hi) > (PROFUNDIDAD (q->hd))) {
		aux=q->hi;
		while (aux->hd != NULL) {aux = aux->hd;}
	      }
	      else {
		aux=q->hd;
		while (aux->hi != NULL) {aux = aux->hi;}
	      }
	      struct nodo *nodotmp = NULL;
	      if ((nodotmp = (struct nodo*) malloc (sizeof (struct nodo)))==NULL){
		printf ("\nError Memory Allocation !!");
		printf ("\nNo hay memoria suficiente, abortando ...");
		exit(1);
	      }

	      nodotmp->dato = aux->dato;

	      if (q->hd == aux)
		nodotmp->hd = aux->hd;
	      else
		nodotmp->hd = q->hd;

	      if (q->hi == aux)
		nodotmp->hi = aux->hi;
	      else
		nodotmp->hi = q->hi;

	      if ((q->padre)==q){ // ES RAIZ
		*p = nodotmp;
		nodotmp->padre=nodotmp;
		}
	      else
		if ((q->padre)->hd == q) {// ES UN HD
		  (q->padre)->hd = nodotmp;
		  nodotmp->padre=q->padre;
		}
		else {
		  (q->padre)->hi = nodotmp; // ES UN HI
		  nodotmp->padre=q->padre;
		}

	      ELIMINAR_NODO(p, aux);

	    } // fin del if
	  } // fin del else
	} // fin del else
      } // fin del else
    } // fin del else
  } // fin del else
 free (q);
} // fin de la funcion eliminar_nodo


void LISTAR_IRD(struct nodo *p){
  if (p!=NULL){
    LISTAR_IRD(p->hi);
    printf("%d ",p->dato);
    LISTAR_IRD(p->hd);
  }
}

struct nodo* BUSCAR_NODO(struct nodo *p,int n){
  if (p==NULL || n==p->dato)
    return p;
  else
    if (n<p->dato)
      return (BUSCAR_NODO(p->hi,n));
    else
      return (BUSCAR_NODO(p->hd,n));
}