// Programma che implementa un'albero binario
abstract class nodobase {
 nodobase sinistro = null;         // Sottoalbero di sinistra (del nodo)
 nodobase destro = null;           // Sottoalbero di destra (del nodo)
 static nodobase albero = null;    // Albero (della classe)

 nodobase () {                // Costruttore che inserisce direttamente nell'albero
   if (albero == null)        // Se non esiste la radice dell'albero
     albero = this;           // Allora il nuovo nodo diventera' la radice
   else
     albero.inserisci (this); // Altrimenti ordina alla radice di inserire
 }

 abstract boolean compare (nodobase nuovo); // Metodo astratto di confronto
 abstract void print ();                    // Metdodo astratto di stampa

 void inserisci (nodobase nuovo) { // Funzione ricorsiva di inserimento
   if (compare (nuovo)) {          // Confronta il nodo da inserire con 'me', che sono la radice del sottoalbero
     if (sinistro != null)         // Se esiste la radice del sottoalbero
      sinistro.inserisci (nuovo);  // Inserisco nel sottoalbero
     else
      sinistro = nuovo;            // Altrimenti il nuovo nodo e' la radice del sottoalebero
   } else {
     if (destro != null)           // Se esiste la radice del sottoalbero
      destro.inserisci (nuovo);    // Inserisco nel sottoalbero
     else
      destro = nuovo;              // Altrimenti il nuovo nodo e' la radice del sottoalebero
   }
 }

 void traversa () {         // Funzione ricorsiva che traversa l'albero
   if (sinistro != null)    // Se esiste il sottoalbero di sinistra (la sua radice) 
     sinistro.traversa ();  // Visito prima il sottoalbero
   print ();                // Stampa il contenuto del nodo    
   if (destro != null)      // Se esiste il sottoalbero si destra
     destro.traversa ();    // Adesso visito anche quello
 }
}

class nodo extends nodobase {
 double chiave;                // Chiave >8)=
 int valore;                   // Valore >8)=

 nodo (double ch, int val) {   // Costruttore con parametri
  chiave = ch;                 // Inizializza i dati del nodo con i parametri
  valore = val;
 }

 boolean compare (nodobase nuovo) {       // Implementazione del metodo astratto della superclasse
   return ((nodo) nuovo).chiave < chiave; // Confront ai valori - deve fare un type cast
 }

 void print () {                  // Implementazione del metodo astratto della superclasse
   System.out.print (chiave);     // Stampo i valori del nodo corrente
   System.out.print (" -> ");
   System.out.println (valore);
 }

 public static void main (String [] args) { // Programma principale
   int i;
   for (i = 0; i < 20; i++)                 // 20 ripetizioni
     new nodo (java.lang.Math.random(),i);  // Crea 20 'nodo', chiave casuale ecc.
   albero.traversa ();                      // Traversa l'albero, dalla radice
   albero = null;                           // Dereferenzia la radice, per elimenare l'albero
 } 
}