using namespace std;

struct NODO{
	int dato;
	struct NODO *izq;
	struct NODO *der;
};

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

int main()
{
   char opcion;
   int elemento;
   NODO *borrado, *raiz;
   clrscr();
   crearArbol(&raiz);
   //raiz=NULL;
   
   for(;;){
      system("cls");
      printf("\tARBOLES BINARIOS DE BUSQUEDA\n\n");
      printf("(0) SALIR\n(1) Insertar\n(2) Eliminar\n(3) Inorder\n(4) Preorder\n(5) Postorder\n");
      printf("\n\tDigite su opcion ---> ");
      
      switch(opcion=getche()){
         case '0':
            exit(0);
         case '1':
            system("cls");
            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':
            system("cls");
            printf("\nEl arbol es: ");
            inorder(raiz);
            system("pause");
            break;
         case '4':
            system("cls");
            printf("\nEl arbol es: ");
            preorder(raiz);
            break;
         case '5':
            system("cls");
            printf("\nEl arbol es: ");
            postorder(raiz);
            break;
      }
      printf("\n\n");
   }


   system("pause");
   return(0);
}
void crearArbol(NODO **cabeza)
{
   *cabeza=NULL;   
}
void insertar(NODO **cabeza, int elemento)
{

   if(*cabeza==NULL){
      *cabeza= (NODO *) malloc(sizeof(NODO));
      
      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");

}

NODO *eliminar(NODO *cabeza, int elemento)
{
   NODO *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(NODO *cabeza)
{
   if(cabeza!=NULL){
      inorder(cabeza->izq);
      printf("%d ",cabeza->dato);
      inorder(cabeza->der);
   }
}

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

void postorder(NODO *cabeza)
{
   if(cabeza!=NULL){
      postorder(cabeza->izq);
      postorder(cabeza->der);
      printf("%d ",cabeza->dato);
   }
}
void salvar(NODO **cabeza, int elemento)
{
   NODO *p, *p2;
   if(elemento==cabeza->dato){
      if(cabeza->izq==cabeza->der){
         free(cabeza);
         return(NULL);
      }
   if (elemento > 0){		
      if ()
         moverDrcha(actual, k);
      else
         combina(actual, k);

   else				/* Sólo tiene "hermano" derecho */
      if (actual->ramas[1]->cuenta > m/2)
         moverIzqda(actual, 1);
      else
         combina(actual, 1);
}