#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);
bool busqueda (Nodo *arbol, int n);
void recorrer_preorden(Nodo *arbol);
void recorrer_inorden(Nodo *arbol);
void recorrer_posorden(Nodo *arbol);


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


void menu(){
	
	Nodo *arbol=NULL;
	int dato, op, cont=0,b,p=1, p1=1;
	do{
		system("cls"); 
		cout<<"\n M E N U"<<endl;
		cout<<"1.- Insertar un nuevo nodo"<<endl;
		cout<<"2.- Imprimir arbol"<<endl;
		cout<<"3.- buscar elemento"<<endl;
		cout<<"4.- Recorrer preorden"<<endl;
		cout<<"5.- Recorrer inorden"<<endl;
		cout<<"6.- Recorrer posorden"<<endl;
		cout<<"7.- 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 buscar";
			        cin>>b;
			        if(busqueda(arbol,b)==true){
			        	 cout<<"Elemento encontrado";
				    }
				    else
				    cout<<"Elemento no encontrado"<<endl;
				    getch();
				    break;
			case 4: cout<<"\nbusqueda en profundidad preorden\n";
			        recorrer_preorden(arbol);
			        getch();
			        break;
			        
			case 5: cout<<"\nbusqueda en profundidad inorden\n";
			        recorrer_inorden(arbol);
			        getch();
			        break;     
			case 6: cout<<"\nbusqueda en profundidad posorden\n";
			        recorrer_posorden(arbol);
			        getch();
			        break; 
		
			case 7: cout<<"A  D  I  O  S";
			        getch();
			        break;
			default: cout<<"fuera de rango"<<endl;
			        getch();
			        break;
			       
		}
		
		
	}while(op!=7);
}
//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;
		getch();
		imprimirarbol(arbol->izq,numero+3);
	}
	
}

bool busqueda (Nodo *arbol, int n){
	
	if(arbol==NULL){
		return false;
	}
	
	else if(arbol->dato==n){
		return true;
	}
	else if(n<arbol->dato){
		return busqueda(arbol->izq,n);
	}
	else{
		return busqueda(arbol->der,n);
	}
		
}

void recorrer_preorden(Nodo *arbol){
	if(arbol==NULL){
		return;
	}
	else{
		cout<<arbol->dato<<"---";
		recorrer_preorden(arbol->izq);
		recorrer_preorden(arbol->der);
	}
}

void recorrer_inorden(Nodo *arbol){
	if(arbol==NULL){
			return;
	}
	else{
		recorrer_inorden(arbol->izq);
		cout<<arbol->dato<<"---";
		recorrer_inorden(arbol->der);
	}
}

void recorrer_posorden(Nodo *arbol){
	if(arbol==NULL){
		return;
	}
	else{
		
		recorrer_posorden(arbol->izq);
		recorrer_posorden(arbol->der);
		cout<<arbol->dato<<"---";
	}
}