#include <iostream>
#include <string>
using namespace std;
class listaAdy;
class nodoV;
class nodoArc;
typedef struct reg{
string nombre;
float x;
float y;
listaAdy Ady;
};

typedef class nodoV {
public:
nodoV *hIzq, *hDer;//Declaracion del nodo con sus dos hijos.
reg estado;
};
class nodoArc{
		public:
		nodoV *Vert;
		nodoArc *sig;
		};

class listaAdy{
public:

nodoArc *primerarco;

public:

void crearlista (){
primerarco=NULL;
}

	void insertarenlista (nodoV *k){
	nodoArc *nodonuevo, *apuntadoraux;
	nodonuevo=new nodoArc;
	if (nodonuevo != NULL){
	nodonuevo->Vert=k;
	nodonuevo->sig=NULL;
	if(primerarco==NULL){
	primerarco=nodonuevo;
	}else{
	apuntadoraux=primerarco;
	while(apuntadoraux->sig!=NULL){
	apuntadoraux=apuntadoraux->sig;
	}
	apuntadoraux->sig=nodonuevo;
	}
	}

}

void mostrarlista (){
nodoArc *apuntadoraux;
int i;i=1;
apuntadoraux=primerarco;
while(apuntadoraux!=NULL){
	cout<<"La cuidad tiene relacion con: "<<apuntadoraux->Vert->estado.nombre<<endl;
	apuntadoraux=apuntadoraux->sig;
	i++;
	}

}

};



class arbin {
public:
nodoV *Raiz; //Raiz del arbol.
int cont;

creararbol(){ //Inicializacion del arbol para que quede vacío.
Raiz=NULL;
cont=0;
}

buscar (string e, nodoV *&actual, nodoV *&anterior){ // Función buscar: Esta funcion es llamada desde insertar para ahorrar recorridos y optimizar el programa ya que informara si existe o no, un elemento no puede estar duplicado.
bool encontrado;
encontrado=false;
anterior=NULL;
actual=Raiz;
	while(!(encontrado)&&(actual!=NULL)){
		if(actual->estado.nombre==e){
		encontrado=true;
		}else{
		anterior=actual;
				if(actual->estado.nombre > e){
				actual=actual->hIzq;
				}else{
				actual=actual->hDer;
				}
			}
}
if(!(encontrado)){
cout<<"No se encontro el elemento"<<endl;
}
else{
cout<<"El elemento existe"<<endl;
}
}

insertar (reg estado){
nodoV *nuevo, *actual, *anterior;//Funcion insertar.
buscar(estado.nombre,actual,anterior);// <- En esta parte usamos buscar, en actual se alojara la posicion de la ultima hoja a la cual le agregaremos el hijo y en anterior se alojara su padre.
if(actual!=NULL){
cout<<"elemento duplicado"<<endl;
}else{
nuevo = new nodoV;
nuevo->estado=estado;
nuevo->hDer=NULL;
nuevo->hIzq=NULL;
if(anterior==NULL){Raiz=nuevo;}else{
if(anterior->estado.nombre > estado.nombre){
anterior->hIzq=nuevo;
}else{
anterior->hDer=nuevo;
}
}
}
}

eliminar (string x){
nodoV *n, *actual, *anterior, *aux,*aux2,*aux3,*aux4;
buscar(x, actual, anterior);
aux=actual;
if(actual==NULL){
cout<<"Elemento inexistente"<<endl;
}else{
		if((actual->hIzq == NULL)&&(actual->hDer==NULL)){
			if(anterior->hDer==actual){anterior->hDer=NULL;}
			if(anterior->hIzq==actual){anterior->hIzq=NULL;}
		}
		if((actual->hIzq!=NULL)&&(actual->hDer==NULL)){
		if(anterior->hIzq==actual){anterior->hIzq=actual->hIzq;}
		if(anterior->hDer==actual){anterior->hDer=actual->hIzq;}
		}
		if((actual->hIzq==NULL)&&(actual->hDer!=NULL)){
		if(anterior->hIzq==actual){anterior->hIzq=actual->hDer;}
		if(anterior->hDer==actual){anterior->hDer=actual->hDer;}
		}

		if ((actual->hIzq!=NULL)&&(actual->hDer!=NULL)){
		aux2=actual;
		eliminarmenor(actual,aux3, x);
		aux2->estado.nombre=x;
}
}
}


eliminarmenor(nodoV *&apunt, nodoV *&aux3, string &x){
nodoV *aux;
if(apunt->hIzq==NULL){
aux=apunt;if(apunt->hDer!=NULL){aux3=apunt->hDer;}else{aux3=apunt;}
x=aux3->estado.nombre;
if((apunt->hDer==NULL)&&(apunt->hIzq==NULL)){apunt=NULL;}else{
apunt->hDer=NULL;
apunt->hIzq=NULL;
}
}else{
eliminarmenor(apunt->hIzq,aux3, x);
}
}


};
//recorridos
preorden(nodoV *raiz){
 if(raiz!=NULL){
 cout<<raiz->estado.nombre<<" ->";
 preorden(raiz->hIzq);
 preorden(raiz->hDer);
 }
 }
 inorden(nodoV *raiz){
 if(raiz!=NULL){
 inorden(raiz->hIzq);
 cout<<raiz->estado.nombre<<" ->";
 inorden(raiz->hDer);
 }
 }
 postorden(nodoV *raiz){
 if(raiz!=NULL){
 postorden(raiz->hIzq);
 postorden(raiz->hDer);
 cout<<raiz->estado.nombre<<" ->";
 }
 }


int main(){
arbin ar;
ar.creararbol();
reg uno, dos, tres;
uno.nombre="Caracas";
dos.nombre="Anzoategui";
tres.nombre="Zulia";
ar.insertar(uno);
ar.insertar(dos);
ar.insertar(tres);
cout<<endl;cout<<"pre: ";
preorden(ar.Raiz);
cout<<endl;cout<<"in: ";
inorden(ar.Raiz);
cout<<endl;cout<<"post: ";
postorden(ar.Raiz);
ar.eliminar("Anzoategui");
cout<<endl;cout<<"pre: ";
preorden(ar.Raiz);
cout<<endl;cout<<"in: ";
inorden(ar.Raiz);
cout<<endl;cout<<"post: ";
postorden(ar.Raiz);
ar.eliminar("Zulia");
cout<<endl;cout<<"pre: ";
preorden(ar.Raiz);
cout<<endl;cout<<"in: ";
inorden(ar.Raiz);
cout<<endl;cout<<"post: ";
postorden(ar.Raiz);



}