Albero n-ario
# Albero n-ario

In informatica un albero n-ario è un albero i cui nodi hanno, al più, grado n; per albero si intende un grafo non orientato, connesso ed aciclico. È una struttura dati ampiamente utilizzata in campo informatico.

Come da caratteri comuni degli alberi, esso ha un nodo chiamato radice (o root), che può avere un numero di figli in numero pari o inferiore all'arietà dell'albero. I nodi senza figli vengono detti foglie e tutti gli altri sono chiamati nodi interni. Gli n nodi figli dello stesso genitore vengono chiamati fratelli. Una sequenza di nodi e rami tali che ciascun nodo (tranne l'ultimo) sia padre del successivo si chiama cammino. Il numero di archi (o rami) coinvolti in un cammino è detta lunghezza del cammino. In generale, un cammino con K nodi ha K-1 archi, ossia ha lunghezza K-1. La lunghezza del più lungo cammino da un nodo ad una foglia si chiama altezza del nodo; tutte le foglie hanno infatti altezza 0, e i genitori delle foglie, altezza 1. Se T è un albero e X è un suo nodo, l'insieme dei nodi di T contenente X e tutti i suoi discendenti si chiama sotto-albero di T. X è detta radice del sotto-albero.

## Implementazione degli alberi n-ari

Tramite l'utilizzo di strutture di programmazione generiche, è possibile dare delle diverse implementazioni agli alberi n-ari. Una delle più diffuse per questa struttura dati, attuabile utilizzando uno dei tanti linguaggi di programmazione, è l'implementazione dinamica primo figlio-fratello, conveniente perché prescinde dal numero di figli che può avere un nodo. In questa implementazione ogni nodo ha sempre e solo due riferimenti:

* al primo figlio (a sinistra)
* al primo fratello (a destra)

A seguire, degli esempi di queste implementazioni.

## Implementazione primo figlio-fratello

Ecco il codice sorgente Java di una implementazione con visite preorder e postorder:

## Implementazione con lista collegata

Di seguito, un'altra implementazione di alberi n-ari molto diffusa, stavolta sfruttando delle liste concatenate. Il linguaggio di programmazione scelto per questa implementazione è il Java.

