/* File: albbin.c */
/* Time-stamp: "2001-05-24 16:23:07 calvanes" */
/* Scopo: manipolazione e visite di alberi binari */

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

typedef int TipoInfoAlbero;

struct nodoAlbero {
  TipoInfoAlbero info;
  struct nodoAlbero *destro, *sinistro;
};
typedef struct nodoAlbero NodoAlbero;
typedef NodoAlbero *TipoAlbero;


typedef TipoAlbero TipoElemCoda;

#include "code.c"


/* Visite di alberi */

void Analizza(int n)
{
  printf("%d ", n);
}  /* Analizza */


void VisitaPreordine(TipoAlbero a)
{
  if (a != NULL) {
    Analizza(a->info);                   /* analizza la radice               */
    VisitaPreordine(a->sinistro);        /* analizza il sottoalbero sinistro */
    VisitaPreordine(a->destro);          /* analizza il sottoalbero destro   */
  }
}  /* VisitaPreordine */


void VisitaPostordine(TipoAlbero a)
{
  if (a != NULL) {
    VisitaPostordine(a->sinistro);       /* analizza il sottoalbero sinistro */
    VisitaPostordine(a->destro);         /* analizza il sottoalbero destro   */
    Analizza(a->info);                   /* analizza la radice               */
  }
}  /* VisitaPostordine */


void VisitaLivelli(TipoAlbero albero)
{
  TipoCoda coda;
  TipoAlbero a;

  InitCoda(&coda);                                /* crea la coda e ...      */
  InCoda(&coda, albero);                          /* ... inserisce la radice */

  while (!TestCodaVuota(coda)) {
    OutCoda(&coda, &a);                         /* estrai un nodo dalla coda */

    if (a != NULL) {
      Analizza(a->info);                      /* analizza il nodo estratto   */
      InCoda(&coda, a->sinistro);             /* metti in coda i sottoalberi */
      InCoda(&coda, a->destro);
    }
  }
}  /* VisitaLivelli */


TipoAlbero RicercaAlbero(TipoAlbero A, TipoInfoAlbero elem)
  /* Effettua la ricerca di elem nell'albero binario di ricerca A.
     Il valore di ritorno e` il sottoalbero di A la cui radice e` pari ad elem,
     se elem e` presente in A, NULL altrimenti.
  */
{
  TipoAlbero posiz;

  if (A == NULL)
    posiz = NULL;
  else if (elem == A->info)                   /* l'elemento e` stato trovato */
    posiz = A;
  else if (elem < A->info)                 /* cerca nel sottoalbero sinistro */
    posiz = RicercaAlbero(A->sinistro, elem);
  else                                       /* cerca nel sottoalbero destro */
    posiz = RicercaAlbero(A->destro, elem);

  return posiz;
} /* RicercaAlbero */


void StampaAlbero(TipoAlbero a)
{
  if (a == NULL) {
    printf("()");
  } else {
    printf("( %d ", a->info);
    StampaAlbero(a->sinistro);
    StampaAlbero(a->destro);
    printf(" )");
  }
}  /* StampaAlbero */


/* Lettura di un albero da file */

char LeggiParentesi(FILE *f)
  /* legge la prossima parentesi nel file */
{
  char c;

  c = fgetc(f);                                        /* legge un carattere */
  while (c != '(' && c != ')')  /* se non e` una parentesi ne legge un altro */
    c = fgetc(f);

  return c;
}  /* LeggiParentesi */


TipoAlbero LeggiSottoAlbero(FILE *file_albero)
{
  char c;
  TipoInfoAlbero i;
  TipoAlbero r;

  c = LeggiParentesi(file_albero);              /* legge la parentesi aperta */
  c = fgetc(file_albero);                            /* carattere successivo */

  if (c == ')')
    return NULL;                     /* se legge () allora l'albero e' vuoto */
  else {
    fscanf(file_albero, "%d", &i);   /* altrimenti legge la radice */
                /* Nota: se le informazioni sono di tipo complesso, per esempio
                   strutture, la istruzione fscanf non era in grado di leggere
                   l'informazione associata, e quindi e` necessaria una
                   funzione di lettura dell'informazione */
    r = malloc(sizeof(NodoAlbero));
    r->info = i;

    /* legge i sottoalberi */
    r->sinistro = LeggiSottoAlbero(file_albero);
    r->destro = LeggiSottoAlbero(file_albero);

    c = LeggiParentesi(file_albero);            /* legge la parentesi chiusa */

    return r;
  }
}  /* LeggiSottoAlbero */


TipoAlbero LeggiAlbero(char *nome_file)
{
  TipoAlbero result;
  FILE *file_albero;

  file_albero = fopen(nome_file, "r");
  if (file_albero == NULL) {
    printf("Errore in apertura del file %s\n", nome_file);
    result = NULL;
  } else {
    result = LeggiSottoAlbero(file_albero);
    fclose(file_albero);
  }

  return result;
}  /* LeggiAlbero */


void DeallocaAlbero(TipoAlbero a)
{
  if (a != NULL) {
    DeallocaAlbero(a->sinistro);
    DeallocaAlbero(a->destro);
    free(a);
  }
}


int main (void)
{
  TipoAlbero alb;
  char nomefile[128];
  TipoInfoAlbero elem;

  printf("Immetti il nome del file contenente l'albero: ");
  scanf("%s", nomefile);

  alb = LeggiAlbero(nomefile);

  StampaAlbero(alb);

  printf("\nVisita in preordine:  ");
  VisitaPreordine(alb);

  printf("\nVisita in postordine: ");
  VisitaPostordine(alb);

  printf("\nVisita per livelli:   ");
  VisitaLivelli(alb);

  printf("\n");
  do {
    printf("Immetti un elemento da cercare nell'albero (-1 per terminare): ");
    scanf("%d", &elem);
    if (elem != -1)
      if (RicercaAlbero(alb, elem))
        printf("%d e` presente nell'albero\n", elem);
      else
        printf("%d NON e` presente nell'albero\n", elem);
  } while (elem != -1);

  DeallocaAlbero(alb);
  return 0;
}