Definizione di albero generale

Gli alberi generali sono strutture dati collegate, ossia sono insiemi di nodi in cui esistono dei legami fra i nodi. Le strutture dati collegate viste fino a questo momento sono le liste e gli alberi binari, che hanno le seguenti caratteristiche:

liste
ogni nodo ha un successore, tranne l'ultimo della lista che ne ha zero;
alberi binari
ogni nodo ha zero, uno oppure due figli

Possiamo quindi dire che l'unica differenza è che nelle liste ogni nodo ha zero oppure un nodo collegato (successore), mentre negli albero ogni nodo può essere collegato a zero, uno oppure due nodi (figli). La differenza è quindi soltanto nel numero massimo dei figli. Elevando questo numero si possono definire altri tipi di struttura dati: per esempio, se si fissa il numero massimo di successori a tre, otteniamo una struttura dati simile agli alberi binari, in cui ogni nodo ha un numero di figli che va da zero a tre. Questo è un possibile esempio.

Come si vede, la radice ha tre figli, ossia i nodi -2, 4 e 12. A loro volta, -2 ha un solo figlio, 4 non ne ha nessuno, mentre 12 ne ha due. Questo è quindi un albero ternario, dato che ogni nodo ha un numero di figli che non supera il tre.

La rappresentazione in memoria di questi alberi non è difficile. Si tratta infatti di estendere i principi di rappresentazione usati per gli alberi binari. Nel caso della rappresentazione con strutture e puntatori, ogni nodo è ancora rappresentato da una struttura. Soltanto che ora ogni nodo ha tre figli, quindi la struttura deve avere, oltre al campo per il nodo, tre campi per i figli (invece di due come per gli alberi binari). Come al solito, quando un figlio è assente, si può usare il valore NULL invece del puntatore al figlio. La rappresentazione in memoria dell'albero di sopra è quindi la seguente. Si noti che l'albero può comunque essere vuoto, per cui l'intero albero viene rappresentato con un puntatore: se vale NULL, l'albero è vuoto (viceversa, per rappresentare l'albero vuoto usiamo il valore NULL).

Il tipo di dati necessario per ottenere questa rappresentazione è semplicemente una estensione della definizione di tipo usata per gli alberi binari: l'unica cosa che cambia è il fatto che la struttura ha un quarto campo puntatore.

struct NodoAlbero {
  int info;
  struct NodoAlbero *sinistro;
  struct NodoAlbero *centrale;
  struct NodoAlbero *destro;
};

typedef struct NodoAlbero *TipoAlbero;

Le funzioni usate sugli alberi binari si estendono in modo ovvio agli alberi ternari, semplicemente considerando che ogni nodo ha tre sottoalberi invece di due. Per esempio, per stampare tutti i nodi di un albero, basta modificare la funzione di stampa in preordine, aggiungendo la stampa ricorsiva del terzo sottoalbero.

int StampaAlberoTernario(TipoAlbero a) {
  if(a==NULL)
    return;

  printf("%d\n", a->info);

  StampaAlberoTernario(a->sinistro);
  StampaAlberoTernario(a->centrale);
  StampaAlberoTernario(a->destro);
}

Per la rappresentazione usando vettori, partiamo dal concetto di completare l'albero con nodi ``virtuali'', e poi di mettere i nodi dell'albero nel vettore procedendo per livelli (prima la radice, poi i suoi figli, ecc). Nel vettore si mettono anche i nodi che nell'albero non c'erano, ma si segnala nel campo booleano la loro assenza. Nel caso dell'albero della figura di sopra, i livelli sono i seguenti (X indica che il nodo non esiste).

3
-2 4 12
2 X X X X X 8 X 5

Il vettore contiene quindi questi elementi in ordine, in cui la X diventa un elemento del vettore in cui il campo esiste vale FALSE. La definizione del tipo di dato è uguale a quella per gli alberi binari. Dato un nodo, è possibile risalire ai suoi tre figli usando una regola lineare che è facile da derivare.

Alberi generali

Gli alberi generali hanno nodi con un numero arbitrario di figli. Un nodo può quindi avere zero figli, o ne può avere cento.

La differenza fondamentale fra gli alberi generali e gli alberi binari (o ternari) non è tanto il fatto che qui un nodo può avere un maggiore numero di figli, quanto il fatto che questo numero non è limitato a priori. In altre parole: quando si va a scrivere la definizione del tipo, non è noto nessun limite sul numero dei figli.

A causa di questo, le due rappresentazioni classiche degli alberi non si possono più usare, per i seguenti motivi:

vettori
La rappresentazione con vettori richiede un passo preliminare di completamento dell'albero, che consiste nel mettere dei nodi fittizi in tutti i punti in cui un figli non c'è. In altre parole, se un nodo non ha tutti i figli che potrebbe avere (due per gli alberi binari, tre per quelli ternari), aggiungiamo i nodi che mancano. Nel caso degli alberi binari, non esiste un limite al numero di figli; questo passo di completamento non si può quindi fare (richiederebbe di aggiungere un numero infinito di nodi).
strutture
Quando la struttura viene definita, viene specificato il numero di campi che ha. Nel caso degli alberi binari o ternari, si definiva ogni struttura come avente il massimo numero di figli, e poi si usava NULL quando un figli mancava. Nel caso degli alberi generali, il numero di figli non ò limitato: un albero potrebbe avere al massimo un nodo con dieci figli, un altro potrebbe avere un nodo con cento figli, ecc. In ogni caso, il numero massimo di figli non è noto quando viene scritta la definizione di tipo.

Per poter dare una rappresentazione in memoria per gli alberi generali, usiamo la seguente definizione: ogni nodo ha un certo numero di figli, che sono anche essi dei nodi. Per ogni nodo, dobbiamo quindi rappresentare due cose:

  1. il suo valore
  2. l'insieme dei suoi successori

Dal momento che abbiamo due cose da rappresentare, usiamo certamente una struttura per ogni nodo. Il primo campo è il valore del nodo. Come al solito, assumiamo che sia un intero, ma potrebbe essere un tipo qualsiasi.

struct NodoAlbero {
  int info;
  ...            // rappresentazione insieme successori
};

Per quello che riguarda l'insieme dei successori, le sue caratteristiche sono:

  1. è un insieme i cui membri sono di tipo struct NodoAlbero *; in altre parole, è un insieme di indirizzi: ogni indirizzo è l'indirizzo di una struttura NodoAlbero
  2. il numero dei suoi elementi è variabile: può essere vuoto, oppure composto da uno o più elementi;
  3. il numero massimo di elementi non è noto.

L'albero di sopra (che è ternario) si può chiaramente anche rappresentare come albero generale. Abbiamo la seguente rappresentazione parziale: per ogni nodo c'è una struttura; il primo campo contiene l'informazione del nodo; il resto della struttura indica l'insieme dei successori, ed è quindi un insieme di altre strutture (le strutture che rappresentano i nodi figli).

Per quello che riguarda la rappresentazione dell'insieme dei successori di ogni nodo, si tratta di trovare un modo di rappresentare un insieme di dati di cui non si conosce un numero massimo. D'altra parte, conosciamo già due modi per rappresentare insiemi di questo genere: i vettori dinamici e le liste collegate.

Iniziamo quindi con la rappresentazione con vettori dinamici, e vediamo poi la rappresentazione con liste.