L’albero è un tipo astratto di dato utilizzato per rappresentare relazioni gerarchiche tra oggetti.
Un albero binario può essere facilmente rappresentato in modo ricorsivo. Infatti, un albero
Per rappresentare un albero binario si puo usare la seguente struttura ricorsiva:
Per controllare se un nodo è vuoto possiamo usare la seguente funzione (vedi figura):
Per sapere il valore di un nodo possiamo usare la seguente funzione che ritorna 0 se l’albero è vuoto, altrimenti memorizza nella variabile val il valore del nodo
Per avere il puntatore al figlio sinistro (destro) di un nodo (vedi figura):
Per costruire un nodo (vedi figura):
Oltre alle operazioni primitive, si definiscono delle operazioni di visita ovvero di analisi dei nodi di un albero in deteminato ordine.
Di seguito analizziamo le seguenti visite di un albero:
Nella visita in Preordine, se l’albero non è vuoto:
Nella visita in preordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 1, 2, 3, 4, 5, 6, 7
Nella visita in ordine, se l’albero non è vuoto:
Nella visita in ordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 3, 2, 4, 1, 6, 5, 7
Nella visita in postordine, se l’albero non è vuoto:
Nella visita in ordine del precedente albero i nodi verrebbero visitati nel seguente ordine: 3, 4, 2, 6, 7, 5, 1
Un albero binario di ricerca è un albero binario in cui per ogni nodo dell’albero N tutti i nodi del sottoalbero sinistro di N hanno un valore minore o uguale di quello di N e tutti i nodi del sottoalbero destro hanno un valore maggiore di quello del nodo N.
Il vantaggio principale di tale organizzazione è nella ricerca.
Ogni volta che bisogna ricercare un elemento, il confronto del valore di un nodo dell’albero permette di eliminare dalla fase di ricerca o il sottoalbero corrente di destra o quello di sinistra.
Per trovare un numero R si procede nel seguente modo:
La ricerca può essere realizzata mediante una funzione ricorsiva che nei casi 3 e 4 invoca se stessa.
Se il sottoalbero sinistro è vuoto, il minimo è la radice.
Altrimenti il minimo è da cercare nel sottoalbero sinistro.
Nella cancellazione di un elemento el da un albero bisogna distinguere i seguenti casi:
Albero vuoto: non viene realizzata alcuna cancellazione;
elimina(radice->sinistro,el);
elimina(radice->destro,el);
La radice è una foglia:
Se il sottoalbero destro è vuoto:
Viene eliminato il nodo el (7).
Il sottoalbero destro e sinistro del nodo el sono non vuoti:
Il codice precedente, non cancella efficacemente un nodo perchè all’atto della cancellazione “free(radice); radice=NULL;” deallochiamo effettivamente la memoria per il nodo da cancellare, ma il nodo padre di quest’ultimo continuerà a puntare ad una locazione di memoria reale, che non è NULL.
La funzione non è corretta perchè porta troppo avanti il puntatore, per cui non abbiamo più la possibilità di modificare il campo destro o sinistro del nodo padre.
Una soluzione è forzare la modifica del nodo padre utilizzando una variabile di comodo.
Un’altra soluzione è quella di utilizzare il metodo del puntatore a puntatore.
Di seguito mostriamo entrambe le soluzioni.
1. Introduzione al Corso - Il Linguaggio C (I parte)
2. Linguaggio C – Seconda Parte
3. Ordinamento, Ricorsione e Code di Priorità
4. Esercitazione su Ricorsione e Code di Priorità
5. Stack e Code
6. Esercitazione di Laboratorio su Stack e Code
7. Implementazioni di Liste puntate
8. Esercitazione di laboratorio su Liste Puntate Semplici
9. Implementazioni di Liste Doppiamente Puntate e Circolari
10. Esercitazione di laboratorio su Liste Doppiamente puntate
12. Esercitazione di laboratorio su Alberi Binari di Ricerca
13. Alberi Binari di Ricerca. Cancellazione di un nodo
14. Esercizio di Laboratorio. Gioco su alberi
15. Grafi: Implementazione ed operazioni di base
16. Esercitazione di laboratorio: Implementazione operazioni di bas...
17. Grafi: Inserimento e Cancellazione di un nodo. Visite in ampiez...
18. Esercitazione di laboratorio: Problema del venditore Prima part...
19. Componenti fortemente connesse e alberi minimi di copertura
20. Esercitazione di laboratorio: Problema del venditore Seconda pa...