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

typedef struct nodo{
	int dato;
	struct nodo *izq;
	struct nodo *der;
	} NODOARBOL;

NODOARBOL *raiz;

void insertar(NODOARBOL **cabeza, int elemento);
void inorder(NODOARBOL *cabeza), preorder(NODOARBOL *cabeza);
void postorder(NODOARBOL *cabeza);
NODOARBOL *eliminar(NODOARBOL *cabeza, int elemento);

void main(){
     char opcion;
     int elemento;
     NODOARBOL *borrado;
     clrscr();
     raiz=NULL;

     for(;;){
	 printf("(1) Insertar, (2) Eliminar, (3) Inorder, (4) Preorder, (5) Postorder, (6) Salir\n");
	 printf("Selecci¢n: ");

	 switch(opcion=getche()){
	 case '1':
	    printf("\nIngrese elemento a insertar: ");
	    scanf("%d", & elemento);
	    insertar(&raiz, elemento);
	    break;

	 case '2':
	    if(raiz==NULL){ printf("\nNo hay nodos en al arbol\n\n");
	    break; }

	    else{
		printf("\nIngrese dato a eliminar: ");
		scanf("%d", & elemento);
		borrado=eliminar( raiz, elemento);
		if(borrado==NULL) printf("\nDato no encontrado\n\n");
		break;
		}

	 case '3':
	     printf("\nEl arbol es: ");
	     inorder(raiz);
	     break;
	 case '4':
	     printf("\nEl arbol es: ");
	     preorder(raiz);
	     break;
	 case '5':
	     printf("\nEl arbol es: ");
	     postorder(raiz);
	     break;
	 }
	 printf("\n\n");
	 if(opcion=='6') break;
	 }
}

void insertar(NODOARBOL **cabeza, int elemento){

     if(*cabeza==NULL){
	*cabeza= (NODOARBOL *) malloc(sizeof(NODOARBOL));

	if(*cabeza==NULL){
	   printf("No hay memoria\n");
	   return;
	   }

	(*cabeza)->dato=elemento;
	(*cabeza)->izq=NULL;
	(*cabeza)->der=NULL;
       }

     else if(elemento< (*cabeza)->dato) insertar(& (*cabeza)->izq, elemento);

     else if(elemento> (*cabeza)->dato) insertar(& (*cabeza)->der, elemento);

     else printf("\nNo puede insertar: valor duplicado\n\n");

}

NODOARBOL *eliminar(NODOARBOL *cabeza, int elemento){
	     NODOARBOL *p, *p2;

	     if(elemento==cabeza->dato){
		if(cabeza->izq==cabeza->der){
		   free(cabeza);
		   return(NULL);
		}

		else if(cabeza->izq==NULL){
		   p=cabeza->der;
		   free(cabeza);
		   return(p);
		}

		else if(cabeza->der==NULL){
		   p=cabeza->izq;
		   free(cabeza);
		   return(p);
	       }

	       else{
		   p2=cabeza->der;
		   p=cabeza->der;
		   while(p->izq) p=p->izq;
		   p->izq=cabeza->izq;
		   free(cabeza);
		   return(p2);
	       }
	     }

	     if(cabeza->dato<elemento) cabeza->der=eliminar(cabeza->der, elemento);
	     else cabeza->izq=eliminar(cabeza->izq, elemento);
	     return(cabeza);
}


void inorder(NODOARBOL *cabeza){
     if(cabeza!=NULL){
	inorder(cabeza->izq);
	printf("%d ",cabeza->dato);
	inorder(cabeza->der);
     }
}

void preorder(NODOARBOL *cabeza){
     if(cabeza!=NULL){
	printf("%d ", cabeza->dato);
	preorder(cabeza->izq);
	preorder(cabeza->der);
     }
}

void postorder(NODOARBOL *cabeza){
     if(cabeza!=NULL){
	postorder(cabeza->izq);
	postorder(cabeza->der);
	printf("%d ",cabeza->dato);
     }
}