Realizzazione di alberi binari
Per realizzare gli alberi binari in Java utilizziamo la classe BinNode<E>, i cui oggetti rappresentano i nodi di un albero. Ogni nodo contiene:
  • un riferimento al BinNode del figlio sinistro,
  • un riferimento al BinNode del figlio destro,
  • un riferimento ad un oggetto di tipo E con l'informazione contenuta nel nodo.
La classe BinNode<E> contiene quindi le seguenti variabili d'istanza:
  
/** 
 * Classe BinNode<E>:
 */
public class BinNode<E> {    
    public E  key;              // Campo chiave
    public BinNode<E> left;     // Riferimento al figlio sinistro
    public BinNode<E> right;    // Riferimento al figlio destro
    

Graficamente un oggetto di BinNode viene rappresentato come segue:

 
left key right

La figura sotto mostra la rappresentazione dell'albero binario del lucido precedente, dove i nodi sono visti come oggetti di BinNode. Le frecce rappresentano riferimenti, null è rappresentato da un cerchietto, l'oggetto nel campo key è impropriamente riportato direttamente dentro il nodo.
 


BinNode<E>: costruttori
La classe BinNode contiene due costruttori che permettono la creazione di un BinNode specificando come inizializzare uno o più campi.
  

   /**
     * Costruttore di un BinNode in cui l'oggetto k (diverso da null) e' il campo chiave,
     * i parametri l e r sono riferimenti al figlio sinistro e destro, rispettivamente
     */
    public BinNode(E k, BinNode<E> l, BinNode<E> r) {
        this.key = k;
        this.left = l;
        this.right = r;
    }

   // Costruttore di una foglia
    public BinNode(E k) {
        this (k, null, null);
    }

Come costruire un albero
I costruttori di BinNode<E> permettono di costruire un albero binario "dal basso", a partire dalla foglie.

Ad esempio,  dopo i comandi
  

   BinNode<Integer> A,B,C,D;
   A = new BinNode<Integer>(10);
   B = new BinNode<Integer>(20);
   C = new BinNode<Integer>(30, A, B);
   D = new BinNode<Integer>(40, null, C);

la variabile D contiene il riferimento all'albero:
 

 

Visita di un albero binario
Visitare un albero significa esaminare sequenzialmente tutti i suoi nodi. Ci sono tre tipi principali di visite:
  • Nella visita in ordine simmetrico si visita il sottoalbero sinistro, quindi si esamina la radice e infine si visita il sottoalbero destro.
  • Nella visita in ordine anticipato si esamina prima la radice e quindi si visitano il sottoalbero sinistro e quello destro.
  • Nella visita in ordine posticipato si visitano prima i due sottoalberi e dopo si esamina la radice.
Altri tre tipi di visite si ottengono dai precedenti scambiando "sinistro" con "destro".

Il seguente metodo statico realizza la visita in ordine anticipato, stampando tutti i nodi dell'albero passato per argomento. Si noti che la struttura dell'algoritmo riflette la definizione ricorsiva degli alberi binari.
  
/*
 * Stampa tutti i nodi di un albero binario, visitandolo 
 * in ordine anticipato
 */
    public static<E> void print(BinNode<E> r){

//caso base (albero vuoto)
        if (r==null) return;

//caso ricorsivo (albero non vuoto)
        System.out.println(r.key); // esamina radice
        print(r.left);             // visita sottoalbero sinistro
        print(r.right);            // visita sottoalbero destro
    }

Le altre due visite si ottengono modificando l'ordine delle tre istruzioni del caso ricorsivo.

Ricerca in un albero binario
Il metodo seguente stabilisce se un certo oggetto appartiene o meno ad un dato albero binario, usando una visita in ordine anticipato. Si noti che:
  • il caso base è banale (come sempre): se l'albero è vuoto, si restituisce false;

  • la visita viene interrotta non appena si trova l'oggetto cercato.
    public static<E> boolean cerca(E x, BinNode<E> r){

//caso base (albero vuoto)
        if (r == null)        return false;

//caso ricorsivo (albero non vuoto)
        if (x.equals(r.key))  return true;
        if (cerca(x, r.left)) return true;
        return (cerca(x, r.right));
    }
 

Calcolo del numero di foglie
Come ultimo esempio di algoritmo su alberi binari, vediamo un metodo che conta le foglie dell'albero passato per parametro. Lo schema è il solito:
  • il caso base è banale: se l'albero è vuoto, allora non contiene alcuna foglia;
  • nel caso ricorsivo distinguiamo due sottocasi:
    • se la radice è una foglia, allora questa è l'unica dell'albero;
    • altrimenti il numero di foglie è la somma di quelle contenute nei due sottoalberi.
Si noti che le due chiamate ricorsive compaiono all'interno della stessa espressione.
  
    public static<E> int contaFoglie (BinNode<E> r) {

// caso base (albero vuoto)
        if (r == null) return 0;

// caso ricorsivo (albero non vuoto)
        if ((r.left == null) && (r.right == null)) return 1;            
        return contaFoglie(r.left) + contaFoglie(r.right);
    }
 

Esercizi
1) Realizzare il metodo 
  public static<E> int contaInterni(BinNode<E> r)

che restituisce il numero di nodi interni dell'albero la cui radice è r.

Un nodo interno è un nodo che ha almeno un figlio.

SOLUZIONE
2) Realizzare il metodo 
  public static<E> int altezza(BinNode<E> r)

che restituisce l'altezza dell'albero binario r .

L' altezza è la massima distanza radice-foglia, contando sia il nodo di partenza che il nodo di arrivo, (0 se l'albero è vuoto, 1 se contiene la sola radice).

SOLUZIONE
3) Realizzare il metodo 
  public static<E> int nodi(BinNode<E> r, int l)

che restituisce il numero di nodi presenti al livello l nell'albero r. (Si assuma che la radice sia al livello 0).

SOLUZIONE