Presenza in un albero

Esercizio: scrivere una funzione che verifica se un albero contiene un certo elemento. Si assuma che i nodi siano interi: il prototipo è quindi:

int Presenza(TipoAlbero, int);

Soluzione: si tratta di implementare la stessa funzione ricorsiva che si è vista per gli alberi binari:

1. se l'albero e' vuoto, ritorna FALSE (l'elemento non c'è)
2. se l'elemento si trova nella radice dell'albero, ritorna TRUE, dato che sappiamo che l'elemento sta nell'albero
3. altrimenti, ritorna TRUE se l'elemento si trova in almeno uno dei sottoalberi

I primi due passi sono identici a quelli degli alberi binari. Per il terzo passo, occorre solo considerare che si tratta in effetti di fare la chiamata ricorsiva su ognuno dei sottoalberi, ritornando TRUE se qualche chiamata ritorna TRUE. L'ultimo passo si può quindi implementare come:

1. per ogni sottoalbero:
   1. se l'elemento sta nel sottoalbero, ritorna TRUE
2. ritorna FALSE

Chiaramente, si ritorna FALSE soltanto se nessuna delle chiamate ricorsive ha tornato TRUE. In altre parole, il return FALSE; va messo fuori dal ciclo (si esegue quindi soltanto se il return dentro il ciclo non viene mai eseguito).

int Presenza(TipoAlbero a, int e) {
  int i;

  if(a==NULL)
    return FALSE;

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

  for(i=0; i<a->numfigli; i++)
    if(Presenza(a->figli[i], e))
      return TRUE;

  return FALSE;
}