HomeWork8aa0203 < Programmazione1/AA0506/PZ

---++ Homework 8 - alberi binari
Vedi anche: DomandeHomework8aa0203, SoluzioneHomework8aa0203, RisultatiHomework8aa0203.
----
%TOC%
----
---+++ Obiettivi
   * lettura in preordine di un albero binario
   * stampa in postordine di un albero binario

---+++ Alberi binari
Un albero binario è composto da nodi formati da 3 campi:
   * *valore* che contiene il valore (intero) associato al nodo
   * *sinistro* che contiene un puntatore al nodo radice del sottoalbero sinistro (oppure NULL)
   * *destro* che contiene un puntatore al nodo radice del sottoalbero destro (oppure NULL)

Parlando di alberi di usano i seguenti termini:
   * *radice* è il nodo più in alto (in informatica gli alberi sono disegnati a testa in giù :-) )
   * *figli* sono i (due) nodi che un nodo ha subito sotto
   * *foglia* è un nodo che non ha figli

---++++ Esempi
<center>
|  http://twiki.dsi.uniroma1.it/cgi-bin/webdot/pub/%WEB%/%TOPIC%/albero.dot.dot.png  |  http://twiki.dsi.uniroma1.it/cgi-bin/webdot/pub/%WEB%/%TOPIC%/albero-2.dot.dot.png  |
</center>

Negli esempi:
   * la *radice* è il nodo che contiene il valore *1*
   * le foglie dell'esempio a sinistra sono i nodi *6, 7, 5, 3*
   * le foglie dell'esempio a destra sono i nodi *5, 6, 7*
   * i *figli* del nodo *2* dell'esempio di sinistra sono i nodi *4, 5*

---+++ Ordinamenti
---++++ Preordine
La lettura (o scrittura) in *preordine* viene eseguita ricorsivamente seguendo il seguente schema:
   * prima si legge (o stampa) il valore del nodo radice
   * poi si legge (o stampa) il sottoalbero sinistro
   * poi si legge (o stampa) il sottoalbero destro

---++++ Inordine
La lettura (o scrittura) in *inordine* viene eseguita ricorsivamente seguendo il seguente schema:
   * prima si legge (o stampa) il sottoalbero sinistro
   * poi si legge (o stampa) il valore del nodo radice
   * poi si legge (o stampa) il sottoalbero destro

---++++ Postordine
La lettura (o scrittura) in *postordine* viene eseguita ricorsivamente seguendo il seguente schema:
   * prima si legge (o stampa) il sottoalbero sinistro
   * poi si legge (o stampa) il sottoalbero destro
   * poi si legge (o stampa) il valore del nodo radice

---+++ Svolgimento
Si scriva un programma C che legge da *stdin* un albero binario in *preordine* e lo stampa su *stdout* in *postordine* 
%RED% *seguendo il formato specificato qua sotto sia per l'input che per l'output* %FINE%.

---+++ Formato del grafo
Nel seguito ==&lt;esiste sottoalbero ...>== può valere:
   * *0* = non esiste
   * *1* = esiste
Nel seguito ==&lt;sottoalbero XXX (se esiste)>== indica che:
   * se l'indicatore ==&lt;esiste sottoalbero XXX>== valeva *1*
      * a partire da quella riga bisogna leggere (o scrivere) un albero
      * quell'albero è il sottoalbero figlio XXX (sinistro o destro) del nodo corrente
   * altrimenti il sottoalbero XXX non c'e' e non appare nell'input (o output)

---++++ Preordine
Il grafo (in *preordine*) viene specificato da una successione di righe che seguono il formato seguente:
<verbatim>
<valore della radice>
<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<sottoalbero destro (se esiste)>
</verbatim>

---++++ Inordine
Il grafo (in *inordine*) viene specificato da una successione di righe che seguono il formato seguente:
<verbatim>
<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<valore della radice>
<sottoalbero destro (se esiste)>
</verbatim>

---++++ Postordine
Il grafo (in *postordine*) viene specificato da una successione di righe che seguono il formato seguente:
<verbatim>
<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<sottoalbero destro (se esiste)>
<valore della radice>
</verbatim>

---+++ Esempio di formato usato per input e/o output
Ecco le diverse rappresentazioni di un grafo:
<center>
<table border="1">
<tr><th>Grafo</th><th>Preordine</th><th>Inordine</th><th>Postordine</th></tr>
<tr valign="top"><td align="center">
http://twiki.dsi.uniroma1.it/cgi-bin/webdot/pub/%WEB%/%TOPIC%/albero.dot.dot.png
</td><td>
<verbatim>
1
1 1
2
1 1
4
1 1
6
0 0
7
0 0
5
0 0
3
0 0
</verbatim>
</td><td>
<verbatim>
1 1
1 1
1 1
0 0
6
4
0 0
7
2
0 0
5
1
0 0
3
</verbatim>
</td><td>
<verbatim>
1 1
1 1
1 1
0 0
6
0 0
7
4
0 0
5
2
0 0
3
1
</verbatim>
</td></tr>
<tr><th>Grafo</th><th>Preordine</th><th>Inordine</th><th>Postordine</th></tr>
<tr valign="top"><td>
http://twiki.dsi.uniroma1.it/cgi-bin/webdot/pub/%WEB%/%TOPIC%/albero-2.dot.dot.png
</td><td>
<verbatim>
1
1 1
2
1 0
5
0 0
3
0 1
4
1 1
6
0 0
7
0 0
</verbatim>
</td><td>
<verbatim>
1 1
1 0
0 0
5
2
1
0 1
3
1 1
0 0
6
4
0 0
7
</verbatim>
</td><td>
<verbatim>
1 1
1 0
0 0
5
2
0 1
1 1
0 0
6
0 0
7
4
3
1
</verbatim>
</td></tr></table>
</center>

---+++ Opzionale
Si faccia in modo che il programma possa accettare sulla riga di comando un parametro che può valere:
   * *pre*  l'albero letto viene stampato in *preordine*
   * *in*   l'albero letto viene stampato  in *inordine*
   * *post* l'albero letto viene stampato in *postordine*
Se il parametro non è presente l'albero letto viene stampato in *postordine*

-- Users.AndreaSterbini - 17 Dec 2002

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group
This topic: Programmazione1/AA0506/PZ > DomandeHomework8aa0203 > HomeWork8aa0203
Topic revision: r9 - 2003-09-30 - AndreaSterbini