Fondamenti di Informatica I
Corso di Laurea in Ingegneria Informatica
Proff. Demetrescu, Iocchi, Nardi, Pirri
ORDINAMENTO 2000
Uso di strutture collegate lineari per la visita di un albero binario: visita in profondita'
Consideriamo gli algoritmi di visita in profondità: visita in preordine, visita in postordine e visita simmetrica che abbiamo realizzato ricorsivamente. Questi algoritmi possono essere realizzati iterativamente con l'ausilio di una pila, in particolare discuteremo ora il caso della visita in preordine.
La pila serve come struttura di appoggio per eseguire le operazioni localizzate di visita della radice e visita dei sottoalberi parziali. L'elemento affiorante rappresenta il puntatore al prossimo nodo dell' albero da analizzare.
Inizialmente inseriamo la radice dell'albero nella pila. Iniziamo un ciclo che termina quando la pila è vuota e che è costituito dai seguenti passi:
Si estrae l'elemento affiorante della pila;
Si visita il nodo corrispondente all'elemento affiorante;
Si inseriscono nella pila il puntatore al figlio destro del nodo visitato (se esiste) e poi il puntatore al figlio sinistro del nodo visitato (se esiste).
Figura 1.
Analizziamo i passi dell'algoritmo di visita in preordine realizzato con l'ausilio di una pila, per l'albero raffigurato in Figura 1.
Si pone il riferimento alla radice, etichettata da G, nella pila. Si estrae l'elemento affiorante e si stampa il valore dell'etichetta, si veda la prima pila nella Figura 1.
Si inseriscono nella pila il figlio destro (prima) e il figlio sinistro (dopo) di G nella pila. Si estrae l'elemento affiorante, ovvero il riferimento al nodo dell'albero con valore E, e si stampa. Si veda la seconda pila nella Figura 1.
Si inseriscono nella pila il figlio destro (prima) e il figlio sinistro (dopo) di E nella pila. Si estrae l'elemento affiorante, ovvero il riferimento al nodo dell'albero con valore E, e si stampa. Si veda la terza pila nella Figura 1.
Si procede in tal modo fino ad arrivare alla pila formata solo dall'elemento avente come etichetta D. Una volta estratto tale elemento la pila resta vuota e il ciclo termina.
Implementazione in Java degli algoritmi di visita in profondità, con uso della pila
Mostriamo nuovi metodi per la classe AlberoBin che forniscono le operazioni di visita in profondità realizzati con l'ausilio di una pila. Nei seguenti metodi, si e' fatto uso dell'implementazione funzionale della pila.
import java.io.*;
class AlberoBin {
...
// Visita in profondita' con l'ausilio di una pila,
// con implementazione funzionale.
// Preodine Sinistro
public void preordineConPila(PrintStream p) throws IOException, AlberoBinException,PilaException {
AlberoBin alb;
Pila pp = new Pila();
if (!this.alberoVuoto())
{ pp = pp.push(this); // inseriamo la radice
while (!pp.empty())
{
alb = (AlberoBin) pp.top(); //estraiamo l'elemento affiorante
pp = pp.pop(); //restituiamo il resto della pila
if (!alb.alberoVuoto())
{
p.println(alb.radice());
pp = pp.push(alb.destro());//inseriamo S-albero destro
pp = pp.push(alb.sinistro());//inseriamo S-albero sinistro
}
}
}
}//end ricerca in Profondita' Preordine Sinistro
Programma di prova delle operazioni di visita in profondità
Il seguente semplice programma di prova estende il programma di prova visto precedentemente con invocazioni alle operazioni di visita in profondità realizzate con l'uso di una pila.
class ProvaAlberoBin {
public static void main(String []arg) throws Exception {
AlberoBin vuoto = new AlberoBin();
AlberoBin t1 = new AlberoBin(vuoto,"A",vuoto);
AlberoBin t2 = new AlberoBin(vuoto,"B",vuoto);
AlberoBin t3 = new AlberoBin(vuoto,"C",vuoto);
AlberoBin t4 = new AlberoBin(vuoto,"D",vuoto);
AlberoBin t5 = new AlberoBin(t1,"E",t2);
AlberoBin t6 = new AlberoBin(t3,"F",t4);
AlberoBin t7 = new AlberoBin(t5,"G",t6);
............................................
System.out.println("Visita in Profondita (Preordine Sinistro):");
t7.preordineConPila(System.out);
}
}
Per un facile utilizzo dei metodi implementati è opportuno inserire le classi Nodo e Pila e le classi per le rispettive eccezioni in un'unica cartella.
Si veda Codice
Uso di strutture collegate lineari per la visita di un albero binario: visita in ampiezza
La visita in ampiezza di un albero, consiste nella visita di ciascun livello dell'albero nella direzione che si vuole, da destra verso sinistra o viceversa.
Figura 2.
I passi di visita sono analoghi alla visita in preordine eseguiti con l'ausilio di una pila
Inizialmente si inserisce nella coda il riferimento alla radice dell'albero. Si inizia un ciclo, che termina quando la coda è vuota, ed è costituito dai seguenti passi:
Implementazione della visita in ampiezza
Si e' fatto uso dell'implementazione non-funzionale della coda.
import java.io.*;
class AlberoBin {
...
//Visita in Ampiezza con l'ausilio di una coda, in questo
//caso utilizziamo l'implementazione non funzionale della
//coda
public void visitaInAmpiezza(PrintStream p) throws IOException, AlberoBinException,CodaException {
AlberoBin alb;
Coda cc = new Coda();
if (!this.alberoVuoto())
{ cc.inCoda(this);
while (!cc.empty())
{
alb = (AlberoBin) cc.first();
cc.outCoda();
if (!alb.alberoVuoto())
{
p.println(alb.radice());
cc.inCoda(alb.sinistro());
cc.inCoda(alb.destro());
}
}
}
}
}
Programma di prova delle operazioni di visita in ampiezza
Il seguente semplice programma di prova estende il programma di prova visto precedentemente con invocazioni alle operazioni di visita in ampiezza realizzate con l'uso di una coda.
class ProvaAlberoBin {
public static void main(String []arg) throws Exception {
AlberoBin vuoto = new AlberoBin();
AlberoBin t1 = new AlberoBin(vuoto,"A",vuoto);
AlberoBin t2 = new AlberoBin(vuoto,"B",vuoto);
AlberoBin t3 = new AlberoBin(vuoto,"C",vuoto);
AlberoBin t4 = new AlberoBin(vuoto,"D",vuoto);
AlberoBin t5 = new AlberoBin(t1,"E",t2);
AlberoBin t6 = new AlberoBin(t3,"F",t4);
AlberoBin t7 = new AlberoBin(t5,"G",t6);
.......................................
System.out.println("Visita in Ampiezza:");
t7.visitaInAmpiezza(System.out);
}
}