#include <iostream>
#include <stdlib.h>

using namespace std;

/*--------- Estructura del arbol -------*/
typedef struct nodo{
int nro;
struct nodo *izq, *der;
}*ABB;


ABB crearNodo(int x);
void insertar(ABB &arbol, int x);
void verArbol(ABB arbol, int n);
bool verificarPertenencia(ABB arbol, int dato);
void menu();
ABB unirConjuntos(ABB x, ABB y);
ABB hacerInterseccion(ABB x, ABB y);
ABB hacerDiferencia(ABB x, ABB y);

int main(int argc, char** argv) {
        ABB arbol, arbol2, arbolUnion, arbolInterseccion, arbolDif;
        arbol = NULL;
        arbol2 = NULL;
        arbolUnion = NULL;
        arbolInterseccion = NULL;
        arbolDif = NULL;
        int op, op2, x;
        char r;
        bool bandera, salir;
        bandera= false;
        salir = true;

        do{
                menu(); cin>> op;
                cout << endl;

                switch(op){
                    case 1:
                        cout << "CONJUNTOS INICIALIZADOS" << endl;
                        bandera = true;
                        break;
                    case 2:
                        if(bandera == true){
                                cout << "¿Conjunto A o Conjunto B?"<<endl;
                                cin >> r;
                                if((r == 'a') || (r == 'A')){
                                        cout << "Ingrese Valor" << endl;
                                        cin >> x;
                                        insertar(arbol, x);
                                }
                                 if((r == 'b') || (r == 'B')){
                                          cout << "Ingrese Valor" << endl;
                                          cin >> x;
                                          insertar(arbol2, x);
                                }
                        }else
                            cout << "Debe elegir primero la opcion 1" << endl;
                                 break;
                     case 3:
                          cout << "Conjunto A" << endl;
                          verArbol(arbol, 0);
                          cout << "Conjunto B" << endl;
                          verArbol(arbol2, 0);
                         break;

                     case 4:
                       arbolUnion = unirConjuntos(arbol, arbol2);
                       verArbol(arbolUnion, 0);
                        break;
                    case 5:
                          arbolInterseccion = hacerInterseccion(arbol, arbol2);
                          verArbol(arbolInterseccion, 0);
                        break;

                    case 6:
                        bool band;
                        cout<<" Valor a buscar: "; cin>> x;
                        band = verificarPertenencia(arbol,x);
                         if(band==1)
                                cout << "\n\tSi Pertenece...";
                        else
                                 cout << "\n\tNo Pertenece...";
                 break;
                case 7:
                    arbolDif = hacerDiferencia(arbol, arbol2);
                    verArbol(arbolDif, 0);
                break;

                case 8:
                        cout << " Autor: Marina Soledad, Gonzalez Torres " << endl;
                        cout << " Fecha: 26 de Noviembre de 2014 " << endl;
                        salir = false;
                break;
        }

        cout<<"\n\n\n";
        }while(salir == true);


    return 0;
}


ABB crearNodo(int x){
        ABB nuevoNodo = new(struct nodo);
        nuevoNodo->nro = x;
        nuevoNodo->izq = NULL;
        nuevoNodo->der = NULL;

        return nuevoNodo;
}

void insertar(ABB &arbol, int x){
        if(arbol==NULL){
                arbol = crearNodo(x); //LLamo al metodo para crear un nodo nuevo en el arbol
       }
        else{
            if(x < arbol->nro)
                insertar(arbol->izq, x);
            else {
                if(x > arbol->nro)
                        insertar(arbol->der, x);
            }
        }
}

void verArbol(ABB arbol, int n){
        if(arbol==NULL)
              return;
        verArbol(arbol->der, n+1);
         for(int i=0; i<n; i++)
                cout<<" ";
        cout<< arbol->nro <<endl;
         verArbol(arbol->izq, n+1);
}

bool verificarPertenencia(ABB arbol, int dato){
        int r=0; // 0 indica que lo encontre
        if(arbol==NULL)
                return r;
        if(dato<arbol->nro)
                r = verificarPertenencia(arbol->izq, dato);

        else{
            if(dato> arbol->nro)
                r =verificarPertenencia(arbol->der, dato);
            else
                        r = 1; // son iguales, lo encontre
        }
        return r;
}

void menu(){

cout << "\n\t\t ..************ MENÚ ************.. \n\n";
cout << "\t [1] Inicializar Conjuntos A y B \n";
cout << "\t [2] Agregar elementos a los conjuntos A y B \n";
cout << "\t [3] Mostrar los conjuntos A y B \n";
cout << "\t [4] Unir los conjuntos A y B \n";
cout << "\t [5] Interseccion de los conjuntos A y B \n";
cout << "\t [6] Verificar pertenencia (Conjunto A)\n";
cout << "\t [7] Diferencia entre A y B \n";
cout << "\t [8] Salir \n";
cout << "\n\t\t ..************ MENÚ ************.. \n\n";

cout << "\n\t Ingrese opcion : ";
}

ABB unirConjuntos(ABB x, ABB y){
    ABB z;
    if(x == NULL)
        return y;
    if(y == NULL)
        return x;
    z = unirConjuntos(x->der, y->izq);
    x->der = z;
    y->izq = x;
        return y;
}

ABB hacerInterseccion(ABB x, ABB y){
        ABB z;
        if((x != NULL) && (y != NULL)){
            if(y->nro == x->nro)
                return y;
            z = hacerInterseccion(x->der, y->izq);

        }
        return y;
 }

ABB hacerDiferencia(ABB x, ABB y){
        ABB d;
        if(x != NULL){
                if(x->nro != y->nro){
                    return x;
                        hacerDiferencia(x->izq, y);
                        hacerDiferencia(x->der, y);
            }else{
                        hacerDiferencia(x->izq, y);
                        hacerDiferencia(x->der, y);
                }
        }

        return d;
}