Algoritmi di visita in profondità (DFS) di un albero binario

lezione 27
Algoritmi di visita in profondità (DFS)
di un albero binario
Algoritmo di visita di un albero binario
in ordine anticipato (versione ricorsiva)
MO PreOrdine(T: AlberoBinario)
» INIZIO
SE (T * NULL))
ALLORA
SCRIVI(T.lnfo)
PreOrdine(T.SX)
PreOrdine(T.DX)
FINESE
Algoritmo di visita di un albero binario
in ordine simmetrico (versione ricorsiva)
ALGORITMO InOrdineQ:
• l
SE (T * NULL)
ALLORA
InOrdine(T.SX)
SCRIVI(T.lnfo)
InOrdine(T.DX)
FINESE
: m
AlberoBinario)
//
//
//
//
(1)
(2)
(3)
(4)
Algoritmo di visita di un albero binario
in ordine posticipato (versione ricorsiva)
• ALGORITMO PostOrdine(T: AlberoBinario)
• INIZIO
•
SE ( T * NULL)
•
ALLORA
PostOrdine(T.SX)
•
PostOrdine(T.DX)
p
SCRIVKT.Info)
•
FINESE
• FINE
Come già sappiamo, questi algoritmi ricorsivi utilizzano una pila, ma i n m o d o i m p l i c i t o .
La pila utilizzata è, infatti, la
durante l'esecuzione del programma, ospitata nel segmento STACK della m e m o r i a .
Consideriamo l ' a l g o r i t m o InOrdineQ.
V e d i a m o i n dettaglio l'evoluzione della pila dei
record d i attivazione durante le chiamate ricorsive q u a n d o si visita l'albero mostrato
nella figura.
pila dei record di attivazione delle chiamate di funzione
1. I n i z i a l m e n t e la p i l a d i esecuzione è vuota.
2. Alla p r i m a chiamata vengono inseriti nella pila l'indirizzo d i r i t o r n o d i InOrdineQ e i l
valore 15. L'albero d i cui 15 è radice n o n è v u o t o , pertanto, InOrdineQ viene invocato
per i l n o d o con valore 4.
3. Vengono inseriti nella pila i l valore d i r i t o r n o (2), cioè i l p u n t o i n cui deve c o n t i n u are l'esecuzione d o p o aver eseguito InOrdineQ,
e i l valore corrente d i N , 4. P o i c h é
TestVuotoQ restituisce falso, InOrdineQ sta per essere invocato per i l figlio sinistro d i
N c i o è 1.
4. Per p r i m a cosa i l valore d i ritorno (2) e i l valore 1 vengono memorizzati nella pila.
5. InOrdineQ viene invocato con i l figlio sinistro del n o d o 1 (cioè N U L L ) . L'indirizzo d i
r i t o r n o (2) e i l valore d i N , N U L L , vengono m e m o r i z z a t i nella pila. P o i c h é N è N U L L ,
InOrdineQ t e r m i n a immediatamente; all'uscita del m e t o d o la documentazione d i attivazione viene eliminata dalla pila.
6. i l sistema guarda ora la sua pila d i esecuzione, ripristina i l valore d i N: 1, esegue
l'enunciato all'indirizzo (2) e visualizza i l valore 1. P o i c h é N n o n è stato esaminato
completamente, i l valore d i N e l'indirizzo (2) si trovano ancora sulla pila.
238
B L O C C O TEMATICO E
STRUTTURE DI DATI
7. C o n i l figlio destro d i N, 1, viene eseguito l'enunciato all'indirizzo (3) che è
la successiva chiamata d i InOrdineQ.
Prima p e r ò vengono inseriti nella pila
l ' i n d i r i z z o (4) e i l valore corrente d i N , N U L L . P o i c h é N è N U L L , InOrdineQ term i n a e la pila viene ripulita.
8. I l sistema ripristina ora i l vecchio valore d i N , 1, ed esegue l'enunciato (4).
9. P o i c h é questa è la terminazione d i InOrdineQ, i l sistema e l i m i n a la documentazione d i attivazione corrente e usa d i n u o v o la pila, r i p r i s t i n a n d o i l valore d i N , 4,
e riprendendo l'esecuzione dall'enunciato ( 2 ) . Questo visualizza i l n u m e r o 4 e
q u i n d i invoca InOrdineQ per i l figlio destro d i N, che è N U L L .
Questi sono solo i p r i m i passi, t u t t i sono dettagliati nella pila dei record d i attivazione:
1
(chiamante)
4
(2)
15
5
(chiamante)
(2)
4
(2)
15
5
(chiamante)
NULL
(2)
1
(2)
4
(2)
15
5
(chiamante)
NULL
(2)
1
(2)
4
(2)
15
5
(chiamante)
1
(2)
4
(2)
15
5
(chiamante)
Stampa (1)
A t i t o l o d i esempio, a lato è
mostrata la versione iterativa
dell'algoritmo
PreOrdineQ.
Tale versione è due volte p i ù
lunga dell'equivalente versione ricorsiva, m a è ancora u n a l g o r i t m o corto e leggibile.
È, tuttavia, appesantita dalla gestione della pila d i supporto.
Algoritmi iterativi per la visita in
profondità di un albero binario
Algoritmo di visita di un albero binario
in ordine anticipato (versione iterativa)
ALGORITMO PreOrdineCRoot: AlberoBinario)
P:Pila
T: AlberoBinario
T «- Root
// Root rappresenta la radice
P - NUOVO PilaO
SE (T * NULL)
ALLORA
P.Push(A)
MENTRE (NOT TestVuoto(P)) ESEGUI
T - P.PopO
SCRIVI(T.lnfo)
SE (T.DX * NULL)
ALLORA
P.Push(T.DX) // In cima alla pila
FINESE
SE (T.SX * NULL)
15 4 — Testa
4
P.Push(T.SX)
FINESE
FINEMENTRE
FINESE
Testa
20
Testa
16
25
Testa
Testa
15
Scrivici
Scrivi-^4
4»- Testa
AÌ.Ì.OPA
20
25 « — Testa
Scrivilo
20
Testa
4 — Testa
ALBERI
UNITÀ D! APPRENDIMENTO 3
23