Homework (compito per casa) 5

Alberi di Natale

Vedi anche: DomandeHomework504, SoluzioneHomework504, RisultatiHomework504

---

---

Descrizione

In un albero binario di interi, una pallina rossa è un nodo in cui la radice è etichettata con un numero intero maggiore o uguale di tutte le etichette presenti nei sottoalberi. Una pallina blu è un nodo in cui la radice è etichettata con un numero intero minore o uguale a tutte le etichette presenti nei sottoalberi. Un nodo esterno destro è o la radice o il figlio destro di un nodo esterno destro. Un nodo esterno sinistro è o la radice o il figlio sinistro di un nodo esterno sinistro. Un nodo e' esterno se è un nodo esterno sinistro o esterno destro. Un albero di natale è un albero binario di interi in cui i nodi esterni sono tutti o palline blu o palline rosse. Il programma dovrà semplicemente stampare 1 se l'albero in input è un albero di natale e 0 altrimenti.

Input

L'albero in input verrà rappresentato da una stringa che segue la seguente sintassi:

• l' albero vuoto è rappresentato dal carattere '*';
• un albero foglia (cioè un albero con entrambi i figli vuoti) è rappresentato semplicemente dal contenuto del campo informazione;
• gli altri alberi sono rappresentati nella forma: radice(FS, FD), dove radice è il contenuto dell'informazione nella radice e FS ed FD sono rispettivamente rappresentazione del sottoalbero sinistro e destro.

Ad esempio, la stringa "3(6, 8(1,4(*,2)))" rappresenta l'albero binario:

 
............3
........6..........8
............... 1.....4
.........................2

Osservate che le foglie, sono riconoscibili dal fatto che non sono seguite dal carattere "(". Suggerimento: osservate che se scrivete una procedura ricorsiva per creare un albero in memoria con la consueta struttura a puntatori, osservate che la presenza di una virgola chiude la lettura di un sottoalbero sinistro, e la presenza di una parentesi tonda chiusa chiude la lettura di un sottoalbero destro.

Output

• produrre in output semplicemente il numero 1 o il numero 0 a seconda che l'albero di input sia o non sia un albero di Natale.

IMPORTANTE

• non far produrre al programma altri output oltre a quelli richiesti.

Ecco un esempio di input in cui il programma deve rispondere 0:

 

8(4(6,2),5(1,*))  

Questo perchè c'è un nodo esterno (il 4), che non è nè una pallina blu, nè una pallina rossa).

Ecco un esempio di input in cui il programma deve rispondere 1:

 

8(1(6,2),5(1,*))

In questo caso la radice è una pallina rossa, l'1 è una pallina blu, il 5 una pallina rossa. Osservate che, stando alle definizioni date, le foglie sono sempre sia palline blu che palline rosse.

Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!

Come compilare ed eseguire il programma

• usate un editor per scrivere il testo del programma e salvatelo in formato testo semplice in un file con l'estensione .c (ad esempio di nome trexpuno.c)
  • NON usate Word, Openoffice, Kword, Abiword che introducono caratteri strani
• compilate (e contemporaneamente linkate) il programma con il comando

gcc -g -o natale natale.c

• eseguite il programma scrivendo

./natale

Come consegnare il programma

• Avete tempo fino a Venerdì 14 gennaio alle ore 23.59 (ora sono le 01:07 del 25).
• Consegnate il testo del programma sorgente C da voi scritto. Io lo compilerò e testerò.
• Usate esclusivamente la pagina di consegna. Non verranno accettate spedizioni via email.

• Set ALLOWTOPICCHANGE = DocentiProg1Group

-- IvanoSalvo - 16 Dec 2004