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
- Teoria degli alberi binari
- Implementazione di un albero binario
- Teoria della ricorsione
- Algoritmi di base
Documenti
- Articolo: [download id=”5″ format=”2″]