#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;

struct Nodo {
	
	int dato;
	Nodo *der;
	Nodo *izq;
	Nodo *padre;
};

void menu();
Nodo *crearnodo(int, Nodo *);
void insertarnodo(Nodo *&arbol, int, Nodo *);
void imprimirarbol(Nodo *, int);
void eliminar(Nodo *, int);
void eliminarNodo(Nodo *);
Nodo* nodo_de_remplazo(Nodo *);
void reemplazar(Nodo *, Nodo *);
void destruir(Nodo *);






int main()
{
	menu();
	getch();
	return 0;
}


void menu(){
	
	Nodo *arbol=NULL;
	int dato, op, cont=0,b;
	do{
		system("cls"); 
		cout<<"\n M E N U"<<endl;
		cout<<"1.- Insertar un nuevo nodo"<<endl;
		cout<<"2.- Imprimir arbol"<<endl;
		cout<<"3.- Eliminar nodo"<<endl;
		cout<<"4.- Salir"<<endl;
		cout<<"Ingrese opción";
		cin>>op;
		switch(op){
			case 1: cout<<"\n Digite  el valor";
			       cin>>dato;
			       insertarnodo(arbol, dato,NULL);
			       getch();
			       break;
			case 2: cout<<"Imprimir arbol"<<endl;
			        imprimirarbol(arbol,cont);
			        cout<<"\n";
			        getch();
			        break;
			
			case 3: cout<<"\nIngresar nodo a eliminar";
			       cin>>b;
			       eliminar(arbol,b);
			       getch();
			       break;
			case 4: cout<<"A  D  I  O  S";
			        getch();
			        break;
			default: cout<<"fuera de rango"<<endl;
			        getch();
			       
		}
		
		
	}while(op!=4);
}
//crear nuevo nodo del arbol

Nodo *crearnodo(int n, Nodo *padre){
	Nodo *nuevo_nodo= new Nodo();
	
	nuevo_nodo->dato=n;
	nuevo_nodo->der=NULL;
	nuevo_nodo->izq=NULL;
	nuevo_nodo->padre=padre;
	
	return nuevo_nodo;
}

//insertar nodo  del arbol

void insertarnodo(Nodo *&arbol, int n, Nodo *padre){
	
	if(arbol==NULL){
		Nodo *nuevo_nodo=crearnodo(n, padre);
		arbol=nuevo_nodo;
	}
	else{
		
		int valor_raiz=arbol->dato;
		if(n< valor_raiz){
			insertarnodo(arbol->izq,n,arbol);
		}else{
			
			insertarnodo(arbol->der,n,arbol);
		}
	}
}

void imprimirarbol(Nodo *arbol, int numero)
{
	
	if(arbol==NULL){
		return;
		
	}else{
		
		imprimirarbol(arbol->der, numero+3);
		for(int i=0;i<numero;i++){
			cout<<"   ";
		}
		cout<<arbol->dato<<endl;
		imprimirarbol(arbol->izq,numero+3);
	}
	
}


void eliminar(Nodo *arbol, int n){
	if(arbol==NULL){
		return;
	}
	else if(n<arbol->dato){
		eliminar(arbol->izq,n);
	}
	else if(n>arbol->dato){
		eliminar(arbol->der,n);
	}
	else{
		eliminarNodo(arbol);
	}
}



Nodo* nodo_de_remplazo(Nodo *arbol){
	if(arbol==NULL){
		return NULL;
	}
	if(arbol->izq){
		return nodo_de_remplazo(arbol->izq);
		
	}
	
		
	
	else{
		return arbol;
		
	}
}

void reemplazar(Nodo *arbol, Nodo *nuevoNodo){
	if(arbol->padre){
		if(arbol->padre->izq==NULL)
		{
		   arbol->padre->der=nuevoNodo;
		}
		else
		{
		
		if((arbol->dato)==(arbol->padre->izq->dato)){
			arbol->padre->izq=nuevoNodo;
		}
		else if((arbol->dato)==(arbol->padre->der->dato)){
			
			arbol->padre->der=nuevoNodo;
		}
	}
	}
	if(nuevoNodo){
		nuevoNodo->padre=arbol->padre;
	}
	
}

void destruir(Nodo *nodo){
	nodo->izq=NULL;
	nodo->der=NULL;
	nodo->padre=NULL;
	delete nodo;
	
}

void eliminarNodo(Nodo *nodoeliminar){
	if(nodoeliminar->izq && nodoeliminar->der){
		Nodo * menor=nodo_de_remplazo(nodoeliminar->der);
		nodoeliminar->dato=menor->dato;
		eliminarNodo(menor);
	}
    else if(nodoeliminar->izq){
    	reemplazar(nodoeliminar,nodoeliminar->izq);
    	destruir(nodoeliminar);
	}
	else if(nodoeliminar->der){
    	reemplazar(nodoeliminar,nodoeliminar->der);
    	destruir(nodoeliminar);
    }
    else{
    	reemplazar(nodoeliminar,NULL);
    	destruir(nodoeliminar);
	}
}