HomeWork060704 < Programmazione2pz

---++ 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 T<sub>1</sub>,... T<sub>n</sub>, la sua rappresentazione è<br />
      l n t<sub>1</sub> ... t<sub>n</sub> <br />
   dove t<sub>1</sub> ... t<sub>n</sub> sono le espressioni che rappresentano gli alberi T<sub>1</sub>,... T<sub>n</sub>.

*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

   <img src="%ATTACHURLPATH%/AlberoNario.jpg" alt="AlberoNario.jpg" width='354' height='307' />

   1. 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).
   2. Scrivere una funzione che preso un albero n-ario rappresentato per mezzo di un albero binario stampa la sequenza che lo rappresenta.
   3. 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<sup>*</sup> la trasformazione di un albero t, se t =   l n t<sub>1</sub> ... t<sub>n</sub>, allora  t<sup>*</sup> =   l n t<sub>n</sub><sup>*</sup> ... t<sub>1</sub><sup>*</sup>. <br /> 
   *Esempio* L'albero dell'esempio precedente diviene <br />
   <img src="%ATTACHURLPATH%/AlberoNarioRev.jpg" alt="AlberoNarioRev.jpg" width='423' height='307' />

-- Users.StefanoGuerrini - 05 Jun 2007
This topic: Programmazione2pz > WebHome > AnnoAcc0607 > HomeWork0607 > HomeWork060704
Topic revision: r1 - 2007-06-05 - StefanoGuerrini