L’ albero è un grafo orientato in cui da ogni nodo possono discendere più figli ma tale che ogni nodo, ad eccezione della radice, abbia un solo padre.
Gli elementi di un albero si chiamano nodi, mentre con ramo si indica un cammino composto da più nodi connessi. Un nodo posto al termine di un ramo è chiamato foglia, mentre il nodo da cui partono i rami è detto radice.
L’albero è considerato un grafo connesso privo di circuiti perché essendo privo di circuiti, garantisce che, partendo dalla radice, si possa raggiungere qualsiasi foglia senza rischiare di finire in un circolo dal quale non si possa uscire.
Nota: Per circuiti si intende un percorso chiuso che permette, partendo da un elemento, di tornare sul medesimo elemento senza ripercorrere lo stesso tratto due volte.
Un albero, a differenza di altre strutture dati quali array, lista, coda, ecc., ha le seguenti caratteristiche:
• Struttura non lineare
• Struttura ricorsiva
• Struttura complessa
Il nodo da cui discende un altro nodo è detto padre. I nodi discendenti da un nodo padre sono detti figli.
Il rapporto padre-figlio dei nodi dell'albero vale per ogni nodo ad eccezione:
• della radice (ha solo figli e non ha padre)
• delle foglie (hanno solo il padre ma non hanno figli)
Una foglia, come già espresso sopra, è un nodo terminale, ovvero un nodo senza figli. Tutti i figli di uno stesso nodo si chiamano fratelli.
Un tipo particolare di albero è
l'albero binario.
Un albero binario è caratterizzato dal fatto che da ogni nodo partono al massimo due rami distinti chiamati sottoalbero sinistro e sottoalbero destro.
Per visitare un albero (cioè visitarne tutti i nodi) esistono tre modi:
•
PREORDINE (Preorder) o ordine anticipato: R - S - D
•
POSTORDINE (Postorder) o ordine posticipato o polacco: S - D - R
•
INORDINE (Inorder) o ordine simmetrico: S - R - D
Dove R sta per la radice, D sta per sottoalbero destro della radice e S sta invece per sottoalbero sinistro della radice.
Il numero massimo di nodi toccati per arrivare ad una foglia prende il nome di profondità dell’albero: nel caso illustrato a destra la profondità è 4.
Si dice anche che l’albero ha quattro livelli, dove per livello si intende l’insieme dei dati che distano un uguale numero di nodi dalla radice.
In generale, se p è la profondità, N il numero massimo di nodi e F il numero massimo di foglie:
N=2P-1 F=2(p-1)
Esempio:
N=26-1 N=64
Un albero avente la profondità strettamente necessaria a contenere i nodi che lo costituiscono si dice bilanciato: ad esempio un albero profondo 6 con 40 nodi è bilanciato, in quanto una profondità inferiore (5) consente di inserire solo 31 nodi e non 40. Viceversa un albero profondo 5 con 14 nodi non è bilanciato,in quanto 14 nodi potrebbero stare in un albero meno profondo.
LA DICHIARAZIONE
Partiamo dal caso più semplice: gli alberi binari. Gli alberi binari possono essere implementati mediante record (strutture, in c) di tre campi: R (il valore del nodo, chiamato R in quanto radice del sotto albero che genera), *D (puntatore al figlio destro e quindi al sotto albero destro generato) e *S (puntatore al figlio sinistro).
Gli alberi non binari invece possono essere implementati, fra i vari modi, mediante record di due campi: la radice (o valore del nodo) e il campo che punta alla lista (o al vettore) dei figli.
Vediamo ora come si dichiara una struttura albero in C.
struct nodo {
// Albero di numeri interi
int DATO;
// Puntatore al sottoalbero destro
struct nodo *DX;
// Puntatore al sottoalbero sinistro
struct nodo *SX;
} NODO;
Questo è il record di tre campi di cui abbiamo parlato all'inizio: DATO, che precedentemente abbiamo chiamato R, *DX e *SX. Per chi non lo ricordasse DATO è la variabile che contiene il valore del nodo.
Ricordo inoltre che il C/C++ è case sensitive e che quindi "NODO" è diverso da "nodo".
Una volta dichiarata la struttura del generico nodo dell'albero, dobbiamo ora dichiarare una variabile che punti a tale struttura.
Tale variabile la chiameremo tree (in inglese tree = albero):
typedef struct nodo* tree;
Questo significa che stiamo definendo un nuovo tipo di dato (typedef) di nome tree che è un puntatore a variabile di tipo nodo.
