Strumenti Utente

Strumenti Sito


fisica:informatica:201415:esercitazioni:esercitazione12

Differenze

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

Link a questa pagina di confronto

Prossima revisione
Revisione precedente
fisica:informatica:201415:esercitazioni:esercitazione12 [07/04/2015 alle 15:35 (10 anni fa)] – creata Susanna Pelagattifisica:informatica:201415:esercitazioni:esercitazione12 [13/05/2015 alle 09:30 (10 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 ); lista_d_t * tree_to_list ( albero_d_t * root );
 </code> </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
fisica/informatica/201415/esercitazioni/esercitazione12.1428420920.txt.gz · Ultima modifica: 07/04/2015 alle 15:35 (10 anni fa) da Susanna Pelagatti

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki