Albero è una struttura di dati astratta. Un albero radicato è un albero in cui si distingue un vertice



Scaricare 17.41 Kb.
22.05.2018
Dimensione del file17.41 Kb.

Gli Alberi


Vai a: navigazione, cerca

Un albero è una struttura di dati astratta.

Un albero radicato è un albero in cui si distingue un vertice (chiamato radice) dagli altri vertici.

I vertici in un albero sono chiamati nodi.

Un albero è un tipo di grafo con le seguenti proprietà:



  • non ha mai cammini chiusi al suo interno (grafo aciclico);

  • dati due nodi è sempre possibile trovare un cammino che li unisce (grafo connesso);

  • un nodo non può avere successori (nodi figli), ma, eccetto la radice, per definizione deve sempre avere un solo genitore;

  • alcuni nodi denominati foglie (o nodi terminali) non hanno figli.

Un albero è quindi un esempio di grafo non orientato, connesso e aciclico.


Sia x un nodo di un albero con radice r: qualunque nodo x sull’unico cammino da r a y è chiamato antenato di y e y si dice discendente di x.

Il sottoalbero radicato in x è l’albero indotto dai discendenti di x, radicato in x (ovvero l’albero formato da tutti i nodi discendenti di x, x stesso e relativi archi).

Una radice induce un orientamento; si può cioè predicare l’attributo di predecessore e successore su ogni nodo.

Si rappresenta l’orientamento con frecce.

Se l’ultimo arco di un cammino dalla radice r ad un nodo x è l’arco (x,y) allora x è il padre di y e y è il figlio di x.

Il numero di figli di un nodo x è il grado di x.

Due nodi con lo stesso padre si dicono fratelli.


La radice è l’unico nodo che non ha padre.

Un nodo senza figli si dice nodo esterno o foglia;

Un nodo non foglia è un nodo interno.



Si definisce livello (o profondità) di un albero la lunghezza del cammino che unisce la radice con il nodo stesso.

Un albero ordinato è un albero radicato in cui i figli di ciascun nodo sono ordinati (cioè si estingue il primo figlio, il secondo, etc).

Un alberi si dice posizionale se i figli dei nodi sono etichettati con interi positivi distinti (l’i-esimo figlio di un nodo è assente se nessun figlio è etichettato con l’intero i).

Un albero k-ario è un albero posizionale in cui per ogni nodo tutti i figli con etichetta più grande di k sono assenti.

Un albero k-ario completo è un albero k-ario in cui tutte le foglie hanno la stessa profondità e tutti i nodi interni hanno grado k.

Il numero di foglie di un albero k-ario è:



  • la radice ha k figli a profondità 1

  • ognuno dei figli ha k figli a profondità 2 per un totale di k.k foglie

  • a profondità h si hanno kh foglie.

Il numero di nodi interni di un albero k-ario completo di altezza h è:

1+k+ k2 + … +kh-1 = Σ i=0..h-1 k i = (kh -1)/(k-1)

Un albero binario è un albero particolare, dove ogni nodo, eccetto le foglie, può avere soltanto uno oppure al massimo due figli.

Un albero binario è quindi un albero di grado due.

Ha una struttura definita su un insieme finito di nodi che:

- o non contiene nessun nodo

- oppure è composto da tre insiemi disgiunti di nodi:


        • un nodo radice

        • un albero binario chiamato sottoalbero sinistro

        • un albero binario chiamato sottoalbero destro.

Un albero binario che non contiene nessun nodo è detto albero vuoto o albero nullo (denotato con NIL).

Se il sottoalbero sinistro (destro) non è vuoto allora la sua radice è detta figlio sinistro (destro).



Se un sottoalbero è l’albero nullo si dice che il figlio è assente o mancante.



©astratto.info 2017
invia messaggio

    Pagina principale