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).
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); }
void StampaAlbero(Albero a) { if(a==NULL) { printf("()"); return; } printf("( %d ",a->radice); StampaAlbero(a->sinistro); StampaAlbero(a->destro); printf(" ) "); }
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); }
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.