Impara a Programmare, Lezione 3: Grafi ed Alberi

Benvenuti in questa terza lezione della serie “Scuola Serale di Italian Geek“.

Queste brevi lezioni sono state progettate in modo tale da risultare volutamente sintetiche, dunque, per approfondimenti contattateci usando i commenti a fine articolo. Il codice presente nelle lezioni e’ funzionante ed e’ stato testato su compilatore gcc version 3.4.6 20060404 (Red Hat 3.4.6-9).

Grafi ed Alberi in linguaggio C

Grafi ed Alberi sono strutture dati cosidette di tipo “non lineare”

Si dicono in generale Grafi:

Insieme di nodi
Connessi da relazioni binarie (archi orientati da un nodo ad un altro nodo)

I Grafi possiedono alcune caratteristiche importanti quali il grado di ingresso e uscita di un nodo, e la dimensione. Vediamo nel dettaglio in cosa consistono:

Grado di ingresso di un nodo:

numero di archi che entrano nel nodo

Grado di uscita di un nodo:

numero di archi che partono dal nodo

La dimensione di un grafo è praticamente data dal numero di dimensioni che servono per poterlo “disegnare” senza incroci:

Le molecole del DNA formano un grafo tridimensionale
Le liste sono casi monodimensionali di grafi (ogni nodo ha un
arco di ingresso e uno di uscita)

Le strutture di relazione tra elementi si rappresentano come grafi.

Alberi

Definizione 1

Un albero è un insieme finito di nodi e archi orientati. Ogni arco collega il nodo padre ad un nodo “figlio” e :

Ogni nodo ha esattamente un padre (grado di ingresso + 1)
Ogni nodo ha al più due figli (grado di uscita <= 2).
Il nodo radice non ha padre (grado di ingresso = 0)

Definizione 2 (“ricorsiva”)

Albero binario è un insieme finito di nodi e può essere:

insieme vuoto oppure
nodo radice + due alberi binari disgiunti, detti rispettivamente sottoalbero sinistro e sottoalbero destro

Si veda come esempio la figura 1 seguente:

Figura 1: Esempio di Albero Binario

Terminologia relativa agli alberi

livello di un nodo: distanza dalla radice, espressa come numero di archi di cui è composto il cammino dalla radice al nodo; la radice è a livello 0;

profondità (o altezza) dell’albero: massimo livello dei nodi dell’albero;

foglia: nodo senza figli;

predecessore: relazione strutturale, ottenibile applicando la proprietà transitiva alla relazione padre-figlio.

Il massimo numero di nodi a livello i (i ≥ 0) è 2ⁱ , come si può verificare per induzione: 2⁰=1, se il massimo numero di nodi a livello i è 2ⁱ, poichè ogni nodo al livello i può avere al più due figli, al livello i+1 il massimo numero di nodi è 2*2ⁱ=2ⁱ⁺¹.

Il massimo numero complessivo di nodi in un albero di profondità k è 2⁰ + 2¹ + … + 2^k = 2^k+1-1.

Visite di un albero

Visitare un grafo, in genere significa: percorrere tutti i suoi nodi una volta e una sola o piú, in generale, visitare un insieme specifico di nodi…

Si visita un albero per visualizzare, elaborare, modificare il contenuto informativo dei nodi.

La visita di un albero può seguire uno delle seguenti modalità base:

preordine: la visita della radice è seguita dalla visita dei sottoalberi
postordine: la visita dei sottoalberi è seguita dalla visita della radice
ordine centrale (simmetrica): la visita della radice è intermedia alle visite dei sottoalberi;

La definizione ricorsiva di albero suggerisce la realizzazione delle varie operazioni con programmazione ricorsiva: le posizioni dei figli di un nodo possono essere trattate come posizioni di radici di alberi.

void PreOrdine(Posiz N, AlbBin T){
 if <albero non vuoto>
  {
    Visita(N); /* A */
    PreOrdine(<figlio sinistro>, T): /* B */
    PreOrdine(<figlio destro>, T); /* C */
  }
} /* end PreOrdine */

Le altre modalità di visita si ottengono semplicemente modificando l’ordine delle operazioni nel corpo della procedura:

B,C,A per il post-ordine e
B,A,C per l’ordine centrale.

Di seguito i link per scaricare il pdf della lezione ed il codice sorgente di esempio.

Download

Lezione 3: Grafi ed Alberi
alberi.c

La lezione si conclude qui, per qualsiasi chiarimento potete lasciare un commento in fondo alla pagina.L’indice delle lezioni si trova qui.La lezione precedente è stata Algoritmi di ordinamento: Insertion Sort e Counting Sort.

Il prossimo appuntamento e’ per Venerdi’ 11 Novembre 2011, la lezione avra’ per argomento gli Alberi rosso-neri.

Alla prossima!

Puoi seguire Massimo Orazio Spata, l’autore di questo post, su Twitter.

Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo:info@italiangeek.com