Presenza in un albero

Rivediamo ora l'esercizio di verifica se un albero contiene un elemento, in cui però l'albero viene rappresentato usando le liste invece dei vettori.

La prima versione dell'algoritmo è sempre la stessa: se l'albero è vuoto, non contiene l'elemento; se la radice contiene l'elemento, si ritorna TRUE; altrimenti, si fa la verifica su tutti i sottoalberi, ritornando TRUE se almeno una di queste verifiche ritorna TRUE.

L'unica differenza rispetto al caso della verifica di presenza con alberi rappresentati con liste è che ora la scansione dei figli di un nodo, che si usa per fare la ricerca sui sottoalberi, va fatta come la scansione di una lista invece della scansione di un vettore. In altre parole, per fare una stessa operazione su tutti i figli di un albero a, il ciclo viene fatto come la scansione della lista a->figli:

l=a->figli;

while(l!=NULL) {
  // operazione sul figlio, che e' l->figlio
  l=l->next;
}

Nel nostro caso, occorre fare la chiamata ricorsiva sul figlio l->figlio, ritornando TRUE se la chiamata ritorna TRUE. Se si arriva alla fine del ciclo, vuol dire che tutte le chiamate ricorsive hanno ritornato FALSE, e quindi l'elemento non si trova nell'albero.

int Presenza(TipoAlbero a, int e) {
  TipoLista l;

  if(a==NULL)
    return FALSE;

  if(a->info==e)
    return TRUE;

  l=a->figli;
  while(l!=NULL) {
    if(Presenza(l->figlio, e))
      return TRUE;

    l=l->next;
  }

  return FALSE;
}

Si noti che l'algoritmo coincide con quello della rappresentazione con liste, e l'unica cosa che cambia è il modo in cui si fa la scansione dei figli di un nodo. Per il resto, la funzione è la stessa.