Algoritmi di visita in ampiezza (BFS) di un albero binario

lezione 26
Algoritmi di visita in ampiezza (BFS)
di un albero binario
Definiamo le strutture dati concrete da utilizzare nei nostri algoritmi di visita. Gli alberi binari che stiamo considerando supporremo che abbiano una rappresentazione
in memoria a liste multiple così come descritto nella Lezione 23.
Una possibile definizione della classe AlberoBinario può essere la seguente:
~-A\
AlberoBinario
INIZIO
PRIVATO Info: INTERO
PRIVATO SX: AlberoBinario
PRIVATO DX: AlberoBinario
// Campo chiave di tipo intero
// Riferimento al figlio sinistro
// Riferimento al figlio destro
// Altri metodi di questa classe
// BFSO; PreOrdineO; PostOrdineO: InOrdineO
FINE
// Classe AlberoBinario
I riferimenti ai figli SX e DX sono a loro volta oggetti di classe AlberoBinario.
Consideriamo la visita top-down da sinistra verso
destra di u n albero binario. La realizzazione di questo
algoritmo è molto semplice se si utilizza u n a c o d a .
D o p o aver visitato u n nodo, i suoi figli, se ce ne sono,
vengono inseriti in u n a coda e si visita il n o d o che si trova in testa a quest'ultima.
Dato che i figli di u n n o d o al livello k si trovano al livello k + 1, e dato che sono stati
inseriti nella coda, essi verranno visitati solo dopo che sono stati visitati tutti i nodi
di livello k. In questo m o d o si rispetta il vincolo che tutti i nodi di livello k debbano
essere visitati prima di u n qualsiasi n o d o di livello k + 1.
Algoritmo BFS
per alberi binari
// Root è la radice dell'albero
ALGORITMO BFSCRoot: AlberoBinario)
// Variabile locale di classe AlberoBinario
Temp: AlberoBinario
O: Coda
INIZIO
Temp *- Root
// All'inizio Temp prende la radice dell'albero
O *^ NUOVO CodaO // Si crea un oggetto di classe Coda
SE (Temp * NULL)
// Se l'albero non è vuoto
ALLORA
O.lnserisci(Temp)
MENTRE (NOT O.TestVuotaO ) ESEGUI // Finché la c o d a non è vuota
// Estrai dalla c o d a un Nodo
Temp «- O.EstraiO
// Visualizza (visita) l'informazione del nodo
SCRIVI(Temp.lnfo)
// Se il figlio sinistro non è vuoto
SE (Temp.SX * NULL)
ALLORA
// Inserisci il figlio sinistro nella c o d a
O.lnserisci(Temp.SX)
FINESET
226
B L O C C O TEMATICO E
STRUTTURE DI DATI
•
•
•
•
•
•
// Se il figlio destro non è vuoto
SE (Temp.DX * NULL)
ALLORA
O.lnserisci(Temp.DX)
FINESE
FINEMENTRE
FINESE
FINE
// Inserisci il figlio destro nella coda
Il parametro Root è di classe AlberoBinario, mentre la variabile Q è di classe Coda.
Consideriamo l'albero binario mostrato nella figura qui sotto. Applicando l'algoritm o otteniamo quanto mostrato nella tabella che segue.
Coda Q
Temp
Visualizzazione
vuota
E
E
E
E
B G
B
B
G D
G
G
D F H
D
D
F H
F
F
H
H
H
vuota
All'inizio, con Q vuota, Temp prende il n o d o E (la radice dell'albero). Poiché il n o d o
non è vuoto, lo inserisce nella coda Q.
Il ciclo estrae dalla coda il n o d o E, visualizza il contenuto del campo Info e passa
ad analizzare i suoi figli. Se il figlio sinistro n o n è vuoto lo inserisce nella coda Q,
altrimenti passa ad analizzare i figlio destro.
Analogamente, se questo n o n è vuoto, lo inserisce in coda. Nel nostro esempio inserisce in coda i nodi B e G in questo ordine. La condizione del ciclo è ancora vera
(Q n o n è vuoto) e quindi Temp prende il n o d o B. Visualizza il contenuto del campo
Info e passa ad analizzare i suoi figli.
Per come è stato strutturato l'algoritmo e per le strutture dati di appoggio utilizzate
(una coda), esso procede analizzando tutti i nodi di u n livello e poi passa ai nodi del
livello successivo; così come mostra la figura seguente:
"*
E
*___D
F
H
ALBERI UNITÀ DI APPVENWMBOO 3