Dal momento che ogni nodo di un albero viene rappresentato come una struttura, il problema da risolvere è quello di specificare i figli di un nodo. Dal momento che i figli sono nodi, si tratta quindi di rappresentare un insieme di indirizzi di strutture. Un esempio è qui sotto.
Ci serve un modo per dire che i successori del nodo 3 sono le strutture che contengono i nodi -2, 4 e 12, ossia dobbiamo rappresentare l'insieme composto dall'indirizzo di queste tre strutture.
Il metodo che vediamo in questa pagina è quello che usa vettori dinamici. Per semplicità, consideriamo il caso più semplice, ossia quello di vettore completamente utilizzato. In altre parole, un vettore dinamico di questo tipo è caratterizzato da un puntatore e da un intero che dice la dimensione del vettore, che coincide con il numero di elemente correntemente usati del vettore. Prima di vedere quale è esattamente la definizione di tipo, consideriamo come viene rappresentato in questo modo l'albero di sopra.
Cominciamo con la radice. Abbiamo una struttura che contiene il valore del nodo (3), e poi un vettore dinamico i cui elementi sono gli indirizzi delle strutture che contengono i figli di 3. Ogni vettore dinamico viene rappresentato da un numero di elementi e dal puntatore al vettore stesso. Dato che la radice ha tre figli, il numero di elementi è 3, e il puntatore contiene l'indirizzo di un vettore di tre elementi. Ogni elemento di questo vettore contiene l'indirizzo di una delle strutture che sono i figli della radice. La struttura che contiene la radice è quindi composta di tre campi, di cui il secondo e il terzo complessivamente indicano quanti e quali sono i figli del nodo.
La stessa rappresentazione vale anche per i figli: per ogni figlio, ho una struttura che contiene il valore del nodo e altri due campi che indicano i successori. Come prima, questi due campi contengono il numero di successori e il puntatore alla zona di memoria dove si trova il vettore.
Questa figura si ottiene considerando che il nodo -2 ha un unico figlio, quindi per i suoi successori serve un vettore composto di un unico elemento; per il nodo 12, dal fatto che ha due figli si ottiene che serve un vettore dinamico di due elementi. I nodi 2, 8 e 5 non hanno figli, quindi basta mettere 0 nel campo che indica la dimensione del vettore (che è infatti anche il numero dei figli).
Lo schema finale sembra piuttosto complesso, ma si ottiene invece molto facilmente:
Abbiamo quindi capito come viene rappresentato in memoria l'albero. Ci serve ora la dichiarazione dei tipi. La struttura è composta di tre campi, i cui primi due elementi sono interi, e il terzo è un puntatore:
struct NodoAlbero {
int info;
int numfigli;
??? figli;
};
L'unica cosa che ci manca è il tipo del puntatore. Questo si può ottenere in questo modo: il puntatore contiene un indirizzo; il suo tipo è fatto dal tipo del dato che si trova a quell'indirizzo seguito da *. Per esempio, se ho una variabile che contiene l'indirizzo di una zona di memoria in cui ho un int, la variabile deve essere di tipo int *.
Nel nostro caso, il terzo elemento della struttura è un puntatore a una zona di memoria che contiene a sua volta un puntatore. Più precisamente, questo è un puntatore a una struct NodoAlbero. Quindi, gli elementi del vettore sono di tipo struct NodoAlbero *, e il puntatore che sta dentro la struttura è di tipo struct NodoAlbero **. Si può stabilire questo un passo per volta. Primo, la struttura è di tipo struct NodoAlbero.
Dato la struttura è di tipo struct NodoAlbero, e il vettore contiene indirizzi di queste strutture, ogni elemento del vettore è di tipo struct NodoAlbero *:
A sua volta, nella struttura c'è l'indirizzo del vettore. Il tipo di questo campo è dato semplicemente dal tipo dell'elemento del vettore a cui va aggiunto *. Questo perchè il terzo elemento della struttura è un puntatore, e il suo tipo è quello dell'oggetto puntato a cui si aggiunge *.
Abbiamo quindi la seguente dichiarazione di dati:
struct NodoAlbero {
int info;
int numfigli;
struct NodoAlbero **figli;
};
Si può stabilire il tipo del terzo elemento anche facendo questo ragionamento alternativo: si tratta di rappresentare un vettore dinamico, e noi sappiamo come si fa nel caso dei vettori di intero. Stabiliamo quindi i tipi nel caso di vettori di interi, e poi facciamo le modifiche che servono per il caso degli alberi. Per rappresentare un vettore dinamico di interi, ci servono due variabili:
int *p; // puntatore alla zona di memoria
// che contiene gli interi
int dim; // numero di elementi del vettore
Si noti che il secondo dato è sempre un intero, dato che è la dimensione del vettore. La prima variabile p dipende invece dal tipo degli elementi del vettore. Per un vettore di interi, p è di tipo int *. Se vogliamo rappresentare un vettore di reali, avremmo float *. Per vettore di caratteri, avremmo usato char *. In generale, se vogliamo rappresentare un vettore i cui elementi sono di tipo TipoElemento, allora la variabile deve essere di tipo TipoElemento *. Questo è dovuto al fatto che una variabile puntatore a un tipo contiene l'indirizzo di una zona di memoria dove sono memorizzati uno o più dati di quel tipo.
Nel nostro caso, gli elementi del vettore non sono di tipo intero. Come si è detto prima, devo rappresentare un insieme di nodi. Ogni nodo lo rappresento come un puntatore a una struttura. Quindi, ogni figlio è rappresentato dall'indirizzo di una struttura struct NodoAlbero. Gli elementi del vettore sono quindi di tipo struct NodoAlbero *. La variabile p deve quindi essere di tipo struct NodoAlbero **p. Ripetiamo:
Questo ragionamento alternativo permette ugualmente di arrivare alla stessa dichiarazione di dati che si ottiene guardando la figura e mettendo uno * ogni volta che si risale una freccia.