/* 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 assegnato in precedenza (soluzione precedente) in modo da:
* 1.creare una classe astratta 'albero' con un attributo statico per il puntoatore alla radice. Dovrà avere:
* Solo i puntatori 'destro' e sinistro', come attributi non staitic
* Un costruttore di default che inserisca il nuovo nodo creato nell'albero
* Un distruttore virtuale che distrugga l'intero albero
* Un metodo virtuale puro 'confronto' privato con un parametro di tipo void *,
* che confronta il nodo corrente con quello passato per parametro
* Un metodo virtuale puro 'stampa' privato che stampa il nodo corrente
* Un metodo pubblico 'traversa' che stampa, tramite il memtodo stampa l'intero albero
* Un metodo statico pubblico 'elimina' che esegua la 'delete' dell'intero albero
* 2.Una classe alberoIntero che derivi in modo privato da albero, la quale:
* Possegga due attributi interi chiave e valore
* Implementi i metodi virtuali pure di albero
* Renda visibili i metodi 'traversa' e 'elimina'
* Tutti gli attributi devono essere privati
* Modificare l'esercizio dell'albero binario, presentato in precedenza trasformato ad oggerri in una precedente lezione. creare:
* 1.una classe template 'albero' analoga alla precedente albero
* 2.Una classe 'nodo' che contenga due numeri, la chiave casuale e il numero d'ordine (come inprecedenza) private
* 3.Una classe alberoChiave derivata da albero, che contenga come dato un puntatore a 'nodo' ed esegua il confronto
* (funzione virtuale) con la chiave.
* 4.Una classe AlberoDato derivata da albero, che contenga come dato un puntatore a 'nodo' ed esegua il confronto
* (funzione virtuale) con il dato.
* 5.La funzione principale costruirà 10 nodi e due alberi, uno derivato da alberoChiave e l'altro da alberoDato, quindi
* stamperà entrambi dli alberi
*/
#include <stdio.h> // Per le funzioni 'srand' e 'random'
#include <stdlib.h> // Per la funzione 'time'
#include <time.h>
/**********************************************************************/
/* Classe TEMPLATE albero */
/**********************************************************************/
template <class T> class albero {
albero *sinistro; // Puntatore al sottoalbero sinistro
albero *destro; // Puntatore al sottoalbero destro
static albero *radice; // Puntatore alla radice (statico)
void inserisci (T *n); // Inserisci ricorsiva, usata internamente
void traversa (); // Traversa ricorsiva, usata internamente
virtual int compare (T *n) = 0; // Compare, virtuale pura
virtual void print () = 0; // Print, virtula pura
protected:
void add () { if (radice) radice -> inserisci ((T*)this); else radice = this; }
public:
albero () { sinistro = destro = (albero*) 0; }; // Non inserisce il nodo ora perche' questo costruttore viene
// richiamato prima che la classe derivata abbia inizializzato
// il puntatore che serve per il confronto
virtual ~albero ();
// Funzioni statiche, inerfaccia all'albero nel suo insieme
static void elimina () { if (radice) delete radice;};
static void Traversa () { if (radice) radice -> traversa (); };
};
/**********************************************************************/
/* Classe nodo */
/**********************************************************************/
class nodo {
friend class alberoChiave; // Queste due classi accederanno per la 'compare'
friend class alberoDato;
int chiave; // Dati del nodo
int valore;
void print (); // Stampa il dato
public:
nodo (int Valore, int Chiave); // Il costruttore costruira' anche i due indici
};
/**********************************************************************/
/* Classe alberoChiave */
/**********************************************************************/
class alberoChiave : private albero<alberoChiave> {
nodo *dato;
virtual int compare (alberoChiave *n); // Implementazione delle virtuali pure di 'albero'
virtual void print ();
public:
alberoChiave (nodo *N) { dato = N; add (); };
albero<alberoChiave>::elimina; // Rendo di nuovo visibile 'elimina'
albero<alberoChiave>::Traversa; // Rendo di nuovo visibile 'Traversa'
};
/**********************************************************************/
/* Classe alberoDato */
/**********************************************************************/
class alberoDato : private albero<alberoDato> {
nodo *dato;
virtual int compare (alberoDato *n); // Implementazione delle virtuali pure di 'albero'
virtual void print ();
public:
alberoDato (nodo *N) { dato = N; add (); };
~alberoDato () { delete dato; }; // La definisco solo qui, perche' se no cancellerei due volte il nodo
albero<alberoDato>::elimina; // Rendo di nuovo visibile 'elimina'
albero<alberoDato>::Traversa; // Rendo di nuovo visibile 'Traversa'
};
/**********************************************************************/
/* Classe TEMPLATE albero - Implementazione */
/**********************************************************************/
/* Aggiunge all'albero o sottoalbero puntato da 'a'
* il nodo puntato da 'n' */
template <class T> void albero<T>::inserisci (T *n)
{
if (compare (n)) // Chiama la 'compare' virtuale, per sapere da che parte mettere il nuovo nodo
{ // 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 = (albero<T>*)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 = (albero<T>*)n; // diventa radice del sottoalbero
}
}
/* Metodo che stampa in ordine un sottoalbero, puntato da 'a' */
template <class T> void albero<T>::traversa ()
{
if (sinistro) // Se esiste il sottoalbero sinistro
sinistro -> traversa (); // Lo stampa
print (); // Chiama la 'print' virtuale per stampare il nodo
if (destro) // Se esiste il sottoalbero destro
destro -> traversa (); // Lo stampa
}
/* Funzione che libera la memoria occupata da un sottoalbero */
template <class T> albero<T>::~albero<T> ()
{
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
}
/**********************************************************************/
/* Classe nodo - Implementazione */
/**********************************************************************/
nodo::nodo (int Valore, int Chiave)
{
chiave = Chiave; // Inizializza i valori
valore = Valore;
new alberoChiave (this); // Crea indice per chiave
new alberoDato (this); // Crea indice per valore
}
void nodo::print ()
{
// 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);
}
/**********************************************************************/
/* Classe alberoChiave - Implementazione */
/**********************************************************************/
// La calsse reale albero<alberoChiave> ha una statica che va' definita!!!
albero<alberoChiave> *albero<alberoChiave>::radice = 0;
int alberoChiave::compare (alberoChiave *n)
{
return (n -> dato -> chiave) < (dato -> chiave); // Ritorna il confronto fra le chiavi (il confronto)
}
void alberoChiave::print ()
{
// Richiama la funzione di stampa del nodo
dato -> print ();
}
/**********************************************************************/
/* Classe alberoDato - Implementazione */
/**********************************************************************/
// La calsse reale albero<alberoDato> ha una statica che va' definita!!!
albero<alberoDato> *albero<alberoDato>::radice = 0;
int alberoDato::compare (alberoDato *n)
{
return (n -> dato -> valore) < (dato -> valore); // Ritorna il confronto fra i dati
}
void alberoDato::print ()
{
// Richiama la funzione di stampa del nodo
dato -> print ();
}
/* Funzione principale */
int main ()
{
srandom (time (NULL)); /* Inizializza il generatore di numeri casuali
* utilizzando il tempo corrente (molto variabile) */
for (int i = 0; i < 10; i++) // Ciclo da 0 a 19
new nodo (i, random ()); // crea nodo con valore l'indice e chiave casuale
alberoChiave::Traversa (); // Stampa l'albero tramite il metodo statico
printf ("\n");
alberoDato::Traversa (); // Stampa l'albero tramite il metodo statico
alberoChiave::elimina (); // Libera la memoria dell'albero tramite il metodo statico,
alberoDato::elimina (); // Libera la memoria dell'albero tramite il metodo statico,
// visto che non ho accesso alla radice
return 0;
}