/* 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;
}