Esercitazione 1

Scrivere un programma C che realizzi degli alberi binari ordinati di interi. Gli alberi binari ordinati sono tali che il valore memorizzato in un nodo è minore o uguale di tutti quelli memorizzati nel sottoalbero destro e maggiore o uguale di tutti quelli memorizzati nel sottoalbero sinistro.

Definire il tipo nodo che rappresenta il nodo generico dell'albero in modo opportuno. Si richiede di implementare almeno:

• inserisci() che permette di inserire un nuovo intero nell'albero
• cancella() che permette di cancellare un intero (se presente)
• cerca() che permette di stabilire se un intero e' presente nell'albero
• stampa() che stampa in modo ordinato tutti i valori di un albero
• main() che effettua un opportuno testing delle funzioni implementate

Suddividere il programma C relativo all'esercizio 1 in piu' file in modo che:

• il main() sia contenuto in un file a parte rispetto alle altre funzioni
• due opportuni file .c e .h per le altre funzioni (inserisci/cancella/cerca)

Sviluppare inoltre un opportuno makefile che contenga almeno i seguenti target:

• all che permette di ricreare l'eseguibile di test
• test test che esegue il test e confronta l'output con l'output atteso segnalando opportuni errori
• cleanall che elimina i file di core e gli oggetti della compilazione.

Si considerino gli alberi ordinati degli esercizi 1 e 2: si realizzino due funzioni map_albero e reduce_albero:

• La map_albero applica una funzione f (di tipo int (*f)(int))a tutti gli interi sull'albero sostituendo ogni intero x con f(x).
• La reduce_albero 'somma' tutti gli interi nell'albero con l'operatore associativo (*f), di tipo int (*f)(int,int)

Definire inoltre un opportuno main di test ed estendere il makefile (ove necessario).