Alberi binari

La parte di programma sugli alberi binari è trattata in modo esauriente sul libro. La definizione di tipo che si usa è la seguente:

/* definizione di albero */
struct NodoAlbero {
  int radice;
  struct NodoAlbero *sinistro, *destro;
};
typedef struct NodoAlbero *Albero;

Qui sotto si riportanto le funzioni di lettura di albero binario in rappresentazione parentetica (etichettato con interi) da file, e un programma di scrittura di albero du file. Si include anche un programma di generazione di alberi casuali (sempre etichettati con interi).

Lettura di un albero da file

Questa operazione richiede la definizione di tre funzioni: la prima ``salta'' gli spazi su un file; la seconda è la vera funzione ricorsiva di lettura; l'ultima funzione apre il file e chiama la funzione ricorsiva.

int LeggiNoSpazi(FILE *fd) {
  int res;
  char c;

  do {
    res=fscanf(fd, "%c", &c);
    if(res!=1) {
      return 0;
    }

  } while ( isspace(c) );

  ungetc(c, fd);
  return 1;
}

Albero LeggiAlberoFD(FILE *fd) {
  Albero a;
  int res, x;
  char c;

			/* legge la parentesi ( */
  LeggiNoSpazi(fd);
  res=fscanf(fd, "%c", &c);
  if(res!=1 || c!='(') {
    ungetc(c, fd);
    return NULL;
  }

			/* legge l'intero oppure ) */
  LeggiNoSpazi(fd);
  res=fscanf(fd, "%c", &c);
  if(res!=1 || c==')')
    return NULL;

  ungetc(c, fd);
  fscanf(fd, "%d", &x);

			/* crea il nodo */
  a=malloc(sizeof(struct NodoAlbero));
  a->radice=x;
  a->sinistro=LeggiAlberoFD(fd);
  a->destro=LeggiAlberoFD(fd);


			/* legge ) */
  LeggiNoSpazi(fd);
  fscanf(fd, "%c", &c);

  return a;
}

Albero LeggiAlberoFile(char *nomefile) {
  FILE *fd;

		/* apre il file */
  fd=fopen(nomefile, "r");
  if( fd==NULL ) {
    perror("Errore in apertura del file");
    exit(1);
  }

		/* legge l'albero */
  return LeggiAlberoFD(fd);
}

Stampa di albero su schermo

void StampaAlbero(Albero a) {
  if(a==NULL) {
    printf("()");
    return;
  }

  printf("( %d ",a->radice);
  StampaAlbero(a->sinistro);
  StampaAlbero(a->destro);
  printf(" ) ");
}

Salva un albero su file

Occorre una funzione ricorsiva che prende come parametro un descrittore di file. Serve poi un'altra funzione (non ricorsiva) che apre il file e chiama quella ricorsiva.

void StampaAlberoFD(FILE *fd, Albero a) {
  if(a==NULL) {
    fprintf(fd, "()");
    return;
  }

  fprintf(fd, "( %d ",a->radice);
  StampaAlberoFD(fd, a->sinistro);
  StampaAlberoFD(fd, a->destro);
  fprintf(fd, " ) ");
}

void StampaAlberoFile(char *nomefile, Albero a) {
  FILE *fd;

		/* apre il file */
  fd=fopen(nomefile, "w");
  if(fd==NULL) {
    perror("Errore in apertura del file");
    exit(1);
  }

		/* ci scrive l'albero */
  StampaAlberoFD(fd, a);
}

Generazione di albero casuale

Il programma albrand.c genera un albero casuale con al massimo cinque livelli (etichettato con interi), lo stampa su schermo e lo salva su file.