/* albero.cc * 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 * Modificare il programma dell'albero binario in modo da: * 1.creare una classe 'nodo' (in realtà una struct nodo) * 2.Scrivere un costruttore con parametri per nodo, che inizializzi sia la chiave che il valore * 3.Scrivere un metodo 'inserisci', con un nodo come parametro che inserisca il nodo dato * come parametro nel sottoalbero del quale il nodo corrente (this) è radice * 4.Trasformare in metodo anche la funzione per traversare l'albero * 5.Trasformare la funzione che cancella l'albero in un distruttore */ #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; nodo (int Valore, int Chiave) { chiave = Chiave; valore = Valore; sinistro = destro = (nodo*) 0; }; void inserisci (nodo *n); void traversa (); ~nodo (); } *albero = NULL; // puntatore all'albero (al nodo radice) /* Aggiunge all'albero o sottoalbero puntato da 'a' * il nodo puntato da 'n' */ void nodo::inserisci (nodo *n) { if (n -> chiave < chiave) { // Se il nodo va' aggiunto a sinistra if (sinistro != NULL) // Se esiste un sottoalbero di sinistra sinistro -> inserisci (n); // Aggiungo a quel sottalbero else // Se il sottalbero non esiste sinistro = n; // diventa radice del sottoalbero } else { // Se il nodo va' aggiunto a destra if (destro != NULL) // Se esiste un sottoalbero di destra destro -> inserisci (n); // Aggiungo a quel sottalbero else // Se il sottalbero non esiste destro = n; // diventa radice del sottoalbero } } /* Metodo che stampa in ordine un sottoalbero, puntato da 'a' */ void nodo::traversa () { if (sinistro) // Se esiste il sottoalbero sinistro sinistro -> traversa (); // 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", chiave, valore); if (destro) // Se esiste il sottoalbero destro destro -> traversa (); // Lo stampa } /* Funzione che libera la memoria occupata da un sottoalbero */ nodo::~nodo () { if (sinistro) // Se esiste un sottoalbero sinistro delete sinistro; // Libera prima la memoria di quel sottoalbero if (destro) // Se esiste un sottoalbero destro delete destro; // Libera prima la memoria di quel sottoalbero } /* Crea un nuovo nodo, lo inizializza e lo aggiunge all'albero * puntato dalla variabile globale 'albero' */ void nuovoNodo (int valore, int chiave) { // Creiamo il nodo, con la funzione 'malloc' nodo *n = new nodo (valore, chiave); if (albero == NULL) // Se l'albero non esiste ancora albero = n; // Il nostro nodo ne costituisc la radice else // Se l'albero esiste gia' albero -> inserisci (n); // Aggiungiamo all'albero esistente } /* Funzione principale */ int main () { srandom (time (NULL)); /* Inizializza il generatore di numeri casuali * * utilizzando il tempo corrente (molto variabile) */ for (int i = 0; i < 20; i++) // Ciclo da 0 a 19 nuovoNodo (i, random ()); // aggiunge nodo con valore l'indice e chiave casuale albero -> traversa (); // Stampa l'albero (sottoalbero = intero albero) delete albero; // Libera la memoria dell'albero (sottoalbero = intero albero) return 0; }