[Fratelli]
Un "fratello" in un albero binario è un nodo n
il
cui padre ha un figlio diverso da n. Si scriva la classe
Fratelli
che contiene il metodo
|
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 |
[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 |
[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.
[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
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)+ "}":""); } |
[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 ) {
|
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.
[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.