#include <stdio.h>
#include <stdlib.h>

#define SIN_MEMORIA 0
#define CLAVE_DUPLICADA 0
#define TODO_BIEN 1
#define FALLO_ABRIR_ARCHIVO 0
#define NO_PUDO_GUARDAR_ARBOL 0
#define FALLO_CREAR_ARCHIVO 0

typedef struct
{
    int num;
}t_info;

typedef struct s_nodo
{   t_info info;
    struct s_nodo *der;
    struct s_nodo *izq;
}t_nodo;

typedef t_nodo* t_arbol;

int menu();
void crearArbol(t_arbol*);
int insertarNodoIterativo(t_arbol*, const t_info*);
int insertarNodoRecursivo(t_arbol*,const t_info*);
int compara(const t_info*,const t_info*);
void preorden(const t_arbol*);
void inorden (const t_arbol*);
void posorden(const t_arbol*);
void mostrar(const t_info*);
void grabarEnArchivo(t_arbol*,FILE*);
int guardarArbol(t_arbol*,FILE*);
int recuperarDeArchivo(t_arbol*,FILE*);
int contarNodos(t_arbol*);
int contarHojas(t_arbol*);
int contarHojasSubarbolDerecho(t_arbol*);
int contarNodosNoHojas(t_arbol*);
int contarNodosconHI(t_arbol*);
int contarHSI(t_arbol*);
int contarPadresSoloCHI(t_arbol*);
int contarNodosMayoresYPares(t_arbol*);
t_nodo* buscarNodo(t_arbol*, const t_info*);
int eliminarHojas(t_arbol*);
void eliminarArbol(t_arbol*);
int eliminarHojasConClave(t_arbol*, const t_info*);
int eliminarSubArbolConClave(t_arbol*, const t_info*);
float promedioArbol(t_arbol*,int*);
int mostrarNoHojas(t_arbol *);


int main()
{
    t_arbol raiz;
    t_info d;
    int opcion;
    t_info clave;
    FILE* pf;
    int sum=0;

     //crearArbol(&raiz);
    while((opcion=menu())!=0)
    {
        switch(opcion)
        {
                case 1:

                        crearArbol(&raiz);
                        printf("Arbol creado correctamente \n");
                        break;
                case 2:

                      printf("Ingresar de forma Iterativa...\n");
                      printf("Ingrese un mumero:\n");
                      scanf("%d",&d.num);
                      if(insertarNodoIterativo(&raiz,&d))
                        printf("Inserto Nodo Correctamente\n");
                      else
                        printf("No se pudo insertar en arbol\n");
                    break;
                case 3:
                       printf("Ingresar de forma Recursiva...\n");
                       printf("Ingrese un mumero:\n");
                       scanf("%d",&d.num);
                       if(insertarNodoRecursivo(&raiz,&d))
                            printf("Inseto Nodo Correctamente\n");
                       else
                         printf("No se pudo insertar en arbol\n");
                    break;
                case 4:
                        printf("Mostrar en preorden...\n");
                        preorden(&raiz);
                        if(raiz==NULL)
                            printf("Arbol Vacio\n");
                        break;

                case 5:
                    printf("Mostrar en inOrden...\n");
                    inorden(&raiz);
                    printf("\n");
                    break;

                case 6:
                    printf("Mostrar en posOrden...\n");
                    posorden(&raiz);
                    break;

                case 7:
                    //if(!(pf=fopen("ArchivoArbol","rb")))
                        if(!(pf=fopen("ArchivoArbol1","wb")))
                            return FALLO_CREAR_ARCHIVO;
                    printf("**************** Guardar el Arbol en Archivo *********************\n");
                    if(guardarArbol(&raiz,pf)==0)
                        printf("No pudo guardar Arbol\n");
                    else
                        printf("Arbol Guardado Correctamente\n");


                        fclose(pf);
                break;

                case 8:
                    crearArbol(&raiz);
                    printf("Recuperar el Arbol de Archivo\n");
                    if(!(pf=fopen("ArchivoArbol1","rb")))
                      return FALLO_ABRIR_ARCHIVO;
                    if(!recuperarDeArchivo(&raiz,pf))
                        printf("No se pudo recuperar datos del arbol\n\n");
                    fclose(pf);
                break;

                case 9:
                    printf("************ CONTAR NODOS ******************\n");
                    printf("Cantidad de nodos en el arbol: %d\t\n\n", contarNodos(&raiz));
                    break;

                case 10:
                    printf("************ CONTAR HOJAS *******************\n");
                    printf("Cantidad de hojas en el arbol: %d\t\n\n", contarHojas(&raiz));
                    break;

                case 11:
                    printf("Hojas del subarbol derecho: %d\t\n\n", contarHojasSubarbolDerecho(&raiz));
                    break;

                case 12:
                    printf("Contar nodos no Hojas\n");
                    printf("Nodos no hojas: %d\t\n\n", contarNodosNoHojas(&raiz));
                    break;

                case 13:
                    printf("***************** Contar nodos con Hijos Izquierda ****************\n");
                    printf("Nodos con hijos a la izquierda: %d\t\n\n", contarNodosconHI(&raiz));
                    break;

                case 14:
                    printf("***************** Contar hijos solo a la izquierda *****************\n");
                    printf("Hijos a la izquierda: %d\t\n\n", contarHSI(&raiz));
                    break;

                case 15:
                    printf("********** Padres con hijos solo a la izquierda *********************\n");
                    printf("Padres con hijos solo a la izquierda: %d\t\n\n", contarPadresSoloCHI(&raiz));
                    break;

                case 16:
                    printf("************* Nodos Pares y Mayores a 50 ****************************\n");
                    printf("Nodos pares y mayores a 50: %d\t\n\n", contarNodosMayoresYPares(&raiz));
                    break;

                case 17:
                    printf("******** Buscar por una clave dada y retornar direccion **************\n");
                    printf("Ingrese la clave de busqueda: ");
                    scanf("%d",&d);
                    printf("La direccion de la clave %d es %p\n", d,buscarNodo(&raiz,&d));

                case 18:
                    printf("************* Eliminar las hojas **********************************\n");
                    printf("Hojas eliminadas: %d\t\n", eliminarHojas(&raiz));
                    break;

                case 19:
                    printf("******************** Eliminar Arbol ********************************\n");
                    eliminarArbol(&raiz);
                    break;

                case 20:
                    printf("*********** Eliminar hojas a partir de una clave *******************\n");
                    printf("Ingrese la clave: ");
                    scanf("%d", & d);
                    printf("Se eliminaron %d hojas\t\n", eliminarHojasConClave(&raiz,&d));
                    break;

                case 21:
                    printf("************ Eliminar Subarbol a partir de una clave *****************\n");
                    printf("Ingrese la clave: ");
                    scanf("%d", & d);
                    printf("Se eliminaron %d nodos del subArbol desde la clave %d", eliminarSubArbolConClave(&raiz,&d), d);
                    break;

                case 22:
                    printf("***************** Promedio del Arbol *******************************)");
                    printf("el promedio del Arbol es: %f", (float)sum/promedioArbol(&raiz,&sum));
                    break;
                case 23:
                    printf("***************** Mostrar No Hojas *******************************)");
                    printf("Mostrar no nodos en el arbol: %d\t\n\n", mostrarNoHojas(&raiz));
                    break;
        }

    }
   //fclose(pf);
return 1;
}
////////////////////////////////////////
int menu(void)
{
    int opcion;
    do{
        printf("1 -  Crear Arbol \n");
        printf("2 -  Insertar Nodo Iterativo \n");
        printf("3 -  Insertar Nodo Recursivo \n");
        printf("4 -  Recorrido PREORDEN \n");
        printf("5 -  Recorrido INORDEN \n");
        printf("6 -  Recorrido POSORDEN \n");
        printf("7 -  Guardar el Arbol a un Archivo \n");
        printf("8 -  Recuperar el Arbol desde un Archivo \n");
        printf("9 -  Contar Nodos\n");
        printf("10-  Contar Hojas\n");
        printf("11-  Contar Hojas sub Arbol Derecho\n");
        printf("12-  Contar Nodos no Hojas\n");
        printf("13-  Contar Nodos con Hijos a la izquierda\n");
        printf("14-  Contar hijos solo a la izquierda\n");
        printf("15-  Contar Padres con Hijos solo a la izquierda\n");
        printf("16-  Contar nodos pares y mayores a 50\n");
        printf("17-  Buscar por una clave dada\n");
        printf("18-  Eliminar las hojas\n");
        printf("19-  Eliminar Arbol\n");
        printf("20-  Eliminar hojas a partir de una clave\n");
        printf("21-  Eliminar un SubArbol a partir de una clave\n");
        printf("22-  Promedio del Arbol\n");
        printf("23-  Mostrar no hojas\n");

        printf("0-  Salir \n");
        scanf("%d",&opcion);

    }while(opcion<0&&opcion>22);
    //system("cls");
}
//////////////////////////////////////////////////
void crearArbol(t_arbol*p)
{
    *p=NULL;
}
//////////////////////////////////
int insertarNodoIterativo(t_arbol* p, const t_info *d)
{int cmp;
    while(*p)
    {
        if((cmp=compara(d,&(*p)->info))==0)
           return CLAVE_DUPLICADA;
         if(cmp<0)
            p=&(*p)->izq;
         else
            p=&(*p)->der;

    }
    ///poner en nodo
    *p=(t_nodo*) malloc(sizeof(t_nodo));
    if(!(*p))
        return SIN_MEMORIA;
    (*p)->info=*d;
    (*p)->izq=(*p)->der=NULL;
    return TODO_BIEN;
}
///////////////////////////////////////
int insertarNodoRecursivo(t_arbol* p, const t_info*d)
{int cmp;
    if(*p)
    {
       if((cmp=compara(d,&(*p)->info))==0)
           return CLAVE_DUPLICADA;
           if(cmp<0)
                insertarNodoRecursivo(&(*p)->izq,d);
           else
                insertarNodoRecursivo(&(*p)->der,d);
    }
    else
    {
           //poner en nodo
        *p=(t_nodo*) malloc(sizeof(t_nodo));
        if(!(*p))
            return SIN_MEMORIA;
        (*p)->info=*d;
        (*p)->izq=(*p)->der=NULL;
        return TODO_BIEN;
    }

}
///////////////////////////////////
int compara(const t_info* d,const t_info* p )
{
    if(d->num < p->num)
        return -1;
    if(d->num > p->num)
        return 1;
    return 0;
}
/////////////////////////////////////
void preorden(const t_arbol *p)
{
    if(*p)
    {
        mostrar(&(*p)->info);
        preorden(&(*p)->izq);
        preorden(&(*p)->der);
    }
}
///////////////////////////////
void inorden(const t_arbol*p)
{
    if(*p)
    {
        inorden(&(*p)->izq);
        mostrar(&(*p)->info);
        inorden(&(*p)->der);
    }
}
//////////////////////////////////////
void posorden(const t_arbol*p)
{
    if(*p)
    {
        posorden(&(*p)->izq);
        posorden(&(*p)->der);
        mostrar(&(*p)->info);
    }
}
//////////////////////////////
void mostrar(const t_info* p)
{
    //mostrar(&(*p)->izq);
    printf("%d\t",p->num);
    printf("\n");
    //mostrar(&(*p)->der);
}

///////////////////////////////////////////////
void grabarenArchivo(t_arbol* p ,FILE* pf)
{
    fwrite(&(*p)->info.num,sizeof(t_info),1,pf);
}

////////////////////////////////////////////////////
int guardarArbol(t_arbol* p, FILE* pf)
{
    //printf("Grabo correctamente\n");
    if(*p)
    {
        grabarenArchivo(p,pf);
        guardarArbol(&(*p)->izq,pf);
        guardarArbol(&(*p)->der,pf);
        return 1;
    }
    return 0;
}

//////////////////////////////////////////////////////////////////
int recuperarDeArchivo(t_arbol* p, FILE* pf)
{
    t_info aux;
    fread(&aux,sizeof(t_info),1,pf);
    while(!feof(pf))
    {
       if(insertarNodoIterativo(p,&aux))
            fread(&aux,sizeof(t_info),1,pf);
        else
            return 0;
    }
    return 1;
}

///////////////////////////////////////////////////////////////////////

int contarNodos(t_arbol* p)
{
    if(*p)
        return 1+ contarNodos(&(*p)->izq) + contarNodos(&(*p)->der);
    return 0;
}
/*
int contarHojas(t_arbol* p)
{
    if(*p)
    {
        if((*p)->izq==NULL && (*p)->der==NULL)
            return 1;
        return contarHojas(&(*p)->izq)+ contarHojas(&(*p)->der);
    }
    return 0;
}
*/

int contarHojas(t_arbol *p)
{
    if(!*p)
        return 0;
    return (((*p)->izq==NULL)&&((*p)->der==NULL))?1:0+contarHojas(&(*p)->izq == NULL)+contarHojas(&(*p)->der);
}
///////////////////////////////////////////////////////////////////////

int contarHojasSubarbolDerecho(t_arbol* p)
{
    if(*p)
        return contarHojas(&(*p)->der);
}

int contarNodosNoHojas(t_arbol* p)
{
    if(!(*p))
        return 0;
    if((*p)->izq ||(*p)->der)
        return 1+contarNodosNoHojas(&(*p)->izq)+contarNodosNoHojas(&(*p)->der);
    return 0;
}

int contarNodosconHI(t_arbol* p)
{
    if(!(*p))
        return 0;
    if((*p)->izq)
        return contarNodosconHI(&(*p)->izq)+contarNodosconHI(&(*p)->der)+1;
    return contarNodosconHI(&(*p)->der);
}

int contarHSI(t_arbol* p)///Hijos a la izquierda y no tienen hijos a la derecha
{
    if(!(*p))
        return 0;
    return contarHSI(&(*p)->izq)+contarHSI(&(*p)->der)+(((*p)->izq) && !(*p)->der)?1:0;
}

int contarPadresSoloCHI(t_arbol* p)
{
    if(!(*p))
        return 0;
    return contarPadresSoloCHI(&(*p)->izq)+contarPadresSoloCHI(&(*p)->der)+((*p)->izq && !(*p)->der)?1:0;
}

int contarNodosMayoresYPares(t_arbol* p)
{
    if(*p)
    {
        return contarNodosMayoresYPares(&(*p)->izq) + contarNodosMayoresYPares(&(*p)->der) + (((*p)->info.num)>50 && (((*p)->info.num)%2==0)?1:0);
    }
    return 0;
}

t_nodo* buscarNodo(t_arbol* p, const t_info* d)
{
    int cmp;
    if(*p)
    {
        if((cmp=compara(d,&(*p)->info))==0)
            return *p;
        if(cmp<0)
            return buscarNodo(&(*p)->izq,d);
        else
            return buscarNodo(&(*p)->der,d);
    }
    return NULL;
}

int eliminarHojas(t_arbol* p)
{
    if(*p)
    {
        if(!(*p)->izq && !(*p)->der)//if((*p)->izq == (*p)->der)
        {
            free(*p);
            *p=NULL;
            return 1;
        }
        return eliminarHojas(&(*p)->izq)+eliminarHojas(&(*p)->der);
    }
}
void eliminarArbol(t_arbol* p)
{
    if(*p)
    {
        eliminarArbol(&(*p)->izq);
        eliminarArbol(&(*p)->der);
        free(*p);
        *p=NULL;
    }
}

int eliminarHojasConClave(t_arbol* p, const t_info* d)
{
    int cmp;
    if(*p)
    {
        cmp=compara(d,&(*p)->info);
        if(cmp==0)
        {
            return eliminarHojas(&(*p)->izq)+eliminarHojas(&(*p)->der);
        }
        if(cmp<0)
            return eliminarHojasConClave(&(*p)->izq,d);
        else
            return eliminarHojasConClave(&(*p)->der,d);
    }
    return 0;
}

int eliminarSubArbolConClave(t_arbol* p, const t_info* d)
{
    t_nodo* nodo;
    if(nodo=buscarNodo(p,d))
    {
       eliminarArbol(&(*nodo).izq);
       eliminarArbol(&(*nodo).der);
       ///eliminarArbol(nodo);
       return 1;
    }
     return 0;
}

/*float promedioArbol(t_arbol* p)
{
    int cont=0;

    int acum=0;
    if(*p)
    {
       cont=sumaracumulararbol(p,&acum);
       return (float) acum/cont;
    }
    return 0;
    *p==NULL;
}

int sumaracumulararbol(t_arbol* p,int* acum)
{
    if(*p)
    {
        printf("%d\n",(*p)->info.num);
        (*acum)+=(*p)->info.num;
        return 1 + sumaracumulararbol(&(*p)->izq,acum)+sumaracumulararbol(&(*p)->der,acum);

        printf("%d: ",acum);

    }
    return 0;
}
*/

float promedioArbol(t_arbol* p,int* sum)
{
    if(*p)
    {
        return promedioArbol(&(*p)->izq,sum)+((*p)->izq?1:0);
            if((*p)->izq)
                *sum+=(*p)->info.num;

        return promedioArbol(&(*p)->der,sum)+((*p)->der?1:0);
            if((*p)->der)
                *sum+=(*p)->info.num;
    }
    return 0;
}

int mostrarNoHojas(t_arbol *p)
{
    int aux=0;
    if(*p==NULL)
        return;
    if((*p)->izq != NULL || (*p)->der !=  NULL)
    {
        printf("%d",(*p)->info.num);
        aux++;
    }
    aux += mostrarNoHojas(&((*p)->izq));
    aux += mostrarNoHojas(&((*p)->der));
    return aux;
}
/*
int eliminarHojas(t_arbol *p)
{
    if(*p)
        return 0;
    if(!(*p)->izq && !(*p)->der )
    {
        free(*p);
        *p=NULL;
        return 1;
    }
    else
    {
      return   eliminarHojas(&(*p)->izq) + //elimina y cuenta
        eliminarHojas(&(*p)->der);
    }
}
*/
/*
void eliminarArbol(t_arbol *p)
int eliminarArbol(t_arbol *p) //para contar
{
    int aux=0;
    if(!*p)

        return;
      (eliminarArbol(&(*p)->izq)+eliminarArbol(&(*p)->der)+1);
     free(*p);

}
*/
/*

int eliminarArbol(t_arbol *p) //para contar
{
    int aux=0;
    if(!*p)

        return 0;
      aux+=eliminarArbol(&(*p)->izq);
      aux+=eliminarArbol(&(*p)->der);
     free(*p);
     *p=NULL;
     return aux;

}
*/

/*
int altura(t_arbol*p)
{
    int hd,hi;
    if(!*0)
        return 0; //0 nivel , 1 altura
    hd=altura(&(*p)->der);
    hi=altura(&(*p)->izq);
    return hd>hi?hd+1:hi+1;0
}
*/