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

// struttura dati albero
struct nodo{
  unsigned char dato;
  int occorrenze;
  struct nodo *maggiori,*minori;
  };

// prototipi
struct nodo* inserisci_in_albero(struct nodo *albero, const unsigned char dato);
void stampa_valori(struct nodo *a);
int profondita_albero(struct nodo *a);
int dimensione_albero(struct nodo *a);

int main(int argc, char **argv){
  FILE *fin; // file da analizzare
  int r; // carattere in lettura
  struct nodo *tree=NULL; // struttura dati

  // controllo esistenza argomento
  if(argc<2){
    fprintf(stderr,"Errore: manca il nome del file da aprire\n");
    exit(EXIT_FAILURE);
  }

  // apro il file e controllo buon esito
  fin=fopen(argv[1],"r");
  if(!fin){
    fprintf(stderr,"Errore: non riesco ad aprire il file %s\n",argv[1]);
    exit(EXIT_FAILURE);
  }

  // leggo carattere per carattere fino a fine file
  while(1){
    r=fgetc(fin); // fgetc di fatto restituisce un int
    if(r==EOF)
      break;
    tree=inserisci_in_albero(tree,(unsigned char)r);
  }
  fclose(fin);

  // stampo i valori ordinati
  printf("Valori ed occorrenze:\n");
  stampa_valori(tree);
  // stampo profondita'
  printf("La profondita' dell'albero e' %d\n",profondita_albero(tree));
  // stampo dimensione
  printf("La dimensione' dell'albero e' %d\n",dimensione_albero(tree));
  exit(EXIT_SUCCESS);
}

// funzione ricorsiva che effettua l'inserimento nell'albero o aggiorna il campo
// occorrenze a seconda che il carattere sia gia' presente o meno nell'albero
struct nodo* inserisci_in_albero(struct nodo *albero, const unsigned char dato){

  // controllo esistenza albero
  if(!albero){
    struct nodo *new;
    new=malloc(sizeof(struct nodo));
    if(!new){
      fprintf(stderr,"Errore: non riesco ad allocare memoria\n");
      exit(EXIT_FAILURE);
    }
    new->occorrenze=1;
    new->maggiori=new->minori=NULL;
    new->dato=dato;
    return new;
  }

  // controllo corrispondenza dato
  if(albero->dato==dato){
    albero->occorrenze++;
    return albero;
  }

  // altrimenti continuo ricerca
  if(albero->dato>dato){
    albero->minori=inserisci_in_albero(albero->minori,dato);
  }else{
    albero->maggiori=inserisci_in_albero(albero->maggiori,dato);
  }
  return albero;
}

// questa funzione ricorsiva attraversa in maniera inorder l'albero stampando i dati
void stampa_valori(struct nodo *a){
  if(!a)return;
  stampa_valori(a->minori);
  printf("%d: %d\n",a->dato,a->occorrenze);
  stampa_valori(a->maggiori);
}

// funzione ricorsiva che restituisce la profondita' dell'albero
int profondita_albero(struct nodo *a){
  int min,mag;

  if(!a)return 0;

  min=profondita_albero(a->maggiori);
  mag=profondita_albero(a->minori);
  return 1+(min>mag?min:mag);
}

// funzione ricorsiva che restituisce la dimensione dell'albero
int dimensione_albero(struct nodo *a){

  if(!a)return 0;

  return 1+dimensione_albero(a->maggiori)+dimensione_albero(a->minori);
}