Esercitazione 4
Alberi n-ari
Corso di Fondamenti di Informatica II
BIAR2 (Ing. Informatica e Automatica) e BSIR2 (Ing. dei Sistemi)
A.A. 2010/2011
19 Novembre 2010
Sommario
Scopo della esercitazione è quello di realizzare una struttura dati
per gestire gli alberi n-ari ed implementare semplici algoritmi di visita.
1
Rappresentazione di un albero n-ario
Un albero n-ario è una struttura dati che permette di rappresentare un generico albero in cui ad ogni nodo è associato un valore e che ha 0 o più nodi
gli. Ogni nodo ha un riferimento al parent (genitore), un campo element
(info) che contiene un valore (del tipo appropriato) e una lista di riferimenti
ai nodi gli.
Figura
Gracamente, il generico nodo dell'albero è rappresentato in
??.
Ci ri siferisca per i dettagli al libro adottato nel Corso Fondamenti di
Informatica 2 (Algoritmi) - Fabrizio D'Amore [?].
Programma Java.
e
TreeNode<E>
Si vogliono implementare le due classi Java
di tipo generico che rappresentano rispettivamente un al-
bero n-ario ed un suo generico nodo.
mentare l' interfaccia
classe
MyTree<E>
Tree<E>
La classe
MyTree<E>
dovrà imple-
(fornita nel materiale di supporto) mentre la
TreeNode<E> dovra' implementare l'interfaccia Position<E> (anch'es-
sa disponibile nel materiale di supporto).
1
Figura 1: Generico nodo di un albero n-ario.
2
Creazione e popolamento di alberi n-ari
Dopo aver realizzato le classi per rappresentare l'albero occorre eettuare dei
test per vedere se i dati vengono inseriti in maniera corretta.
Programma Java.
Si vuole realizzare una classe
MyTest con un main per
il test della rappresentazione in cui creare un albero, inserire alcuni valori di
prova e poi stamparlo con il metodo stampa della classe
TreeUtil
nel materiale di supporto). Un possibile main di prova è il seguente:
public
static
v o i d main ( S t r i n g [ ]
MyTree<I n t e g e r > t
args )
= new MyTree<I n t e g e r >() ;
P o s i t i o n <I n t e g e r > r o o t
= t . setRoot (100) ;
P o s i t i o n <I n t e g e r > c
= root . addChildren (20) ;
final
P o s i t i o n <I n t e g e r > c h i l d = r o o t . a d d C h i l d r e n ( 2 3 0 ) ;
c h i l d . addChildren ( 1 ) ;
c h i l d . addChildren ( 2 ) ;
c h i l d . addChildren ( 3 ) ;
c . addChildren ( 4 ) ;
T r e e U t i l . stampa ( t ) ;
2
(fornita
3
Visita di alberi n-ari
Per visita di un albero n-ario si intende l'operazione di accedere a tutti i suoi
nodi eseguendo o meno operazioni su di essi, ad esempio stampandone il valore o inserendoli in un insieme. Ci sono diversi tipi di visita dipendentemente
dall'ordine con cui i nodi vengono visitati.
Programma Java.
Si vuole modicare la classe
MyTree<E>
aggiungendo
i seguenti metodi di istanza.
public
void
printPreorder ()
Stampa i nodi dell'albero in preordine.
public
L i s t <E> p o s t o r d e r ( )
Restituisce una lista degli elementi dell'albero in postordine.
4
Visita di alberi n-ari con calcolo di proprietà
La visita di un albero può essere l'operazione di base quando il task è calcolare
una particolare proprietà di un albero n-ario, e può essere opportuno (o
necessario) utilizzare un tipo di visita piuttosto che un altro.
Programma Java.
Si vuole modicare la classe
MyTree<E>
aggiungendo
i seguenti metodi di istanza.
public
int
size ()
Restituisce il numero di nodi dell' albero.
public
int
depth
()
Restituisce la profondità dell' albero.
public
int
maxBranchingFactor
()
Restituisce il massimo del numero di gli di un nodo (branching factor).
3
Programma Java (per casa).
Si vuole modicare la classe
MyTree<E>
aggiungendo i seguenti metodi di istanza.
public
int
c o n t a O c c o r r e n z e (E e l e m e n t )
Ritorna il numero di occorrenze di element all'interno dell'albero
Parametri.
• element:
public
elemento da cercare
L i s t <E> r e s t i t u i s c i L i v e l l o ( i n t
l)
Ritorna l'insieme di tutti gli elementi dei nodi che si trovano a livello l
Parametri.
• l:
livello
Suggerimento.
Per realizzare i metodi precedenti è consigliabile ricorrere
a metodi privati di supporto in modo da poter aggiungere eventuali parametri
aggiuntivi rispetto a quelli indicati nelle signature dei metodi. Ovviamente
dovrà essere tali metodi aggiuntivi dovranno essere privati e non accessibili
dall'esterno ed utilizzati solo all'interno della classe.
4