Le Foreste e gli Alberi

Un grafo non orientato e senza cicli è detto foresta:

algo_str8

Se questo grafo è anche connesso allora viene detto albero:

algo_str9

Definiamo un albero come una coppia T=(V,E) .

Alberi con radice

Gli alberi con radice sono particolari alberi formati da una coppia (T,r) , dove T è un albero e r un suo vertice detto radice. Mostriamo ad esempio il medesimo grafo in cui è stato evidenziato un vertice radice.

algo_str11

Un albero radicato può essere facilmente rappresentato mendiate una lista, oppure mediante una tabella Padre – Nodo oppure Nodo – Figlio:

Padre Nodo
1 (radice)
1 2
1 3
2 4
Nodo Figlio
1 (radice) 2
1 (radice) 3
2 4

Utilizzando questa notazione chiameremo il nodo iniziale “seme” o “radice”, i nodi intermedi “interni” e i nodi finali “foglie”. Inoltre potremmo utilizzare termini come: “discendente”, “successore”, “antenato”, “predecessore”. Definiremo “altezza” di un nodo x la lunghezza del più lungo cammino percorribile da x a una foglia, e “profondità” la lunghezza del cammino dalla radice a x .

Alberi ordinati

Un albero ordinato (o piano) è un albero in cui i figli di ogni vertice sono totalmente ordinati. I seguenti alberi ad esempio, coincidono come alberi radicati, ma differiscono come alberi ordinati.

algo_str12 algo_str13

Consideriamo le strategie utilizzate per l’attraversamento degli alberi ordinati, ovvero per la visita di tutti i nodi di un albero in un qualche ordine. Due metodi possibili per svolgere queste operazione sono l’attraversamento in pre-ordine o in post-ordine (in ordine anticipato o posticipato).

Pre-ordine Post-ordine
algo_str14 algo_str15

Algoritmi di visita di un albero ordinato T in pre-ordine:

  • Se T è costituito da un solo nodo r , allora visita r ;
  • Altrimenti se T = (r, T_{1}, T_{2}, \ldots, T_{n}) allora:
    • Visito la radice r , di T_{i} ;
    • Attraverso in pre-ordine gli alberi T_{1}, T_{2}, \ldots, T_{n} .

Algoritmo di visita di un albero ordinato T in post-ordine:

  • Se T è costituito da un solo nodo r , allora visita r ;
  • Altrimenti se T = (r, T_{1}, T_{2}, \ldots, T_{n}) allora:
    • Attraverso in post-ordine gli alberi T_{1}, T_{2}, \ldots, T_{n} .
    • Visito la radice r , di T_{i} ;

Vedremo in seguito sviluppare questo tipo di algoritmi mediante la Ricorsione.

Alberi binari

Un albero binario è un albero radicato in cui ogni nodo interno ha al più due figli, ogni figlio viene distinto come figlio destro o figlio sinistro. L’altezza di un albero binario bilanciato, ovvero il percorso massimo tra la sua radice e la sua foglia è uguale a log_{2}(k) , con k uguale al numero delle foglie.

algo_str16

L’altezza di un albero binario non bilanciato può invece oscillare tra il valore minimo di log_{2}(k) , fino al valore massimo di k-1 , che occorre quando l’albero è totalmente sbilanciato. Un albero è totalmente sbilanciato quando è rappresentato da un vettore.

log_{2}k \le h \le k-1

L’attraversamento di un albero binario viene detto in ordine simmetrico, esso è così sviluppato.
Sia r la radice dell’albero binario:

  1. Se r ha figlio sinistro allora attraversa il sotto-albero sinistro di r ;
  2. Visita r ;
  3. Se r ha figlio destro allora attraversa il sotto-albero destro di r .

Gli alberi in Linguaggio C

Di seguito presentiamo l’implementazione in linguaggio C di un piccolo programma destinato alla gestione degli alberi. Come si può vedere dal codice del programma, gli alberi necessitano di una struttura di memorizzazione molto simile a quella dei grafi.

struct tree {
  int id;
  int value;
  int nA;
  struct tree **ar;
};

Ricordiamo inoltre che gli alberi sono di natura non orientati, durante la creazione di un albero sarà quindi necessario specificare esplicitamente l’esistenza di due archi, da un generico nodo A ad un generico nodo B e dallo stesso generico nodo B al precedente nodo A.

Gli alberi in Linguaggio C, programma completo

Per completezza allego questo programma completo per la gestione di un semplice albero in linguaggio C.

Nota: Nel programma sono omessi i controlli sugli indici e sui tipi, si presuppone che l’utente inserisca sempre dati corretti. Per il programma completo fare riferimento a questo link.