#include <time.h>
#include <stdio.h>
 
#include <stdlib.h>
#include <cmath>
#include <iostream>
 
using namespace std;
 
class Nodo
{
    private: 
    int dato;
    Nodo *HijoIzquierdo, *HijoDerecho,*Raiz;
    public:
        Nodo* InsertaNodo(int, Nodo*);
        void EnOrden(Nodo*);
        void PreOrden(Nodo*);
        void PostOrden(Nodo*);
        int Nivel_arbol(Nodo*);
        int NumeroNodo(Nodo*);
        int FE(Nodo*);
        int Total_hojas2(Nodo*);
        int Total_hojas(Nodo*);
        int Suma_nodos(Nodo*);
 
};
 
 
 
//Declaro las funciones que tiene el programa
 
Nodo::Nodo* InsertaNodo(int valor, Nodo*subArbol)
{
   if(subArbol==NULL)
   {
      subArbol=new Nodo;
      subArbol->HijoIzquierdo=subArbol->HijoDerecho=NULL;
      subArbol->dato=valor;
   }
   else
 
      if(valor<subArbol->dato)
         subArbol->HijoIzquierdo=InsertaNodo(valor, subArbol->HijoIzquierdo);
 
      else
         subArbol->HijoDerecho=InsertaNodo(valor, subArbol->HijoDerecho);
   return(subArbol);
}
 
 
void Nodo:: EnOrden(Nodo *subArbol)
{
   if (subArbol!=NULL)
   {
      EnOrden(subArbol->HijoIzquierdo);
      printf("%d ", subArbol->dato);
      EnOrden(subArbol->HijoDerecho);
   }  
}
 
void Nodo:: PreOrden(Nodo *subArbol)
{
   if (subArbol!=NULL)
   {
      printf("%d ", subArbol->dato);
      PreOrden(subArbol->HijoIzquierdo);      
      PreOrden(subArbol->HijoDerecho);
   }  
}
 
void Nodo:: PostOrden(Nodo *subArbol)
{
   if (subArbol!=NULL)
   {
 
      PostOrden(subArbol->HijoIzquierdo);      
      PostOrden(subArbol->HijoDerecho);
      printf("%d ", subArbol->dato);
   }  
}
 
int Nodo:: Nivel_arbol(Nodo *subArbol)
{
    int a=0,b=0;
   if(subArbol==NULL)
   {
      return 0;
   }
 
   else 
   {
      a=Nivel_arbol(subArbol->HijoIzquierdo)+1;
      b=Nivel_arbol(subArbol->HijoDerecho)+1;
   }
   if(a>=b)
      return a; //La raiz no se suma
   else
      return b; //La raiz no se suma
 
}
 
int Nodo:: NumeroNodo (Nodo *subArbol)
{
   if(subArbol==NULL)
      return 0;
 
   else
      return 1+NumeroNodo(subArbol->HijoIzquierdo)+NumeroNodo(subArbol->HijoDerecho);
}
 
int Nodo:: FE(Nodo *subArbol)
{
   if(subArbol==NULL)
      return 0;
 
   else 
      return Nivel_arbol(subArbol->HijoDerecho)-Nivel_arbol(subArbol->HijoIzquierdo);
}
 
int Nodo:: Total_hojas(Nodo *subArbol)
{
   if(Raiz==NULL)
      return 0;
   if(Raiz->HijoDerecho==NULL && Raiz->HijoIzquierdo==NULL)
      return 0;
 
   return Total_hojas2(subArbol);
}
 
int Nodo:: Total_hojas2(Nodo *subArbol)
{
   if(subArbol==NULL)
      return 0;
 
   if(subArbol->HijoDerecho==NULL&&subArbol->HijoIzquierdo==NULL)
      return 1;
 
   return Total_hojas(subArbol->HijoDerecho) + Total_hojas(subArbol->HijoIzquierdo);
 
 
   //return 0;
}
 
int Nodo::Suma_nodos(Nodo *subArbol)
{
   if(subArbol==NULL)
      return 0;
 
   return subArbol->dato + Suma_nodos(subArbol->HijoDerecho) + Suma_nodos(subArbol->HijoIzquierdo);
 
}
 
int main()
{
    Nodo Obj;
 
   int k,num,opc=1,valor,nivel=0,nodos=0,nivel_esperado,frecu=0,hojas=0;
   Nodo *Raiz;
   Raiz=NULL;
 
   while(opc!=11)
   {
      printf("1.- Insertar Arbol\n");
      printf("2.- Recorrido en preorden\n");
      printf("3.- Recorrido  en orden\n");
      printf("4.- Recorrido en postorden\n");
      printf("5.- Nivel del arbol\n");
      printf("6.- Numero de Nodos\n");
      printf("7.- Nivel Perfecto de Nodos\n");
      printf("8.- Factor de Equilibrio\n");
      printf("9.- Numero de Hojas\n");
      printf("10.- Suma de Nodos\n");
      printf("11.- Salir\n");
      scanf("%d",&opc);
 
      switch(opc)
      {
         case 1:
            printf("Inserta Numero para el Arbol\n");
            scanf("%d",&num);
            Raiz=Obj.InsertaNodo(num, Raiz);
            //printf("Quieres seguir...");
            break;
 
         case 2:  Obj.PreOrden(Raiz);
            printf("\n");
            break;
 
         case 3:  Obj.EnOrden(Raiz);
            printf("\n");
            break;
 
         case 4:  Obj.PostOrden(Raiz);
            printf("\n");
            break;
 
         case 5: 
            nivel=Obj.Nivel_arbol(Raiz);
            printf("Nivel del Arbol %d\n", nivel-1);
            break;
 
         case 6:
            nodos=Obj.NumeroNodo(Raiz);
            printf("Numero de Nodos %d\n", nodos);
            break;
 
         case 7:
            nivel_esperado = long(float(Obj.NumeroNodo(Raiz)))/log(2.0);
            printf("El Nivel Perfecto %d\n", nivel_esperado);
            break;
 
         case 8:
            frecu=Obj.FE(Raiz);
            printf("Factor de Equilibrio es %d \n", frecu);
            break;
 
         case 9:
            hojas=Obj.Total_hojas(Raiz);
            printf("La cantidad de Hojas es %d\n",hojas);
            //cout<<hojas<<endl;
            break;
 
         case 10:
            printf("La suma es %d\n", Obj.Suma_nodos(Raiz));
            break;
 
 
 
      }
      //system("cls");
   }
   system("PAUSE");
   return 0;    
 
}