#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
#include <iostream>

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

void insertar();
void eliminar();
void preorden();
void inorden();
void postorden();
void salir();

int main()
{
    int elemento, valor, opcion;
     NODOARBOL *raiz=NULL;
     system("cls");
    int menu; //declaramos la variable "menu"
   
         //mostramos en pantalla todas las opciones disponibles
         std::cout << "Menu C para programas C/C++" << std::endl;
         std::cout << "2008 Inc1ud3zn" << std::endl;
         
         //incluimos una tabulación para hacer el menú a dos linias (t)
         std::cout << "Introduzca su seleccion" << std::endl;
         std::cout << "1. Insertar"  << std::endl;
         std::cout << "2. Eliminar"  << std::endl;
         std::cout << "3. Preorden"  << std::endl;
         std::cout << "4. Inorden"  << std::endl;
         std::cout << "5. Postorden"  << std::endl;
         std::cout << "6. Salir"  << std::endl;
         
         std::cin >> menu; //hacemos que el programa lea del teclado la variable "menu"
         
          switch (menu)
  {
 case 1:
    system("cls");
    printf("\nIngrese elemento a insertar [0 : 99]: ");
    scanf("%d", &elemento);
    if(elemento<0 || elemento>99){
          printf("\nDato desbordado");
          getch();
    break;
       }
       insertar(&raiz, elemento);
       break;
 case 2:
    system("cls");
       printf("\nIngrese elemento a eliminar [0 : 99]: ");
       scanf("%d", &elemento);
       if(elemento<0 || elemento>99)
       {
          printf("\nDato desbordado");
          getch();
       break;
       }
       valor = 0;
       buscar(raiz, elemento, &valor);
       if(valor==1){
          raiz=eliminar( raiz, elemento);
          printf("\nNodo eliminado\n");
          getch();
       }
       break;
 case 3:
 system("cls");
        printf("El  arbol inorder es: "); inorden(raiz);
        getch();
        break;
 case 4:
 system("cls");
        printf("El  arbol preorder es: "); preorden(raiz);
        getch();
        break;
 case 5:
 system("cls");
        printf("El  arbol postorder es: "); postorden(raiz);
        getch();
        break;
 case 6: //para salir
      break; //rompemos el control del programa y lo enviamos al final del switch ( } ) ahí acabará la ejecución después del return 0;
 default://en caso de otro número, limpiamos la pantalla y enviamos el programa al inicio.
    system("cls");
    goto top;
    break;
   }
   
return 0;   
}

//funciones secundarias
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");
      getch(); }
}

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


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


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


void buscar(NODOARBOL *cabeza, int elemento, int *valor){
    if(cabeza!=NULL){
       if((cabeza)->dato==elemento) *valor=1;

       else{
       if(elemento<(cabeza)->dato) buscar((cabeza)->izq, elemento, valor);

       else buscar((cabeza)->der, elemento, valor);
       }
    }
    else{ printf("\nDato no encontrado\n");
     getch(); }
}

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

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

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

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

          else{
         p2=cabeza->der;
         p1=cabeza->der;
         while(p1->izq) p1=p1->izq;
         p1->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);
}