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