#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;

template <class T> //ES LO MISMO PONER CLASS O TYPENAME???
class Arbolito2{

private:

    struct  Nodo {
       T dato;
       struct Nodo *der;
       struct Nodo *izq;
	};

    Nodo *Arbol = NULL;

public:
    void  Menu();
    Nodo* CrearNodo(T);
    void  insertar(Nodo *&,T);
    void  Inorden(Nodo *);
    bool  Pertenece(Nodo *,T);
    int CantElem(Nodo *);

};

int main()
{
    Arbolito2<int> Arb;
    Arb.Menu();

    getch();
    return 0;
}


//-------------------------------------------
template <class T>
void Arbolito2<T>::insertar(Arbolito2<T>::Nodo *&Arbol,T n)
{
    if(Arbol == NULL)
    {
     Arbol= CrearNodo(n);
    }
    else
    {
        if(n < Arbol->dato)
            insertar(Arbol->izq,n);
        else
            insertar(Arbol->der,n);
    }
}

//-------------------------------------------
template <class T>
void Arbolito2<T>::Inorden(Arbolito2<T>::Nodo *Arbol){
    if(Arbol != NULL)
    {
        Inorden(Arbol->izq);
        cout<<Arbol->dato<<" ";
        Inorden(Arbol->der);
    }
}
//-------------------------------------------
template <class T>
Arbolito2<T>::Nodo Arbolito2<T>::*CrearNodo(T n){
    Nodo *Nuevo_Nodo = new  Nodo();

    Nuevo_Nodo->dato = n;
    Nuevo_Nodo->der = NULL;
    Nuevo_Nodo->izq = NULL;

    return Nuevo_Nodo;
}
//-------------------------------------------
template <class T>
bool Arbolito2<T>::Pertenece(Arbolito2<T>::Nodo *Arbol, T n)
{
    if(Arbol!=NULL)
    {
        if(Arbol->dato == n)
        {
            bool esta = true;
            return  esta;
        }
        else
        {
            if(n < Arbol->dato)
                Pertenece(Arbol->izq,n);
            else
                Pertenece(Arbol->der,n);
        }
    }
    else{
        bool esta = false;
        return esta;
    }
}
//-------------------------------------------
template <class T>
int Arbolito2<T>::CantElem(Arbolito2<T>::Nodo *Arbol){
    if(Arbol != NULL)
    {
        int Long = 1 + CantElem(Arbol->izq) +CantElem(Arbol->der);
        return Long;
    }
}
//-------------------------------------------
template <class T>
void Arbolito2<T>::Menu()
{
    T dato;
    int op;
    bool esta;
    do{
        cout<<"\t :MENU:."<<endl;
        cout<<"1. insertar nuevo nodo."<<endl;
        cout<<"2. Imprimir el Arbol Inorden."<<endl;
        cout<<"3. Pertenencia de un elemento al arbol."<<endl;
        cout<<"4. Cantidad de Elementos del Arbol."<<endl;
        cout<<"5. Consulta si el Arbol Esta Vacio."<<endl;
        cout<<"6. Salir."<<endl;
        cin>>op;

        switch(op){
            case 1:
                cout<<"\nDigite un numero : ";
                cin>>dato;
                if(Pertenece(Arbol,dato))
                    cout<<"El Elemento ya se Encuentra en el Arbol"<<endl;
                else
                    insertar(Arbol,dato);
                cout<<"\n";
                system("pause");
                break;
            case 2:
                cout<<"LOS NODOS SON: "<<endl;
                Inorden(Arbol);
                system("pause");
                break;
            case 3:
                cout<<"ingrese el elemento que desea buscar en el Arbol : "<<endl;
                cin>>dato;
                esta = Pertenece(Arbol,dato);
                if(esta)
                    cout<<"el elemento SI se encuentra en el arbol"<<endl;
                else
                    cout<<"el elemento NO se encuentra en el arbol"<<endl;
                system("pause");
                break;
            case 4:
                cout<<" La Cantidad de Elementos es : "<< CantElem(Arbol)<<endl;
                system("pause");
                break;
            case 5:
                if(CantElem(Arbol)==0)
                    cout<<" EL ARBOL ESTA VACIO."<<endl;
                else
                    cout<<" EL ARBOL CONTIENE ELEMENTOS."<<endl;
                system("pause");
                break;
        }
        system("cls");
    }   while(op!=6);
}