Strutture Dati - Prova del 19 Aprile

Ecco le mie soluzioni ai due esercizi della prova di Strutture Dati del 19 Aprile con il prof. Salvatore La Torre.


E Il primo esercizio consisteva nell'implementare il metodo int maxValFoglie(BinaryTree<Integer> t) che restituisce il massimo tra i valori contenuti nelle foglie dell'albero t:

public static int maxValFoglie(BinaryTree<Integer> T)

{

int max = 0;

Iterable<Position<Integer>> posizioni = T.positions();

Iterator<Position<Integer>> it = posizioni.iterator();

while(it.hasNext())

{

Position<Integer> curr = it.next();

if (T.isExternal(curr))

max = Math.max(max, curr.element());

}

return max;

}

//versione ricorsiva

public static int maxValFoglie(BinaryTree<Integer> T)

{

return maxValFoglie(T, T.root(), 0);

}

public static int maxValFoglie(BinaryTree<Integer> T, Position<Integer> p, int max)

{

if(T.isExternal(p))

max = Math.max(max, p.element());

else

{

if (T.hasLeft(p))

max = maxValFoglie(T, T.left(p), max);

if (T.hasRight(p))

max = maxValFoglie(T, T.right(p), max);

}

return max;

}

mentre il secondo consisteva nell'implementare il metodo void forzaInorder(BinaryTree<E> t, PositionList<E> l) che a) testa se l'albero t e la lista l hanno lo stesso numero di elementi; b) in caso affermativo, gli elementi di l sono copiati in t in modo che la visita inorder di t produca l'ordine della lista l; c) in caso negativo viene lanciata una IrregularArgumentException:

public static <E> void forzaInorder(BinaryTree<E> t, PositionList<E> l)

{

if (t.size() != l.size())

throw new IllegalArgumentException("Tree and Sequence are different");

 

f(t,l,t.root());

}

public static <E> void f (BinaryTree<E>t, PositionList<E>s, Position<E> p)

{

if (t.hasLeft(p))

f(t, s, t.left(p));

 

t.replace(p, s.remove(s.first()));

 

if (t.hasRight(p))

f(t, s, t.right(p));

}