III esercizio (04/05/05): stampa per livelli di un albero binario
Per rappresnetare alberi binari etichettati con valori interi positivi, si utilizzi la rappresentazione prefissa definita nel seguente modo
T ::= p T1 T2 | n
dove
p
è un intero positivo, mentre
n
è un intero negativo. Il numero
p
è l'etichetta del nodo che ha come sottoalberi
T1
e
T2
, mentre
n
è un intero negativo e serve a denotare una foglia contente il vaolore (positivo)
-n
.
Si deve scrivere un programma che legge da input un albero scritto nella precedente rappresentazione prefissa e lo stampa per livelli.
Si ricorda che per stampare un albero per livelli si può utilizzare una coda, ricorrendo al seguente algoritmo
- poni la radice dell'albero nella coda
- fino a che ci sono nodi nella coda, preleva il nodo in testa alla coda, stampa la sua etichetta e inserisci in fondo alla coda i suoi figli (se ne ha).
--
StefanoGuerrini - 05 May 2005