Esercizio di esame del 26-9-2000

Testo

Sia A il puntatore alla radice di un albero i cui nodi contengono valori interi. Si assuma che l'albero sia già presente in memoria. Si scriva una funzione che riceve come parametro questo puntatore, restituisce una lista dei valori interi contenuti nell'albero, nello stesso ordine in cui si trovano visitando l'albero in preordine. In altre parole, stampando la lista si devono ottenere gli stessi elementi, nello stesso ordine, che si ottengono visitando l'albero in preordine.

Ad esempio, dato l'albero seguente:

La funzione deve restituire la lista:

(56 93 0 80 24 49)

Il programma 26-9-2000-driver.c contiene le funzioni di lettura di albero da file, di stampa di alberi e liste. Per provare le funzioni, si possono semplicemente scrivere all'interno di questo programma, subito prima di main.

Di serguito vengono dati dei file da usare per il test del programma (tree3.txt è l'albero vuoto). La soluzione è fatta di due righe: la prima è la stampa dell'albero letto, la seconda è la stampa della lista che si ottiene eseguendo la funzione.

tree1.txt    soluzione
tree10.txt    soluzione
tree11.txt    soluzione
tree2.txt    soluzione
tree3.txt    soluzione
tree4.txt    soluzione
tree5.txt    soluzione
tree6.txt    soluzione
tree7.txt    soluzione
tree8.txt    soluzione
tree9.txt    soluzione

Soluzione quadratica

La soluzione più semplice è quella di fare la visita dell'albero in preordine, aggiungendo ogni elemento incontrato in coda alla lista. In altre parole, l'algoritmo è il seguente: faccio una visita in preordine dell'albero; la analisi di un nodo non è la stampa del valore, ma la sua aggiunta in coda alla lista.

È chiaro che la aggiunta in coda alla lista si puù realizzare come una funzione. Si tratta in effetti di una funzione che è stata vista a lezione, e che si trova spiegata nel dettaglio in una delle pagine web del corso (inserimento in coda a una lista). Riportiamo una possibile implementazione di questa funzione qui sotto.

void InserisciCodaLista(TipoLista *pl, int e) {
  TipoLista s;

		/* caso di lista vuota */
  if(*pl==NULL) {
    *pl=malloc(sizeof(struct NodoLista));
    (*pl)->val=e;
    (*pl)->next=NULL;
    return;
  }

		/* lista con almeno un elemento: scansione fino alla fine */
  s=*pl;
  while(s->next!=NULL)
    s=s->next;


		/* crea un nuovo elemento in coda */
  s->next=malloc(sizeof(struct NodoLista));
  s=s->next;
  s->val=e;
  s->next=NULL;
}

La stessa funzione si può anche realizzare in modo ricorsivo, oppure usando il record generatore. Sono tre alternative valide. Si noti che scrivere per esteso il codice della funzione fa parte della soluzione del compito. In altre parole, lo svolgimento dell'esercizio deve contenere la implementazione di tutte le funzioni, anche quelle che sono state viste a lezione.

La lista viene realizzata mediante una funzione di visita, in cui l'operazione di analisi non è la stampa del valore, ma la sua aggiunta in coda alla lista. La funzione ha quindi due parametri: l'albero e la lista in cui l'elemento va aggiunto. La lista va chiaramente passata per indirizzo, dal momento che la aggiunta in coda può modificare il puntatore iniziale.

La funzione si realizza quindi mettendo in coda la radice, e poi visitando i due sottoalberi. Occorre naturalmente tenere conto che l'albero può essere vuoto (caso base della ricorsione): in questo caso, non c'è niente da aggiungere, per cui la funzione termina senza fare modifiche alla lista.

void VisitaInCoda(TipoAlbero a, TipoLista *pl) {
  if(a==NULL)
    return;

  InserisciCodaLista(pl, a->radice);
  VisitaInCoda(a->sinistro, pl);
  VisitaInCoda(a->destro, pl);
}

La funzione che occorre realizzare deve prendere un albero e restituire una lista, per cui la funzione di sopra non va bene. La funzione che risolve il problema, d'altra parte, deve fare solo due cose: inizializzare la lista a NULL, e lanciare la funzione di visita. Si noti che la inizializzazione è necessaria, dal momento che la funzione di visita non fa mai questa inizializzazione (infatti, si limita solo ad aggiungere in coda alla lista).

TipoLista ListaPreordineCoda(TipoAlbero a) {
  TipoLista l;

  l=NULL;

  VisitaInCoda(a, &l);

  return l;
}

Soluzione lineare

Il programma di sopra è quadratico (numero di istruzioni eseguite proporzinale al quadrato del numero di nodi dell'albero). Il problema è che, ogni volta che faccio un inserimento in coda, devo fare la scansione di tutta la lista solo per trovare l'indirizzo dell'ultima struttura. È possibile evitare queste scansioni: nella corso della visita dell'albero mi ricordo l'indirizzo dell'ultima struttura della lista, e aggiungo l'elemento a partire da questo punto. Si noti che la funzione di visita non ha bisogno del puntatore iniziale della lista: infatti, per aggiungere in coda basta l'indirizzo dell'ultima struttura.

La funzione di visita crea quindi un nuovo elemento supponendo di sapere l'indirizzo dell'ultima struttura della lista. Dopo aver fatto la aggiunta in coda, si deve spostare il puntatore (infatti, la aggiunta in coda ha creato un nuovo ultimo elemento della lista). Si continua poi la visita sul sottoalbero sinistro e sul destro.

Si noti che il puntatore all'ultima struttura va passato per indirizzo. Infatti, se il sottoalbero sinistro non è vuoto, allora la prima chiamata ricorsiva aggiunge elementi in coda alla lista, per cui il puntatore all'ultimo elemento deve cambiare (punta al nuovo ultimo elemento della lista). Il programma principale deve vedere questa modifica? Chiaramente sí, dato che deve passare questo valore alla seconda chiamata ricorsiva. Quindi, il puntatore va passato per indirizzo.

void VisitaAggiungi(TipoAlbero a, TipoLista *ps) {
  if(a==NULL)
    return;

  (*ps)->next=malloc(sizeof(struct NodoLista));
  (*ps)=(*ps)->next;		/* la lista ha un nuovo ultimo elemento */
  (*ps)->val=a->radice;
  (*ps)->next=NULL;

  VisitaAggiungi(a->sinistro, ps);
  VisitaAggiungi(a->destro, ps);
}

La funzione di sopra aggiunge la radice in coda alla lista, e poi fa le chiamate ricorsive. Occorre tenere presente che l'aggiunta in coda, cosí come è stata fatta in questa funzione, è corretta solo se la lista contiene già almeno un elemento. La funzione finale deve essere scritta in modo tale che la chiamata alla funzione di visita passi sempre una lista che contiene già almeno un elemento. Abbiamo quindi due soluzioni:

  1. si usa un elemento generatore;
  2. si mette la radice dell'albero nella lista, e poi si fanno le due chiamate alla funzione.

Qui sotto facciamo vedere la funzione che si ottiene implementando la seconda strategia. La funzione principale crea una lista con un elemento, che è quello che si trova nella radice dell'albero. A questo punto, occorre visitare in preordine i due sottoalberi, per cui si fanno due chiamate alla funzione di visita (una sul sottoalbero sinistro e una sul destro).

TipoLista VisitaLista(TipoAlbero a) {
  TipoLista l, s;

  if(a==NULL)
    return NULL;

  l=malloc(sizeof(struct NodoLista));
  l->val=a->radice;
  l->next=NULL;

  s=l;
  VisitaAggiungi(a->sinistro, &s);
  VisitaAggiungi(a->destro, &s);

  return l;
}

Esistono ovviamente della soluzioni alternative: una è quella di creare un elemento fittizio nella lista (elemento generatore), fare la visita a partire dalla radice, e poi eliminare il primo elemento dalla lista. Un'altra possibile soluzione è quella di modificare la funzione di visita in modo da renderla corretta anche quando la lista non è vuota (questo chiaramente è possibile solo se la funzione riceve anche il puntatore iniziale della lista).