OPS > Alberi

PREMESSA

La seguente figura rappresenta un albero genealogico che contiene i nodi a, b, c, d, e, f, g, h, i, j, k.

Gli alberi di questo tipo possono essere descritti con un insieme di termini del tipo:

arco(<genitore>,<figlio>)

In tal modo, l’albero sopra riportato è descritto dal seguente insieme di termini:

arco(b,e), arco(b,f), arco(a,b), arco(a,c), arco(c,g), arco(a,d), arco(d,h), arco(d,i), arco(d,j), arco(i,k)

Si ricordino i gradi di parentela: gli zii sono i fratelli del genitore, i cugini sono i figli degli zii, il nonno è il padre del padre, ecc.

Pertanto, in questo albero:

  • il nodo a è nonno di 6 nipoti [e, f, g, h, i, j],
  • il nodo k ha 2 zii [h, j],
  • il nodo h ha 2 fratelli [i, j] e 3 cugini [e, f, g].

Il nodo a, che non ha genitore, si dice radice dell’albero; i nodi [e, f, g, h, j, k] che non hanno figli, si dicono foglie dell’albero.


PROBLEMA

Disegnare l’albero genealogico (con radice h) descritto dai seguenti termini:

arco(i,a), arco(g,b), arco(g,f), arco(e,d), arco(d,c), arco(h,i), arco(h,g), arco(h,e)

Rispondere ai quesiti sotto riportati.

  • Trovare la lista L1 delle foglie dell’albero, scritte in ordine alfabetico.
  • Trovare la lista L2 degli zii di b, riportati in ordine alfabetico.
  • Trovare la lista L3 dei cugini di f, riportati in ordine alfabetico.
  • Trovare la lista L4 dei nonni presenti nell’albero, riportati in ordine alfabetico.