#include <iostream>
using namespace std;

class Nodo
{
public:
int ele, nhijos;
Nodo *padre;
Nodo *izq;
Nodo *der;
Nodo();
};

Nodo::Nodo()
{
ele=0;
nhijos=0;
}

class ArbolBinario
{
public:
Nodo *raiz;
int cnodo, choja, con, sum, profu;
ArbolBinario();
void Insertar(int e);
//void Eliminar();
void Imprimir_Pre(Nodo *actual);
void Imprimir_Orden(Nodo *actual);
void Imprimir_Post(Nodo *actual);
void Busqueda(Nodo *actual, int e);
void Busqueda2(Nodo *actual, int e);
void Recorrer(Nodo *actual);
void Encontrar(Nodo *actual, int maymen);
};

ArbolBinario::ArbolBinario()
{
raiz=NULL;
cnodo=0;
choja=0;
sum=0;
profu=-999;
}

void ArbolBinario::Insertar(int e)
{
int nro=0;
Nodo *actual, *siguiente;
if (raiz==NULL)
{
Nodo *nuevo=new Nodo;
nuevo->ele=e;
nuevo->izq=NULL;
nuevo->der=NULL;
nuevo->padre=NULL;
raiz=nuevo;
sum+=e;
cnodo++;
}
else
{
actual=raiz;
siguiente=raiz;
Nodo *nuevo=new Nodo;
nuevo->ele=e;
nuevo->izq=NULL;
nuevo->der=NULL;
nuevo->padre=NULL;
actual->nhijos+=1;
while(e!=nro && siguiente!=NULL)
{
nro=siguiente->ele;
actual=siguiente;
if (e<nro)
{
siguiente=actual->izq;
}
else
{
siguiente=actual->der;
}
}
if (e==(actual->ele))
{
cout <<"Es un duplicado!\n";
}
else
{
cnodo++;
sum+=e;
//actual->nhijos+=1;
if (e<(actual->ele))
{
actual->izq=nuevo;
nuevo->padre=actual;
}
else
{
actual->der=nuevo;
nuevo->padre=actual;
}
}
}
}

void ArbolBinario::Imprimir_Pre(Nodo *actual)
{
if (actual==NULL)
{
return;
}
else
{
cout <<actual->ele<<"\n";
Imprimir_Pre(actual->izq);
Imprimir_Pre(actual->der);
}
}

void ArbolBinario::Imprimir_Orden(Nodo *actual)
{
if (actual==NULL)
{
return;
}
else
{
Imprimir_Orden(actual->izq);
cout <<actual->ele<<"\n";
Imprimir_Orden(actual->der);
}
}

void ArbolBinario::Imprimir_Post(Nodo *actual)
{
if (actual==NULL)
{
return;
}
else
{
Imprimir_Post(actual->izq);
Imprimir_Post(actual->der);
cout <<actual->ele<<"\n";
}
}

void ArbolBinario::Busqueda(Nodo *actual, int e)
{
Nodo *papa=NULL, *abuelo=NULL;
if (actual==NULL)
{
cout <<"No se encontro el elemento!\n";
return;
}
else
{
papa=actual->padre;
if (papa!=NULL)
{
abuelo=papa->padre;
}
if (actual->ele==e)
{
cout <<"El elemento "<<actual->ele<<" fue encontrado!\n";
if (papa!=NULL) cout <<"El padre del mismo es: "<<papa->ele;
if (abuelo!=NULL) cout <<"\nEl abuelo es: "<<abuelo->ele;
cout <<"\n";
}
else if (e>actual->ele)
{
Busqueda(actual->der, e);
}
else
{
Busqueda(actual->izq, e);
}
}
}

void ArbolBinario::Busqueda2(Nodo *actual, int e)
{
Nodo *antecesor=NULL;
if (actual==NULL)
{
cout <<"No se encontro el elemento!\n";
return;
}
else
{
if (actual->ele==e)
{
cout <<actual->ele<<"\n";
antecesor=actual->padre;
while (antecesor!=NULL)
{
cout <<antecesor->ele<<"\n";
antecesor=antecesor->padre;
}
}
else if (e>actual->ele)
{
Busqueda2(actual->der, e);
}
else
{
Busqueda2(actual->izq, e);
}
}
}

void ArbolBinario::Recorrer(Nodo *actual)
{
Nodo *antecesor=NULL;
if (actual==NULL)
{
return;
}
else
{
if (actual->izq==NULL && actual->der==NULL)
{
con=0;
choja++;
antecesor=actual->padre;
while (antecesor!=NULL)
{
con++;
antecesor=antecesor->padre;
}
con++;
if (con>profu)
{
profu=con;
}
}
Recorrer(actual->izq);
Recorrer(actual->der);
}

}

void ArbolBinario::Encontrar(Nodo *actual, int maymen)
{
Nodo *sucesor, *antecesor;
antecesor=actual;
if (maymen==1)
{
sucesor=actual->izq;
while (sucesor!=NULL)
{
antecesor=sucesor;
sucesor=sucesor->izq;
}
cout <<"El menor elemento es: "<<antecesor->ele;
}
else
{
sucesor=actual->der;
while (sucesor!=NULL)
{
antecesor=sucesor;
sucesor=sucesor->der;
}
cout <<"El mayor elemento es: "<<antecesor->ele;
}
cout <<"\n";
}