// intento2.cpp: define el punto de entrada de la aplicación de consola.
//

#include "stdafx.h"
#include <cstdlib>
#include <stdlib.h>
#include <iostream>

using namespace std;



typedef struct tnodo *pnodo;
typedef struct tnodo
{
	int dato;
	pnodo izquierdo;
	pnodo derecho;
};

int mostrarMenu();
void iniciar(pnodo &x);
void recorrer(pnodo a);
pnodo crearNodo(pnodo nuevo);
void agregar(pnodo &a, pnodo nuevo);
void unirLosConjunto(pnodo a, pnodo b);
void posorden(pnodo a);
pnodo hacerInterseccion(pnodo x, pnodo y);
bool verificarPertenencia(pnodo x, int valor);
pnodo hacerDiferencia(pnodo x, pnodo y);


int _tmain(int argc, _TCHAR* argv[])
{
	pnodo A, B, nuevo, dif, inter;
	nuevo = NULL;
	dif = NULL;
	inter = NULL;
	bool bandera,bandera2, salir, per;
	salir = true;
	bandera = false;
	bandera2 = false;
	int opc, numero;
	char r, con;

	while(salir == true){
		opc = mostrarMenu();
		if(opc == 1){
			iniciar(A);
			iniciar(B);
			bandera = true;
			cout << "CONJUNTOS INICIALIZADOS" << endl;
		}
		if((opc == 2)&&(bandera == true)){
			cout << "conjunto A" << endl;
			cout << "Continua? (S/N)" << endl;
			cin >> r;
			while((r == 's')||(r == 'S')){
				agregar(A, nuevo);
				bandera2 = true;
				cout << "Continua? (S/N)" << endl;
				cin >> r;
			}
			cout << "conjunto B" << endl;
			cout << "Continua? (S/N)" << endl;
			cin >> r;
			while((r == 's')||(r == 'S')){
				agregar(B, nuevo);
				bandera2 = true;
				cout << "Continua? (S/N)" << endl;
				cin >> r;
			}
		}
		if((opc == 3)&&(bandera2 == true)){
			 recorrer(A);
		}
		if((opc == 4)&&(bandera2 == true)){
			unirLosConjunto(A, B);
		}
		if((opc == 5)&&(bandera2 == true)){
			 inter = hacerInterseccion(A, B);
			 recorrer(inter);
		}
		if((opc == 6)&&(bandera2 == true)){
			cout << "Ingrese el conjunto que quiere verificar la pertenencia de un valor" << endl;
			cin >> con;
			if((con == 'A') || (con == 'a')){
				cout << "ingrese el numero" << endl;
				cin >> numero;
				per = verificarPertenencia(A, numero);
				if(per == false)
					cout << "El dato no existe en l conjunto A" << endl;
				else
					cout << "El dato si existe en el conjunto A" << endl;
			}else{
				if((con == 'B') || (con == 'b')){
				cout << "ingrese el numero" << endl;
				cin >> numero;
				per = verificarPertenencia(B, numero);
				if(per == false)
					cout << "El dato no existe en l conjunto B" << endl;
				else
					cout << "El dato si existe en el conjunto B" << endl;
			   }
			}
		}
		if((opc == 7)&&(bandera2 == true)){
			 dif = hacerDiferencia(A, B);
			 recorrer(dif);
		}
		 if(opc == 8){
                cout << " Autor: Marina Soledad, Gonzalez Torres " << endl;
                cout << " Fecha: 26 de Noviembre de 2014 " << endl;
                salir = false;
         }
	}

	return 0;
}

int mostrarMenu(){
	int opc;
		cout << "************* MENU PRINCIPAL *************" << endl;
        cout << "1) Iniciar los conjuntos A y B" << endl;
        cout << "2) Asignar elementos a A y B" << endl;
        cout << "3) Mostrar los conjuntos A y B" << endl;
        cout << "4) Union de A y B" << endl;
        cout << "5) Interseccion de A y B" << endl;
        cout << "6) Pertenencia (conjunto A)" << endl;
        cout << "7) Diferencia entre A y B" << endl;
        cout << "8) Salir" << endl;
        cout << "************* MENU PRINCIPAL *************" << endl;
        cout << "ELIJA UNA OPCION" << endl;
        cin >> opc;
        return opc;
 }

void recorrer(pnodo a){
	if(a != NULL){
		cout << a->dato;
		recorrer(a->izquierdo);
		recorrer(a->derecho);
	}
}

void iniciar(pnodo &x){
	x = NULL;
}

void agregar(pnodo &a, pnodo nuevo){
	crearNodo(nuevo);
	if (a==NULL){
		a=nuevo;
	}
	else{
		if (nuevo->dato < a->dato)
			agregar(a->izquierdo, nuevo);
		else
			agregar(a->derecho, nuevo);
	}
}

pnodo crearNodo(pnodo nuevo){
	nuevo = new tnodo;
	if(nuevo != NULL){
		cout << "Ingrese valor" << endl;
		cin >> nuevo->dato;
		nuevo->izquierdo = NULL;
		nuevo->derecho = NULL;
	}
	return nuevo;
}

void unirLosConjunto(pnodo a, pnodo b){
	pnodo c;
	if((a != NULL)&&(b != NULL)){
		if(a->dato != b->dato){
			if(a->dato < b->dato){
				agregar(c, a);
				unirLosConjunto(a, b);
			}else{
				agregar(c, b);
				unirLosConjunto(a, b);
			}
		}
	}
}

void posorden(pnodo a){
	if (a!=NULL){
		posorden(a->izquierdo);
		posorden(a->derecho);
		cout << a->dato;
	}
}

pnodo hacerInterseccion(pnodo x, pnodo y){
	pnodo z;
	if((x != NULL)&&(y != NULL)){
		if(x->dato == y->dato){
			agregar(z, x);
			hacerInterseccion(x->izquierdo, y->izquierdo);
			hacerInterseccion(x->derecho, y->derecho);
		}else{
			hacerInterseccion(x->izquierdo, y->izquierdo);
			hacerInterseccion(x->derecho, y->derecho);
		}
	}
	return z;
}

bool verificarPertenencia(pnodo x, int valor){
	bool pertenece = false;
	if(x->dato == valor)
		pertenece = true;
	else{
		recorrer(x);
		verificarPertenencia(x, valor);
	}
	return pertenece;
}

pnodo hacerDiferencia(pnodo x, pnodo y){
	pnodo d;
	if(x != NULL){
		if(x->dato != y->dato){
			agregar(d, x);
			hacerDiferencia(x->izquierdo, y);
			hacerDiferencia(x->derecho, y);
	    }else{
			hacerDiferencia(x->izquierdo, y);
			hacerDiferencia(x->derecho, y);
		}
	}

	return d;
}