Diagrammi di allocazione di alberi

Fase preparatoria - 20.04.2015



Albero generico di 10 nodi

Disegno 1

Diagramma di un albero ternario di altezza 3 con 10 nodi.



Tabella di rappresentazione dell’allocazione sequenziale statica dell’albero

Disegno 2

Nell'allocazione statica sequenziale di un albero, il criterio di attraversamento di esso è prestabilito e l'albero viene memorizzato in una struttura sequenziale (ad es. un array statico). La tabella mostrata sopra mostra l'array contenente la rappresentazione dell'albero al disegno 1.

Nella colonna centrale viene scritto l'indice dall'array nella cui posizione si trova il padre.



Allocazione dinamica non sequenziale (liste di figli) dell’albero

Disegno 3

Nell'allocazione dinamica non sequenziale (liste di figli) ogni nodo dell'albero è costituito dal campo informativo (contornato in nero nel disegno) e da un secondo campo (contornato in verde) che è il puntatore alla lista dei figli: una lista concatenata di tanti puntatori quanti sono i figli del nodo.



Allocazione dinamica non sequenziale (padre-primo figlio-fratello) dell'albero

Disegno 4

Nell'allocazione dinamica non sequenziale (padre-primo figlio-fratello) ogni nodo è costituito da 3 campi:
   1- puntatore all'informazione del nodo (contornato in nero nel disegno);
  2- puntatore al primo figlio (contornato in giallo)
  3- puntatore al primo fratello (contornato in verde)



Albero binario di 9 nodi

Disegno 5

Diagramma di un albero binario.



Allocazione dell'albero binario utilizzando le liste multiple (senza link al padre)

Disegno 6

Nell'allocazione di un albero binario si usano strutture dati con nodi a tre campi:
  1- puntatore al sottoalbero sinistro (contornato in giallo nel disegno)
  2- puntatore ai dati del nodo (contornato in nero)
  3- puntatore al sottoalbero destro (contornato in verde)

Comment Stream