Alberi n-ari
Supponiamo di rappresentare alberi n-ari non vuoti etichettati con interi per mezzo di espressioni in base alla seguente regola
- se la radice dell'albero T ha etichetta l e n sotto-alberi T1,... Tn, la sua rappresentazione č
l n t1 ... tn
dove t1 ... tn sono le espressioni che rappresentano gli alberi T1,... Tn.
Esempio L'espressione
1 2 2 1 3 2 1 0 2 0 -2 3 4 0 0 2 -6 0 0 0 3 1 -1 2 1 0 4 1 -6 0
rappresenta l'albero
- Scrivere una funzione che legge da input la sequenza che rappresenta un albero n-ario e costruisce la rappresentazione dell'albero n-ario sotto forma di albero binario (il figlio sinistro punta al primo figlio nella lista dei figli del nodo, mentre il figlio destro punta al fratello successivo nella lista dei figli del padre del nodo).
- Scrivere una funzione che preso un albero n-ario rappresentato per mezzo di un albero binario stampa la sequenza che lo rappresenta.
- Scrivere una funzione che preso un albero n-ario rappresentato mediante albero binario inverte l'ordine della lista dei figli di ogni nodo. Ovvero, indicando con t* la trasformazione di un albero t, se t = l n t1 ... tn, allora t* = l n tn* ... t1*.
Esempio L'albero dell'esempio precedente diviene
--
StefanoGuerrini - 05 Jun 2007