/*
  Ejercicio # 7
  Nombre: Arbol Binario
  Autor: Carlos Rolando Calán Ajquill
  Fecha: 24/06/06 00:45
  Descripción: Programa que maneja estructura tipo arbol binario y recorrer el 
               mismo en preorden, inorden y postorden, almacena datos de 
               acuerdo al valor ascii de cada uno.
  Versión: 1.0 
*/
#include <cstdlib>
#include <iostream>
#include <conio.c>
#include <iomanip>
using namespace std;
//Estructura base que sirve para almacenar los datosds de la estructura
struct base 
{                             
  char let;              // para almacenar carácter
  struct base* izq;      // puntero izquierdo
  struct base* der;      // puntero derecho
} *raiz, *aux;           // raiz puntero al nodo raíz; aux puntero auxiliar
//Procedimiento para realizar el recorrido en INORDEN
void InOrden(struct base* puntero);
//Procedimiento para realizar el recorrido en PREORDEN
void PreOrden(struct base* ptr);
//Procedimiento para realizar el recorrido en POSTORDEN
void PostOrden(struct base* ptr);  
//Procedimiento para recorrer el arbol
void Recorrido(struct base* ptr);  
//Para Otro elemento al arbol
void Otro();
//Procedimiento para agregar un nuevo elemento al arbol
int Agregar(char letra, struct base* puntero);
//Sirve para aceptar los datos del teclado
char Acepta (void);           

int main(int argc, char *argv[])
{
  int Opcion = 0;
  while (Opcion != 6)
  {
    system("CLS");
    cout<<"\t \t \t UNIVERSIDAD MARIANO GALVEZ \n \n"; 
    cout<<"\t \t Proyecto Final Estructura De Datos \n";    
    cout<<"\t \t Carlos Rolando Calan Ajquill    Junio/2006 \n";
    cout<<"\t \t Carne: 0910-04-13429         5to. Semestre \n";
    cout<<"\t \t ---------------------------------------------\n";    
    cout<<"\t \t Arbol Binario y recorrido del mismo \n ";
    cout<<"\t \t ---------------------------------------------\n\n";    
		cout<<"\t 1.- Ingreso de datos al Arbol \n";
		cout<<"\t 2.- Recorrer el Arbol \n";
		cout<<"\t 3.- Recorrido del Arbol en INORDEN \n";
   	cout<<"\t 4.- Recorrido del Arbol en PREORDEN \n";
		cout<<"\t 5.- Recorrido del Arbol en POSTORDEN \n";
    cout<<"\t 6.- Salir \n";
    cout<<"\t ------------------------------------------------\n";    
		cout<<"\t \t Seleccione una opcion \t";
		cin>>Opcion;
		cout<<"\n";
	  switch (Opcion)
		{
		  case 1:
        cout<<"OPCION 1: Ingresar Datos \n";
		    Otro();
				break;
			case 2:
        cout<<"OPCION 2: Recorre Arbol \n";
        Recorrido(raiz);
        getch();		    
				break;
		  case 3:
        cout<<"OPCION 3: Recorrido INORDEN \n";
		    InOrden(raiz);
		    getch();
				break;
      case 4:
        cout<<"OPCION 4: Recorrido PREORDEN \n";
		    PreOrden(raiz);
		    getch();
				break;
      case 5:
        cout<<"OPCION 5: Recorrido POSTORDEN \n";
		    PostOrden(raiz);
		    getch();
				break;				
			case 6:        
			  system("CLS");
        cout<<"Hecho por Carlos Rolando Calán Ajquill, hasta pronto ......\n\n";			        
			  break;
      default:
        cout;      
        cout<<"Opcion Invalida \n\n";
        break;	    
    } 
 	}  
  system("PAUSE");
  return EXIT_SUCCESS;
}
//Para otro nuevo elemento al arbol
void Otro()
{  
  char c;  
  while ((c = Acepta()) != 's') 
  { 
    if (Agregar(c, raiz)) 
      break;    
  }     
}
// Introducir datos por teclado
char Acepta(void) 
{  
  char c;
  cout<<"Pulse un carácter, Para salir 's' -> \t";
  while (1) 
  {
    c = getchar();
    // 10 == New Line
    if (c == 10) continue;    
    return c;
  }
}
// Sirve para agregar un nuevo elemento al arbol
int Agregar(char letr, struct base* ptr) 
{  
  // 1o. solo la primera vez!!!
  if (raiz == NULL) 
  {           
    raiz = (struct base*) malloc(sizeof(base));
    if (raiz == NULL) 
    {
      cout<<"NO hay memoria suficiente!!" ;
      cout;
      return 1;
    }
    raiz->let = letr;
    raiz->izq = raiz->der = NULL;
    return 0;
  }  
  // 2o. El carácter ya existe
  if (letr == ptr->let) 
     return 0;    
  if (letr < ptr->let) 
  {
    // 3o.
    if (ptr->izq == NULL) 
    {   // enlace libre: incluir
      aux = (struct base*) malloc(sizeof(base));
      if (aux == NULL) 
      {
        cout << "NO queda suficiente memoria";
        return 1;
      }
      aux->let = letr;
      aux->izq = aux->der = NULL;
      ptr->izq = aux;
      return 0;
    }
    // ocupado: seguir buscando
    if (Agregar(letr, ptr->izq))     
      return 1;               // falla la inserción
  }
  // 4o.
  if (letr > ptr->let) 
  {   
    if (ptr->der == NULL) 
    {   // enlace libre: incluir
      aux = (struct base*) malloc(sizeof(base));
      if (aux == NULL) 
      {
        cout << "NO queda suficiente memoria";
        return 1;
      }
      aux->let = letr;
      aux->izq = aux->der = NULL;
      ptr->der = aux;
      return 0;
    }
    if (Agregar(letr, ptr->der))     // ocupado: seguir buscando
      return 1;               // falla la inserción
  }
  return 0;
}

// Recorrer árbol INORDEN
void InOrden(struct base* ptr) 
{
  if (ptr == NULL) 
    return;
  InOrden(ptr->izq);
  cout<<" - "<<ptr->let;
  InOrden(ptr->der);
}
// Para recorrer el Arbol
void Recorrido(struct base* ptr) 
{
  if (ptr == NULL) 
    return;
  Recorrido(ptr->izq);
  cout<<" - "<<ptr->let;
  Recorrido(ptr->der);
}
// Recorrer arbol PREORDEN
void PreOrden(struct base* ptr) 
{     
  if (ptr == NULL) 
    return;
  cout<<" - "<<ptr->let;
  PreOrden(ptr->izq);
  PreOrden(ptr->der);
}
// Recorrer arbol POSTORDEN
void PostOrden(struct base* ptr) 
{
  if (ptr == NULL) 
    return;
  PostOrden(ptr->izq);
  PostOrden(ptr->der);
  cout<<" - "<<ptr->let;
}