/*
	Name: Arboles Binarios
	Copyright:
	Author:
	Date: 15/08/16 22:25
	Description:  Programa para arboles binarios de busques
*/

#include <iostream>


using namespace std;

class nodo{

	private:

		int clave;
		int contador;
		nodo *izdo;
		nodo *dcho;

	//Contrsuctor
	nodo(int cl = 0, int con = 1, nodo *iz = NULL, nodo *de = NULL){

		clave = cl;
		contador = con;
		izdo = iz;
		dcho = de;
	}

friend class ArbolBus;

};


typedef nodo *pnodo;
  pnodo q;


class ArbolBus{

	private:

		nodo *raiz;
		void LiberarMem(pnodo);


	public:

	//Constructor y detructor
		ArbolBus(pnodo r = NULL){

			raiz = r;
		}

		~ArbolBus() { LiberarMem(raiz); }

	//Metodos
	int ArbolVacio(pnodo raiz){ return raiz == NULL;}

	void BuscarClave(int x){buscar(x, raiz);}
	void buscar(int, pnodo &);

	void Visualizar(int n){visualizar_arbol(raiz, n);}
	void visualizar_arbol(pnodo, int);

	void VerPreOrden(){cout << " Recorrido en Pre-Orden: "; PreOrden(raiz); }
	void PreOrden(pnodo &b);

	void VerInOrden(){cout << " Recorrido en In-Orden: "; InOrden(raiz); }
	void InOrden(pnodo &b);

	void VerPostOrden(){cout << " Recorrido en Post-Orden: "; PostOrden(raiz); }
	void PostOrden(pnodo &b);

	void BorrarNodo(int x){borrar(x, raiz);}
	void borrar(int x, pnodo &p);
	void borrar_nodo(pnodo &d);
};



	void ArbolBus::LiberarMem(pnodo a){
		if(!ArbolVacio(a)){
			LiberarMem(a->izdo);
			LiberarMem(a->dcho);
			delete a;
		}
	}


void ArbolBus::buscar(int x, pnodo &a){

	if(ArbolVacio(a))
	{
		a = new nodo(x);
	}
	else
	{
		if (x < a->clave)
			buscar(x, a->izdo);
		else
		{
			if(x > a->clave)
				buscar(x, a->dcho);
			else
				a->contador++;

		}
	}
};


void ArbolBus::visualizar_arbol(pnodo a, int n){

	int i;
	if(!ArbolVacio(a))
	{
		visualizar_arbol(a->izdo, n+1);

			for (i=1; i <= n; i++)
				cout << "      ";
		printf("%d(%d,%d, %d)\n", a->clave, a->contador, i, n);
		visualizar_arbol(a->dcho, n+1);
	}
}

void ArbolBus::borrar(int x, pnodo &p){



	//buscar el nodo que se desea borrar
	if(ArbolVacio(p))
		cout << "\n Ese nodo no esta en el arbol\n\n";
	else if(x < p->clave)
		borrar(x, p->izdo);
	else if (x > p->clave)
	    borrar(x, p->dcho);
	else{		                     // borrar el nodo apuntado por p
		q = p;
		if(q->dcho	== NULL)
			p = q->izdo;
		else if (q->izdo == NULL)
			p = q->dcho;
		else
			borrar_nodo(q->izdo);
		 	delete q;

	}
}

void ArbolBus::borrar_nodo(pnodo &d){


	//descender al nodo mas a la derecha del subarbol d
	if (d->dcho != NULL)
		borrar_nodo(d->dcho);
	else
	{
		q->clave = d->clave;
		q->contador = d->contador;
		q = d;
		d = d->izdo;
	}
}

void ArbolBus::PreOrden(pnodo &b){


	if( b != NULL){

		cout << b->clave << ", ";
		PreOrden(b->izdo);
		PreOrden(b->dcho);
	}
}

void ArbolBus::InOrden(pnodo &b){

	if( b != NULL){

		InOrden(b->izdo);
		cout << b->clave << ", ";
		InOrden(b->dcho);
	}

}

void ArbolBus::PostOrden(pnodo &b){

	if( b != NULL){

		PostOrden(b->izdo);
		PostOrden(b->dcho);
		cout << b->clave << ", ";
	}

}



int main(){

	cout << endl << endl;

	ArbolBus arbol_b;
	int k;

	system("cls");

	/*
	cout << "Introducir claves. Finalizar con ^Z\n\n";
	cout << "Clave: ";
	while(cin >> k){
		arbol_b.BuscarClave(k);
		cout << "clave: ";
	}
	*/
	cout << endl << endl;

	arbol_b.BuscarClave(10);
	arbol_b.BuscarClave(5);
	arbol_b.BuscarClave(15);
	arbol_b.BuscarClave(3);
	arbol_b.BuscarClave(8);
	arbol_b.BuscarClave(1);
	arbol_b.BuscarClave(4);
	arbol_b.BuscarClave(13);
	arbol_b.BuscarClave(18);

	arbol_b.Visualizar(0);
	cout << endl << endl;


	arbol_b.VerPreOrden();
	cout << endl << endl;
	arbol_b.VerInOrden();
	cout << endl << endl;
	arbol_b.VerPostOrden();
	cout << endl << endl;

	cout << "Desea borrar un Nodo:" ; cin >> k;
	arbol_b.BorrarNodo(k);


	arbol_b.Visualizar(0);


	cout << endl << endl;
	system("PAUSE");
	return 0;
}