#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"; 
}