1. Definizione di Albero



Scaricare 142.5 Kb.
Pagina1/11
21.12.2019
Dimensione del file142.5 Kb.
  1   2   3   4   5   6   7   8   9   10   11

Prof.S.Cavalieri a.a.2009/2010

Struttura Dati Astratta ABR



La Struttura Dati Astratta Albero Binario di Ricerca (ABR)

1.Definizione di Albero


In informatica, un albero è, per definizione, un insieme di elementi chiamati nodi e da relazioni tra i nodi stessi. Per un albero, devono valere le seguenti proprietà:

  1. Un albero che non contiene nodi si dice vuoto.

  2. Se l’albero non è vuoto, tra tutti i nodi dell'albero, solo uno, prende il nome di "radice"; tale elemento deve esistere necessariamente e deve essere unico.

  3. Tra tutti i nodi dell'albero esiste una particolare relazione tale che: preso un qualunque nodo dell'albero tranne la radice, per tale nodo è possibile individuare sempre uno ed un solo nodo dell'albero, che viene denominato "genitore"; ovviamente esisteranno alcuni nodi per i quali il nodo genitore è rappresentato dalla radice dell'albero stesso. Nel seguito, tutti i nodi posti in relazione con un nodo genitore verranno chiamati nodi "figli".

  4. L'albero è connesso, nel senso che preso un qualunque nodo tranne la radice e procedendo verso il suo genitore, e poi verso il genitore del genitore e così via, si arriva sempre alla radice.

Per una maggiore comprensione, un albero può essere rappresentato graficamente nella seguente maniera.

Come si vede, ogni nodo è stato rappresentato da un cerchio ed etichettato in modo univoco. E' possibile distinguere la radice, e le relazioni tra i nodi sono rappresentate da una linea. Tali relazioni collegano i "figli" con uno ed un solo "genitore". Ad esempio n5, n6 e n7 hanno come genitore il nodo n1. Si può verificare che l'albero in figura è connesso, mentre il seguente insieme di nodi, anche se molto simile, non risulta connesso, e, dunque, non può definirsi albero.



Come si vede, infatti, considerando i nodi n8 o n9 e procedendo verso i nodi genitori non è possibile pervenire alla radice dell'albero.





Condividi con i tuoi amici:
  1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale