/* albero.c * Scrivere un programma che definisca un albero binario il cui nodo contiene, * come dati, due interi. Il primo intero sarà la chiave, mentre il secondo * indicherà l'ordine di creazione. Usando una variabile globale come * puntatore alla radice dell'albero, * scrivere: * Una funzione ricorsiva che inserisca un nodo nell'albero * Una funzione che crei (allochi) un nodo e lo inserisca * nell'albero, usando al bisogno la funzione ricorsiva di cui sopra. * Una funzione ricorsiva che 'traversi' l'albero, stampando il contenuto di ogni nodo, nell'ordine * Una funzione ricorsiva che liberi la memoria occupata dall'albero * Un programma principale che, utilizzando le funzioni scritte: * 1.Crei un'albero di venti numeri casuali * 2.Li stampi in maniera ordinata, secondo il valore casuale * 3.Liberi la memoria occupata dall'alabero */ #include <stdio.h> /* Per le funzioni 'srand' e 'random' */ #include <stdlib.h> /* Per la funzione 'time' */ #include <time.h> /* Struttura del nodo, come descritto nel testo */ struct nodo { struct nodo *sinistro; int chiave; int valore; struct nodo *destro; } *albero = NULL; /* puntatore all'albero (al nodo radice) */ /* Aggiunge all'albero o sottoalbero puntato da 'a' * il nodo puntato da 'n' */ void aggiungiNodo (struct nodo *a, struct nodo *n) { if (n -> chiave < a -> chiave) { /* Se il nodo va' aggiunto a sinistra */ if (a -> sinistro != NULL) /* Se esiste un sottoalbero di sinistra */ aggiungiNodo (a -> sinistro, n); /* Aggiungo a quel sottalbero */ else /* Se il sottalbero non esiste */ a -> sinistro = n; /* diventa radice del sottoalbero */ } else { /* Se il nodo va' aggiunto a destra */ if (a -> destro != NULL) /* Se esiste un sottoalbero di destra */ aggiungiNodo (a -> destro, n); /* Aggiungo a quel sottalbero */ else /* Se il sottalbero non esiste */ a -> destro = n; /* diventa radice del sottoalbero */ } } /* Crea un nuovo nodo, lo inizializza e lo aggiunge all'albero * puntato dalla variabile globale 'albero' */ void nuovoNodo (int valore, int chiave) { struct nodo *n; /* puntatore al nodo che stiamo per creare */ /* Creiamo il nodo, con la funzione 'malloc' */ n = (struct nodo*) malloc (sizeof (struct nodo)); /* Inizializziamo il nodo, con i valori passati per parametro */ n -> sinistro = NULL; /* Il sottoalbero sinistro e' vuoto */ n -> chiave = chiave; n -> valore = valore; n -> destro = NULL; /* Il sottoalbero destro e' vuoto */ if (albero == NULL) /* Se l'albero non esiste ancora */ albero = n; /* Il nostro nodo ne costituisc la radice */ else /* Se l'albero esiste gia' */ aggiungiNodo (albero, n); /* Aggiungiamo all'albero esistenta */ } /* Funzione che stampa in ordine un sottoalbero, puntato da 'a' */ void traversa (struct nodo *a) { if (a -> sinistro) /* Se esiste il sottoalbero sinistro */ traversa (a -> sinistro); /* Lo stampa */ /* Stampa i valori del nodo (chiave in un campo di 12, '->' ed il valore in un campo di 2 */ printf ("%14d -> %2d\n", a -> chiave, a -> valore); if (a -> destro) /* Se esiste il sottoalbero destro */ traversa (a -> destro); /* Lo stampa */ } /* Funzione che libera la memoria occupata da un sottoalbero */ void libera (struct nodo *a) { if (a -> sinistro) /* Se esiste un sottoalbero sinistro */ libera (a -> sinistro); /* Libera prima la memoria di quel sottoalbero */ if (a -> destro) /* Se esiste un sottoalbero destro */ libera (a -> destro); /* Libera prima la memoria di quel sottoalbero */ free (a); /* Per finire libera la memoria della radice */ } /* Funzione principale */ int main () { int i; srandom (time (NULL)); /* Inizializza il generatore di numeri casuali * * utilizzando il tempo corrente (molto variabile) */ for (i = 0; i < 20; i++) /* Ciclo da 0 a 19 */ nuovoNodo (i, random ()); /* aggiunge nodo con valore l'indice e chiave casuale */ traversa (albero); /* Stampa l'albero (sottoalbero = intero albero) */ libera (albero); /* Libera la memoria dell'albero (sottoalbero = intero albero) */ return 0; }