Arbol.Binario.Seleccion.Repetido.Recorrido.3

// Arboles_Binarios.cpp : main project file.

//1. Que no permita agregar nodos repetidos. Si existe, desplegar "Nodo a insertar ya existe".
//2. Para eliminar un nodo con dos hijos preguntar si se sustituye por el predecesor o por el sucesor, y luego hacer la respectiva eliminación.
//3. Al momento de desplegar el arbol debe preguntar que forma lo recorre:
// preorden, in orden, post orden .... nivel por nivel y desplegarlo según el recorido.

// Investigar sobre Árboles Balanceados ( AVL )
// 1. ¿Qué es un árbol balanceado
// 2. ¿Qué valores tiene el factor de balance
// 3. ¿Cómo insertar un nodo en un árbol balanceado.
//    3.1 Presentar los casos existentes para balancear un árbol después de la inserción de un nodo.
//    3.2 Presentar ejemplos de cada caso utilizando valores numéricos
// 4. ¿Cómo eliminar un nodo en un árbol balanceado?
//    4.1 Presentar casos existentes para balancear un árbol después de a eliminación de un nodo
//    4.2 Presentar ejemplos de cada caso utilizando valores numéricos.
// 5. Hacer programa insertar, eliminar y desplegar por nivel los nodos de un árbol balanceado



#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;
	}
};
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 *auxl, *aux2, *aux3;
	auxl=new nodoarbol;
	aux2=raiz;
	aux3=NULL;
	int buscador=0;
	cout<<"Entre el valor del nodo a insertar:";
	cin>>auxl->info;
	while(aux2!=NULL) // Este ciclo recorre el arbol.
	{
			  aux3=aux2; // El aux3 siempre señalará al nodo PADRE al nodo que señala aux2
			  if( auxl->info==aux2->info )
			  {
				buscador=buscador+1;
				cout<<"El nodo a insertar ya existe"<<endl;
			    break;
			  }
				if(auxl->info>aux2->info) aux2=aux2->der;
			    else aux2=aux2->izq;
	}
	if( buscador==0 )
	{
      if(aux3==NULL) raiz=auxl;  // Primera inserción
	  else
		if(auxl->info<aux3->info) aux3->izq=auxl;
		else aux3->der=auxl;
	}

}
nodoarbol *devolver_raiz ()
{
	return raiz;
}


void despliega(nodoarbol *raiz)// InOrden
{
	if(raiz!=NULL)
	{
		despliega(raiz->izq);
		cout<<raiz->info<<endl;
		despliega(raiz->der);
	}
}

void preOrden(nodoarbol *raiz)
{
     if(raiz!=NULL)
     {
		cout<<raiz->info<<endl;
		preOrden(raiz->izq);
		preOrden(raiz->der);
     }
}

void postOrden(nodoarbol *raiz)
{
     if(raiz!=NULL)
     {
		postOrden(raiz->izq);
		postOrden(raiz->der);
		cout<<raiz->info<<endl;
     }
}


void eliminar_nodo(int valor)
{
	nodoarbol *auxl, *aux2, *temp;
	int numero;
	bool b;
	// Inicio de la busqueda del nodo a eliminar
	if(raiz!=NULL)
	{
		auxl=raiz;
		aux2=NULL; // Siempre señala al nodo PADRE del que señala el apuntador AUX1

		while(auxl->info!=valor)
		{
			aux2=auxl;
			if(valor<auxl->info) auxl=auxl->izq;
			else auxl=auxl->der;
			if(auxl==NULL)
			{
				cout<<"EL NODO A ELIMINAR NO EXISTE"<<endl;
				break;
			}
		}
	}
else
{
	cout<<"EL ARBOL NO CONTIENE NODOS"<<endl;
	auxl=NULL;
}
// Fin de la busqueda del nodo a eliminar.
// En auxl queda la dirección del nodo a eliminar.
// En aux2 queda la dirección del nodo	PADRE del nodo a eliminar
if(auxl!=NULL)
{
	//Cuando no tiene hijos
	temp=auxl ;
	if((auxl->izq==NULL)&&(auxl->der==NULL))
	{
		if(aux2!=NULL)
		{
			if(auxl->info>aux2->info) aux2->der=NULL;
			else aux2->izq=NULL;
		}
		else
		{
			raiz=NULL;
		}
	}
	else
	{
		if ((auxl->izq!=NULL)&&(auxl->der!=NULL))
		{	//Cuando tiene dos hijos
			aux2=auxl;	//con el predecesor ( PADRE )

			b=true;

			cout<<" "<<endl;
			cout<<"Por cual nodo desea sustituir el nodo a eliminar?"<<endl;
			cout<<" "<<endl;
			cout<<"1. Predecesor"<<endl;
			cout<<"2. Sucesor"<<endl;
			cout<<" "<<endl;
			cin>>numero;

			switch( numero )
			{
				case 1:
					temp=auxl->izq;
					while (temp->der!=NULL)
					{
						aux2=temp;
						temp=temp->der;
						b=false;
					};
					auxl->info=temp->info; // Cambiar por Predesesor
					cout<<"El predecesor es: "<<endl;
					cout<<auxl->info<<endl;
					break;

				case 2:
					temp=auxl->der;
					while (temp->izq!=NULL)
					{
						aux2=temp;
						temp=temp->izq;
						b=false;
					};
					auxl->info=temp->info; // Cambiar por Sucesor
					cout<<"El sucesor es: "<<endl;
					cout<<auxl->info<<endl;
					break;

				default: cout<<"Error de digitacion"<<endl; /* break; */
			};



			if (b==true)auxl->izq=temp->izq;
			else
			{
				if(temp->izq!=NULL) aux2->der=temp->izq;
				else aux2->der=NULL;
			}

		}
		else
		{ //cuando tiene un solo hijo
			if(auxl->izq==NULL)
				if (aux2!=NULL)
				{
					if (auxl->info<aux2->info)
						 aux2->izq=auxl->der;
					else aux2->der=auxl->der;
				}
				else raiz=auxl->der;
			else
				if(aux2!=NULL)
				{
					if (auxl->info<aux2->info)
						aux2->izq=auxl->izq;
					else aux2->der=auxl->izq;
				}
				else raiz=auxl->izq;
		}
	}
	delete temp;
}
}
};
void main()
{
 nodoarbol *raiz;
 char resp;
 int valor, numero;
 ABB n ;
 do
 {
	n.insertar (); // Agrega un nuevo nodo al arbol
	cout<<"Desea crear otro nodo (s/n):";
	cin>>resp;
	cout<<endl;
	resp=tolower(resp);
 }while(resp!='n');
 cout<<"LOS NODOS DEL ARBOL (inorden) SON"<<endl;
 raiz=n.devolver_raiz();
 n.despliega(raiz);
 do
 {
	cout<<"Entre el valor del nodo a eliminar"<<endl;
	cin>>valor;
	n.eliminar_nodo(valor);
	cout<<endl;

	cout<<" "<<endl;
    cout<<"Como desea eliminar los nodos?"<<endl;
	cout<<" "<<endl;
	cout<<"1. InOrden"<<endl;
	cout<<"2. PreOrden"<<endl;
	cout<<"3. PostOrden"<<endl;
	cout<<" "<<endl;
	cin>>numero;

	switch( numero )
	{
		case 1: raiz=n.devolver_raiz();
			    n.despliega(raiz);
				break;
		case 2: raiz=n.devolver_raiz();
				n.preOrden(raiz);
				break;
		case 3: raiz=n.devolver_raiz();
				n.postOrden(raiz);
				break;
		default: cout<<"Error de digitacion"<<endl; /* break; */
    };

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