Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- fisica:informatica:201415:esercitazioni:esercitazione12 [07/04/2015 alle 15:35 (11 anni fa)] – creata Susanna Pelagatti
+++ fisica:informatica:201415:esercitazioni:esercitazione12 [13/05/2015 alle 09:30 (11 anni fa)] (versione attuale) – [Esercizio 5: Alberi binari di ricerca] Susanna Pelagatti
@@ Linea 30: / Linea 30: @@
 lista_d_t * tree_to_list ( albero_d_t * root );
 </code>
+===== Esercizio 5: 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 inserisci_ord ( albero_d_t * root, double x );
+/* cancella l'etichetta x nell'albero mantenedolo ordinato e deallocando l'etichetta (difficile!)
+restituice il puntatore al nuovo albero */
+albero_d_t* cancella_ord ( albero_d_t * root, double x );
+</code>
+===== Approfondimenti: 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 teria dei grafi che abbiamo accennato nella lezione di oggi