Alberi binari


Notice: wpdb::escape è deprecata dalla versione 3.6.0! Utilizzare al suo posto wpdb::prepare() or esc_sql(). in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-includes/functions.php on line 3893

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 113

Notice: Trying to access array offset on value of type bool in /web/htdocs/www.andrea-asta.com/home/portfolio2/wp-content/plugins/download-monitor/classes/downloadable_file.class.php on line 114

Una delle strutture fondamentali di tutta la programmazione è l’albero. Esiste un particolare tipo di albero, detto binario, che per le sue particolari proprietà si presta molto bene ad alcuni tipi di operazioni, quali l’analisi di espressioni matematiche o la ricerca dicotomica.
Particolari tipi di alberi binari sono utilizzati come nuovi tipi di strutture dati, particolarmente ottimizzati per operazioni di ricerca o ordinamento: è il caso degli heap, degli alberi di ricerca e così via.
In questo fascicolo analizzeremo tutti gli algoritmi basilari per la gestione di un albero binario, partendo dalle definizioni e ragionando su ogni algoritmo.
Il linguaggio scelto per la stesura dei programmi è il C++, anche se in realtà saranno utilizzati concetti del tutto compatibili con il C. E’ da sottolineare, tuttavia, che il codice è compilabile in ANSI C++, per la compilazione in C saranno necessarie alcune modifiche. Quindi quando vedete scritto [C/C++] non significa che il codice è compilabile in C, ma solo che la sintassi utilizzata non prevede elementi proprietari del C++, quali classi, template, reference e così via.
Naturalmente questo fascicolo è dedicato esclusivamente alla parte relativa all’albero binario come struttura dati, quindi tutti i discorsi relativi alla sintassi del linguaggio adottato sono dati per scontati. In particolare, è bene avere buona padronanza delle strutture, dei puntatori e delle funzioni ricorsive, anche se quest’ultimo punto è presente una piccola digressione.

Sommario

  1. Teoria degli alberi binari
  2. Implementazione di un albero binario
  3. Teoria della ricorsione
  4. Algoritmi di base

Documenti