Visita per profondità di un albero generico

(1)

1

Università di Torino – Facoltà di Scienze MFN Corso di Studi in Informatica Curriculum SR (Sistemi e Reti)

Algoritmi e Laboratorio a.a. 2006-07 Lezioni

prof. Elio Giovannetti

Parte 16bis – Alberi binari: visite completamente iterative.

Quest' opera è pubblicata sotto una Licenza Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

08/02/2007 E. Giovannetti - AlgELab-06-07 - Lez.16 2

Visita per profondità di un albero generico

Visita per profondità (depth-first) di un albero: un percorso che, per ogni nodo, visita ciascuno dei sottoalberi-figli del nodo in modo completo separatamente dagli altri; la visita della radice può essere effettuata prima e/o dopo le visite dei sottoalberi, e/o fra di esse (quindi anche più volte)

α α α α

T1

...

Tn

T1

...

Tn

Le visite in pre-ordine, inordine e postordine sono esempi di visite per profondità di un albero binario.

Definizione induttiva di visita per profondità (da sinistra) La più generale visita di un albero per profondità è:

dfvisit(albero di radice ααααe figli T1, ...Tn) = nodePrevisit(αααα), (pre-visita della radice)

dfvisit(T1), (visita per profondità del primo figlio) nodeInvisit1(αααα), (prima visita intermedia della radice) dfvisit(T2), (visita per profondità del secondo figlio) nodeInvisit2(αααα), (seconda visita intermedia della radice) ...

dfvisit(Tn), (visita per profondità dell'ultimo figlio) postvisit(αααα). (post-visita della radice)

Naturalmente alcune delle visite della radice, ad es. tutte quelle intermedie, possono essere nulle, cioè non venire effettuate.

Visite per profondità, ricorsione, iterazione.

• Una visita per profondità si realizza in modo naturale con un algoritmo ricorsivo, corrispondente alla definizione induttiva.

• Un algoritmo iterativo, tuttavia, sarebbe utile per poter disporre di una "posizione corrente" su un albero la quale possa avanzare come un indice in un array, di un passo alla volta separatamente.

• Nel caso in cui sia assente la postvisita della radice, come nelle visite preorder e inorder di albero binario, l'ultima chiamata ricorsiva, essendo di coda, può essere eliminata, ma l'algoritmo rimane (semi-)ricorsivo.

• Per ottenere un algoritmo esclusivamente iterativo occorre idearlo in modo completamente diverso, a partire da un opportuno invariante.

Alberi binari: visita in preordine iterativa.

Invariante (situazione al passo generico):

T1 ^T2

...

Tn

Nota: alcuni dei T1, ..., Tn (o anche tutti) possono essere vuoti.

T1, T2, ... , Tnè una sequenza di alberi binari da visitare ciascuno in preordine, uno dopo l'altro da T1a Tn.

Azioni da eseguire (corpo del ciclo)– due casi:

•T1è vuoto: lo si elimina, e la sequenza diventa T2, ..., Tn;

•T1non è vuoto: allora ha una radice e due figli;

...

Tn T2 α

α α α

T11 T12 continua nella

slide seguente

Alberi binari: visita in preordine iterativa (continua).

si visita il nodo , poi la sequenza di alberi da visitare in preordine diventa:

α α α α

T2 Tn

T11 T12

...

Il ciclo termina quando non vi sono più alberi da visitare, cioè quando la sequenza è vuota.

Chiamando Sla sequenza di alberi:

while(Snon è vuota) {

estrai da S il primo elemento, sia essoT;

if(Tnon è l'albero vuoto) { visita il suo nodo radice;

rimetti in testa aSi sottoalberi sinistro e destro diT;

} }

(2)

2

Ma una sequenza in cui

si estraggono e si immettono elementi solo in testa è uno stack (o pila) !

Inizializzazione:

• la sequenza iniziale è la sequenza costituita da un solo elemento che è l'albero da visitare (eventualmente vuoto);

• nella programmazione a oggetti ogni (sotto-)albero è rappresentato dall'oggetto-nodo costituente la sua radice, e l'intero albero è rappresentato dall'oggetto puntato dal campo root dell'oggetto della classe BinTree;

Inoltre (forma del ciclo):

poiché la sequenza iniziale non è mai vuota (contiene l'albero puntato da root) il corpo delwhileviene eseguito almeno una volta: allora è conveniente trasformare il whilein un do, in modo da evitare una inutile prima esecuzione del test.

Dopo aver definito una opportuna classe StackDiNodi, dotata dei metodi add e remove, si ha, nella classe-albero:

public void preOrderIt() {

StackDiNodi stack = new StackDiNodi();

stack.add(root);

do {

Node node = stack.remove();

if(node != null) {

System.out.println(node.element);

stack.add(node.right);

stack.add(node.left);

}

} while(!stack.empty());

}

Si noti che per ottenere la sequenza T11 T12T2 ... Tn occorre immettere nello stack (push) primaT12e poiT11.

Usando la classe Stack delle API Java:

Stack<Node> stack = new Stack<Node>();

stack.push(root);

do {

Node node = stack.pop();

if(node != null) {

stack.push(node.right);

stack.push(node.left);

}

Alberi binari: visita in preordine iterativa. Ottimizzazione.

È inutile mettere nello stack i sottoalberi vuoti. Allora:

Invariante (situazione al passo generico):

T1 T2

...

Tn

T1, T2, ... , Tnè una sequenza di alberi binari non vuotida visitare ciascuno in preordine, uno dopo l'altro da T1a Tn.

Azioni da eseguire (corpo del ciclo):

• T1 è sicuramente non vuoto:

allora ha una radice e due figli;

...

Tn T2 α

αα α

T11 T12 continua nella

slide seguente

si visita il nodo , poi la sequenza di alberi da visitare in preordine diventa:

α α α α

T2 Tn

T11 T12

...

dove T11 e T12 vengono aggiunti solo se non vuoti.

Chiamando Sla sequenza di alberi:

while(Snon è vuota) {

estrai da S il primo elemento, sia essoT;

visita il suo nodo radice;

if(T1.destrnon è vuoto) aggiungilo in testa alla sequenza;

if(T1.sinistnon è vuoto) aggiungilo in testa alla sequenza;

} }

se non vuoto se non vuoto

(3)

3

Alberi binari: visita in preordine iterativa. Ottimizzazione.

Naturalmente, anche l'intero albero iniziale, cioè root, va messo sullo stack solo se non nullo.

Anche in questa versione si può evitare un test inutile trasformando il whilein un do.

if(root != null) { stack.push(root);

do {

if(node.right != null) stack.push(node.right);

if(node.left != null) stack.push(node.left);

} }

Alberi binari: visita in inordine iterativa (ottimizz.)

• Idea: per visitare un albero in inordine occorre visitare in inordine i suoi due sottoalberi, ma fra la visita del sinistro e quella del destro occorre visitare la radice.

• Al passo generico la sequenza ancora da visitare sarà quindi una sequenza mista di nodi singoli e di (sotto-)alberi.

Invariante:

P1, P2, ... , Pnè una sequenza di oggetti ancora da visitare, ognuno dei quali può essere un albero non vuoto da visitare in inordine oppure un nodo singolo da visitare:

P1 P2

...

Pn

Alberi binari: visita in inordine iterativa (continua).

Azioni (corpo del ciclo) – due casi:

• P1 è un nodo singolo αααα:

...

_Pn

P2 α αα α

lo si toglie dalla sequenza e lo si visita;

la nuova sequenza è quindi:

...

Pn

P2

continua nella slide seguente

• P1 è un albero (non vuoto), quindi ha due sottoalberi:

...

Pn P2 α

α α α

TL TR

non si visita nessun oggetto, ma la sequenza di oggetti da visitare diventa:

T2 Tn

TL TR

...

se non vuoto se non vuoto

αα αα

cioè l'albero P1 viene tolto dalla sequenza e al suo posto vengono messi in testa alla sequenza TL(se non è vuoto), αααα, e TR(se non è vuoto):

In Java, se isLeaf (= èUnaFoglia) è un metodo di Node che verifica se il nodo è una foglia o no:

public void InOrderIt() {

if(root != null) { stack.push(root);

do {

if(node.isLeaf())

else {

if(node.right != null) stack.push(node.right);

stack.push(new Node(node.element));

if(node.left != null) stack.push(node.left);

}

} }

Esercizi

• Esercizio 1.Definire la versione di inOrderItpiù semplice (non ottimizzata) che mette sullo stack anche i sottoalberi vuoti, analoga alla prima versione di preOrderIt.

• Esercizio 2.Definire una versione completamente iterativa della visita in post-ordine (postOrderIt).

(4)

4

Visita per larghezza (breadth-first) o per livelli

A differenza delle visite per profondità, la visita per livelli nonè definibile per induzione strutturale sull'albero; cioè la visita per livelli di un albero non è definibile in termini di visite per livelli del sottoalbero sinistro e di quello destro.

Fallisce cioè il passo induttivo.

Visita per livelli (continuazione)

La visita per livelli visita un dato livello di più sottoalberi, poi passa al livello successivo, ecc. L'algoritmo è inerentemente iterativo.

Invariante:

T1, T2, ..., Tnè una sequenza di alberi da visitare per livelli contemporaneamente, cioè: si deve visitare prima la radice di T1, la radice di T2, ... , la radice di Tn; poi il livello 1di T1, di T2, ..., di Tn; poi il livello 2 ..., ecc.:

Visita per per livelli (continuazione)

Corpo del ciclo:

Si estrae il primo elemento T1della sequenza. Due casi:

• T1è un albero vuoto:

lo si butta via, e la nuova sequenza è T2, ..., Tn;

(ovviamente nella versione ottimizzata, che non mette nella sequenza sottoalberi vuoti, questo caso non si presenta mai)

• T1non è vuoto:

allora ha un nodo-radice e due sottoalberi figli: (T11 ααααT12) La visita per livelli di (T11 ααααT12)equivale a:

• visita del nodo αααα;

• visita del livello 0(radice) di T2, ..., Tn;

• visita del livello 0(radice) di T11, T12;

• ...

• visita del livello kdi T2, ..., Tn;

• visita del livello kdi T11, T12;

• ...

Visita per per livelli (continuazione)

Quindi corpo del ciclo:

se la sequenza è (T11 ααααT12), T2, ... Tn

• si visita il nodo a;

• la sequenza da visitare per livelli diventa:

T2, ..., Tn,T11, T12

Sulla sequenza si fanno dunque estrazioni solo dalla testa, ma inserimenti solo in fondo: è una coda !

cioè:

Visita per per livelli (continuazione)

L'algoritmo è lo stesso di quello della visita per profondità in preordine, ma usando una coda invece di una pila.

public void visitaPerLivelli() { CodaDiNodi q = new CodaDiNodi();

q.add(root);

while(!q.empty()) { Node node = q.remove();

if(node != null) {

q.add(node.left);

q.add(node.right);

} } }

Ma nota l'ordine scambiato degli add rispetto al preorder !

Esercizio 3 (facile).

Scrivere la versione della visita per livelli che non inserisce nella coda gli alberi vuoti.