ABB.Final.1

// Arboles_Binarios.cpp : main project file.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace System;
using namespace std;

class nodoarbol
{
public:
	int info;
	nodoarbol *der,*izq;
	nodoarbol()
	{
		izq=NULL;
		der=NULL;
	}
	nodoarbol(int dato)
	{
		info=dato;
		izq=NULL;
		der=NULL;
	}
};
struct nodo
{
	nodoarbol *actual;
	nodo *sig;
};
class Fila
{
private:
	nodo *frente;
	nodo *final;
	int lon;
public:
	Fila();
	void meter(nodoarbol *nodo);
	char sacar(nodoarbol *&valor);
	~Fila();
	void limpiarFila();//Quita todos los elementos de la fila
	int frenteFila();//Obtiene el elemento frente de la fila
	int longitudFila();//Obtiene la cantidad de elementos de la fila
	void desplegarFila();//Muestra los elementos de la fila
};
char Fila::sacar(nodoarbol *&valor)//Quitar (Pop) elementos de una fila
{
	nodo *apunt;
	apunt=frente;
	if(apunt==NULL)return 0;
	else
	{
		lon--;
		valor=apunt->actual;
		if(frente->sig==NULL)
		{
			frente=NULL;
			final=NULL;
		}
		else frente=apunt->sig;
		delete apunt;
		return 1;
	}
}
Fila::Fila()
{
	frente=NULL;
	final=NULL;
	lon=0;
}
Fila::~Fila()
{
	nodo *apunt;
	apunt=frente;
	while(frente!=NULL)
	{
		cout<<"borro"<<endl;
		frente=apunt->sig;
		delete apunt;
		apunt=frente;
	}
}
void Fila::meter(nodoarbol *nuevo)//Insertar un nodo
{
	nodo *el_nodo=new nodo();
	el_nodo->actual=nuevo;
	if(final==NULL)frente=el_nodo;
	else final->sig=el_nodo;
	el_nodo->sig=NULL;
	final=el_nodo;
	lon++;
}
int Fila::longitudFila()
{
	return lon;
}
class ABB
{
private:
	nodoarbol *raiz;
public:
	ABB()
	{
		raiz=NULL;
	}
	~ABB()
	{
		cout<<"Entro al destructor"<<endl;
		borrar_nodos(raiz);
		cout<<"Salgo del destructor"<<endl;
	}
	void borrar_nodos(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			borrar_nodos(raiz->izq);
			borrar_nodos(raiz->der);
			cout<<"Destructor de "<<raiz->info<<endl;
			delete raiz;
		}
	}
	void insertar()
	{
		nodoarbol *aux1,*aux2,*aux3;
		aux1=new nodoarbol;
		aux2=raiz;
		aux3=NULL;
		cout<<"Entre el valor del nodo a insertar:";
		cin>>aux1->info;
		while(aux2!=NULL)
		{
			aux3=aux2;
			if(aux1->info>aux2->info) aux2=aux2->der;
			else
			{
				if(aux1->info<aux2->info) aux2=aux2->izq;
				else
				{
					cout<<"El nodo a agregar ya existe"<<endl;
					break;
				}
			}
		}
		if(aux3==NULL)raiz=aux1;
		else
			if(aux1->info<aux3->info)aux3->izq=aux1;
			else
			{
				if(aux1->info>aux3->info)aux3->der=aux1;
				else delete aux1;
			}
	}
	nodoarbol *devolver_raiz()
	{
		return raiz;
	}
		void despliega(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			despliega(raiz->izq);
			cout<<raiz->info<<endl;
			despliega(raiz->der);
		}
	}
	void despliega2(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			cout<<raiz->info<<endl;
			despliega2(raiz->izq);
			despliega2(raiz->der);
		}
	}
	void despliega3(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			despliega3(raiz->izq);
			despliega3(raiz->der);
			cout<<raiz->info<<endl;
		}
	}
	void despliega4(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			despliega(raiz->der);
			cout<<raiz->info<<endl;
			despliega(raiz->izq);
		}
	}
	void despliega5(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			cout<<raiz->info<<endl;
			despliega2(raiz->der);
			despliega2(raiz->izq);
		}
	}
	void despliega6(nodoarbol *raiz)
	{
		if(raiz!=NULL)
		{
			despliega3(raiz->der);
			despliega3(raiz->izq);
			cout<<raiz->info<<endl;
		}
	}

	void despliega7(nodoarbol *raiz)
	{
		Fila f;
		nodoarbol *apunt;
		if(raiz!=NULL)
		{
			f.meter(raiz);
			while(f.longitudFila()>0)
			{
				f.sacar(apunt);
				cout<<apunt->info<<endl;
				if(apunt->izq!=NULL)f.meter(apunt->izq);
				if(apunt->der!=NULL)f.meter(apunt->der);
			}
		}
	}
	void eliminar_nodo(int valor)
	{
		int hijo;
		nodoarbol *aux1, *aux2, *temp;
		bool b;
		//inicio de la busqueda del nodo a eliminar para esta parte

		if(raiz != NULL)
		{
			aux1= raiz;
			aux2=NULL;

			while(aux1->info != valor)
			{
				aux2=aux1;
				if(valor<aux1->info) aux1=aux1->izq;
				else aux1=aux1->der;
				if(aux1==NULL)
				{
					cout<<"el nodo a eliminar no existe"<<endl;
					break;
				}
			}
		}
		else
		{
			cout<<"el arbol no contiene nodos"<<endl;
			aux1=NULL;
		}
		if(aux1 != NULL)
		{
			temp = aux1;
			if((aux1->izq==NULL)&&(aux1->der==NULL))
			{
				if(aux2 != NULL)
				{
					if(aux1->info<aux2->info) aux2->der=NULL;
					else aux2->izq=NULL;
				}
				else
				{
					raiz = NULL;
				}
			}
			else
			{
				if((aux1->izq!=NULL)&&(aux1->der!=NULL))
				{//tiene dos hijos
				    cout<<"el nodo padre a eliminiar tiene dos hijos"<<endl;
					cout<<"si desea reemplazarlo por parte del hijo menor dijite ( 1 ) "<<endl;
					cout<<"si desea reemplazarlo por parte del hijo meyor dijite ( 2 ) "<<endl;
					cin>>hijo;
					if(hijo == 1)
					{
						aux2=aux1;
						temp=aux1->izq;
						b=true;
						while(temp->der!=NULL)
						{
							aux2=temp;
							temp=temp->der;
							b=false;
						}
						aux1->info=temp->info;
						if(b==true)aux1->izq=temp->izq;
						else
						{
							if(temp->izq!=NULL) aux2->der=temp->izq;
							else aux2->der=NULL;
						}
					}
					else
					{
						aux2=aux1;
						temp=aux1->der;
						b=true;
						while(temp->izq!=NULL)
						{
							aux2=temp;
							temp=temp->izq;
							b=false;
						}
						aux1->info=temp->info;
						if(b==true)aux1->der=temp->der;
						else
						{
							if(temp->der!=NULL) aux2->izq=temp->der;
							else aux2->izq=NULL;
						}
					}
				}
				else
				{
					if(aux1->izq==NULL)
						if(aux2 != NULL)
						{
							if(aux1->info<aux2->info)
								aux2->izq=aux1->der;
							else aux2->der=aux1->der;
						}
						else raiz=aux1->der;
					else
						if(aux2!=NULL)
						{
							if(aux1->info<aux2->info)
								aux2->izq=aux1->izq;
							else aux2->der=aux1->izq;
						}
						else raiz=aux1->izq;
				}
			}
			delete temp;
		}
	}
};

		void main()
	{//Console::Title::set(" PROGRAMADOR: JULIAN VILLAMIZAR ");
		//Console::ForegroundColor::set(ConsoleColor::Red);
		cout<<"\n\t\t\t !BIENVENIDO USUARIO!\n\n";
		//Console::ForegroundColor::set(ConsoleColor::White);

		nodoarbol *raiz;
		char resp, resp3;
		int resp1, resp2, valor;
		ABB n;
		do
		{
			n.insertar();
			cout<<"Desea crear otro nodo (s/n): ";
			cin>>resp;
			cout<<endl;
			resp=tolower(resp);
		}while(resp!='n');
//char resp;
	do{
		cout<<endl;

		cout<<"Por favor digite, como desea desplegar el arbol ?"<<endl<<endl;
		cout<<"1. Desplegar el arbol en Preorden"<<endl;
		cout<<"2. Desplegar el arbol en Inorden"<<endl;
		cout<<"3. Desplegar el arbol en Postorden"<<endl;
		cout<<"4. Desplegar el arbol en Preorden converso"<<endl;
		cout<<"5. Desplegar el arbol en Inorden converso"<<endl;
		cout<<"6. Desplegar el arbol en Postorden converso"<<endl;
		cout<<"7. Desplegar el arbol en Nivel por nivel"<<endl;
		cout<<"0. Salir"<<endl;
		cout<<endl;
		cin>>resp1;
		switch(resp1)
		{
		case 1:
			cout<<"Preorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega2(raiz);
			break;
		case 2:
			cout<<"Inorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega(raiz);
			break;
		case 3:
			cout<<"Postorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega3(raiz);
			break;
		case 4:
			cout<<"Preorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega5(raiz);
			break;
		case 5:
			cout<<"Inorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega4(raiz);
			break;
		case 6:
			cout<<"Postorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega6(raiz);
			break;
		case 7:
			cout<<"Nivel por nivel"<<endl;
			raiz=n.devolver_raiz();
			n.despliega7(raiz);
			break;
		case 0:
			cout<<"Continue"<<endl<<endl;
			break;
		default:
			cout<<"Opcion no valida"<<endl;
		}
	}while(resp1!=0);

		do{
			cout<<"Entre el valor del nodo a eliminar"<<endl;
			cin>>valor;
			n.eliminar_nodo(valor);
			cout<<endl;
//char resp;
	do{
		raiz=n.devolver_raiz();
		cout<<endl;
		cout<<"Por favor digite, como desea que se despliegue el arbol ?"<<endl<<endl;
		cout<<"1. Desplegar el arbol en Preorden"<<endl;
		cout<<"2. Desplegar el arbol en Inorden"<<endl;
		cout<<"3. Desplegar el arbol en Postorden"<<endl;
		cout<<"4. Desplegar el arbol en Preorden converso"<<endl;
		cout<<"5. Desplegar el arbol en Inorden converso"<<endl;
		cout<<"6. Desplegar el arbol en Postorden converso"<<endl;
		cout<<"7. Desplegar el arbol en Nivel por nivel"<<endl;
		cout<<"0. Salir"<<endl;
		cout<<endl;
		cin>>resp2;
		switch(resp2)
		{
		case 1:
			cout<<"Preorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega2(raiz);
			break;
		case 2:
			cout<<"Inorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega(raiz);
			break;
		case 3:
			cout<<"Postorden"<<endl;
			raiz=n.devolver_raiz();
			n.despliega3(raiz);
			break;
		case 4:
			cout<<"Preorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega5(raiz);
			break;
		case 5:
			cout<<"Inorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega4(raiz);
			break;
		case 6:
			cout<<"Postorden converso"<<endl;
			raiz=n.devolver_raiz();
			n.despliega6(raiz);
			break;
		case 7:
			cout<<"Nivel por nivel"<<endl;
			raiz=n.devolver_raiz();
			n.despliega7(raiz);
			break;
		case 0:
			cout<<"Continue"<<endl<<endl;
			break;
		default:
			cout<<"Opcion Invalida. Intentelo de nuevo"<<endl;
		}
	}while(resp2!=0);

		cout<<"Desea eliminar otro nodo (s/n):"<<endl;
		cin>>resp3;
		cout<<endl;
		resp=tolower(resp);
	}while(resp3!='n');
		getch();
}