DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Esercitazione alberi ======

===== Esercizio 1: conta occorrenze =====
Definire il tipo ''albero_s_t'' di un albero binario in cui le etichette sono stringhe di al piu' 20 caratteri. Scrivere una funzione
<code c>
int conta_occorrenze ( albero_s_t * root, char * s );
</code>
che conta le occorrenze della stringa ''s'' nell'albero di radice ''root'' e restituisce tale numero.

===== Esercizio 2: somma =====
Definire il tipo ''albero_d_t'' di un albero binario in cui le etichette sono valori di tipo ''double''. Scrivere una funzione 
<code c>
double somma_le_foglie ( albero_d_t * root);
</code>
che restituisce la somma dei valori delle etichette delle sole foglie dell'albero.
 

===== Esercizio 3: Alberi binari di ricerca =====
Un albero binario di ricerca e' un albero in cui in ogni nodo $n$ e' verificata la relazione
$$ E(n_{sx}) \leq E(n) \leq E(n_{dx}) $$ 
dove $n_{sx}$ e' un qualsiasi nodo dell'albero di sinistra e $n_{dx}$ e' un qualsiasi nodo dell'albero di destra.
Utilizzando il tipo ''albero_d_t'' realizzate le seguenti funzioni:

<code c>
/* inserisce l'etichetta x nell'albero mantenedolo ordinato, 
restituisce il puntatore al nuovo albero */
albero_d_t* inserisci_ord ( albero_d_t * root, double x );
/* ricerca l'etichetta x nell'albero analizzando un numero di nodi pari all'altezza dell'albero 
 restituisce 1 se la trova e 0 se non la trova */
int ricerca ( albero_d_t * root, double x );
/* cancella l'etichetta x nell'albero mantenedolo ordinato e deallocando il nodo (difficile!) oppure utilizzando un
campo in più nella struttura che indica se il nodo è stato cancellato e
restituisce il puntatore al nuovo albero */
albero_d_t* cancella_ord ( albero_d_t * root, double x );
</code>


===== Approfondimenti: (avanzato) Eulero e il problema dei ponti di Koeningsberg =====

Questo e' il [[http://it.wikipedia.org/wiki/Problema_dei_ponti_di_K%C3%B6nigsberg|link]] al problema di Eulero che ha dato origine alla teoria dei grafi. Come si potrebbe rappresentare usando una struttura ricorsiva ?