LSD
Martedi' 14 maggio 2002

Esercizi su Alberi Binari (di Ricerca)
Alcuni metodi generali su alberi binari : MetodiAlberiBinari.java

[Fratelli]
Un "fratello" in un albero binario è un nodo nil cui padre ha un figlio diverso da n. Si scriva la classe Fratelli che contiene il metodo

/* restituisce il numero di "fratelli" contenuti nell'albero la cui radice e' il nodo n */
public static int fratelli ( BinNode n){
// da completare }

Si consiglia di scrivere con precisione una definizione ricorsiva della funzione fratelli (ad esempio in un commento) prima di scrivere il codice. Indicare esplicitamente che tipo di visita dell'albero si usa.
Per testare il metodo, si compili e si esegua la classe TestFratelli.java. Se il metodo è corretto, l'output dovrebbe essere il seguente:

I fratelli del primo albero sono 4
I fratelli del secondo albero sono 14
I fratelli dell'albero vuoto sono 0

Soluzione: Fratelli.java

[Alberi Felici]

Un nodo di un albero binario è un figlio sinistro se è il figlio sinistro di suo padre, e simmetricamente per figlio destro. Un nodo è contento se il sottoalbero di cui è radice contiene più figli sinistri che figli destri. Si scriva la classe NumContentiTreeSet che estende la classe TreeSet e fornisce il seguente metodo:

    public int numContenti () ;
    // da completare
    }

Il metodo numContenti restituisce il numero di nodi contenti dell'albero su cui viene invocato. Si usino opportuni metodi ausiliari per la soluzione.
Per testare la classe NumContentiTreeSet, si compili ed esegua la classe TestNumContentiTreeSet. L'output deve essere il seguente:

Provo il metodo NumContentiTreeSet.numContenti()...
Albero vuoto: [valore atteso] 0 [valore ottenuto] 0
Primo albero: [valore atteso] 3 [valore ottenuto] 3
Secondo albero: [valore atteso] 5 [valore ottenuto] 5

Soluzione: NumContentiTreeSet.java

[Verifica che un albero binario sia albero binario di ricerca]
Si scriva la classe CheckABR che contiene un metodo
public TreeSet isABR(BinNode n);
che controlla se l'albero binario di radice n è un albero binario di ricerca. In caso positivo si restituisce l'albero stesso come oggetto della classe TreeSet. Altrimenti si restituisce null. Scrivere una classe che testi il nuovo metodo.
Suggerimento: Se l'albero è un albero binario di ricerca, per costruire il corrispondente oggetto della classe TreeSet si può creare un albero vuoto, e poi inserire tutti gli elementi dell'albero di radice n con una visita anticipata.

Soluzione: CheckABR.java

[Transpose]

Si scriva la classe Transpose che contene il metodo

    public static BinNode transpose (BinNode r) ;
    // da completare
    }

Il metodo transpose restituisce un nuovo albero binario che è ottenuto dall'albero avente come radice r scambiando in ogni nodo il figlio sinistro ed il figlio destro. Il metodo non deve modificare l'albero passato per argomento. Ad esempio, se l'albero su cui è invocato transpose è:

x1
/ \
x2    x3
/ \    \
x4   x5    x6

allora l'albero restituito sarà:

x1
/ \
x3    x2
/     / \
x6     x5 x4

Scrivere un metodo main che costruisce un albero binario, lo stampa, ci applica il metodo transpose e stampa sia l'albero risultante che quello originale (per verificare che non sia stato modificato).
Per stampare l'albero, si faccia uso del seguente metodo:

public static String print (BinNode r){
    if (r == null) {
          return "";
    }
    else
          return ((r.left!=null)? "["+print(r.left)+"] ":"") +
              r.key + ((r.right != null)? " {" +print(r.right)+ "}":"");
}

Soluzione: Transpose.java

[Alberi di Fibonacci]
Un albero binario T è chiamato un albero di Fibonacci se è un albero vuoto, oppure se non è vuoto e per ogni nodo n di T vale la seguente proprietà: n è una foglia, oppure le profondità dei sottoalberi destro e sinistro di n differiscono ESATTAMENTE di 1.
Sia dato il seguente frammento di programma

import lab2.*;
public class Fibonacci {
    public static boolean verificaFibonacci ( BinNode r ) {
    // da completare
    }
}

Si completi la classe precedente, in maniera che il metodo verificaFibonacci restituisca true se e solo se l'albero di radice r è un albero di Fibonacci.
Per testare la classe, si scriva un metodo main che costruisce alcuni alberi, invoca il metodo verificaFibonacci su di essi e stampa il risultato.

Soluzione: Fibonacci.java
[VisitAndPrint]
Si scriva la classe VisitAndPrint che contiente il metodo

    public static void print (BinNode r) ;
    // da completare
    }

Il metodo print deve stampare tutti gli oggetti contenuti nell'albero binario avente come radice r visitando l'albero in ordine anticipato. Attenzione: il metodo print non deve usare la ricorsione, né direttamente né tramite metodi ausiliari. [Suggerimento: si usi una pila]
Scrivere una classe principale che testi il nuovo metodo.