Homework 8 - alberi binari

Vedi anche: DomandeHomework8aa0203, SoluzioneHomework8aa0203, RisultatiHomework8aa0203.

---

---

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

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 seguendo il formato specificato qua sotto sia per l'input che per l'output .

Formato del grafo

Nel seguito <esiste sottoalbero ...> può valere:

• 0 = non esiste
• 1 = esiste

Nel seguito <sottoalbero XXX (se esiste)> indica che:

• se l'indicatore <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:

<valore della radice>
<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<sottoalbero destro (se esiste)>

Inordine

Il grafo (in inordine) viene specificato da una successione di righe che seguono il formato seguente:

<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<valore della radice>
<sottoalbero destro (se esiste)>

Postordine

Il grafo (in postordine) viene specificato da una successione di righe che seguono il formato seguente:

<esiste sottoalbero sinistro> <esiste sottoalbero destro>
<sottoalbero sinistro (se esiste)>
<sottoalbero destro (se esiste)>
<valore della radice>

Esempio di formato usato per input e/o output

Ecco le diverse rappresentazioni di un grafo:

Grafo	Preordine	Inordine	Postordine
	1 1 1 2 1 1 4 1 1 6 0 0 7 0 0 5 0 0 3 0 0	1 1 1 1 1 1 0 0 6 4 0 0 7 2 0 0 5 1 0 0 3	1 1 1 1 1 1 0 0 6 0 0 7 4 0 0 5 2 0 0 3 1
Grafo	Preordine	Inordine	Postordine
	1 1 1 2 1 0 5 0 0 3 0 1 4 1 1 6 0 0 7 0 0	1 1 1 0 0 0 5 2 1 0 1 3 1 1 0 0 6 4 0 0 7	1 1 1 0 0 0 5 2 0 1 1 1 0 0 6 0 0 7 4 3 1

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

-- AndreaSterbini - 17 Dec 2002

• Set ALLOWTOPICCHANGE = DocentiProg1Group