Home Introduzione Programma Orario Laboratorio Nettuno Esame Diario 02-03 Materiale Challenge News Link Forum Esoneri

horizontal rule

Tema n. 2

scadenza: ore 23:59 del 01/06/2007 (perentoria)

Inclina l'albero

Scrivere un algoritmo Java che, dato un albero generico rappresentato attraverso la classe Nodo appresso specificata, riordini le liste di nodi "fratelli" in maniera da privilegiare i nodi che sono radici di sottoalberi con "meno" nodi.

public final class Nodo {

public Nodo primoFiglio,

ultimoFiglio,

proxFratello,

precFratello;

public Object dati;

}

La classe Nodo, non estendibile, prevede per ciascun nodo:

bulletriferimenti ai due fratelli adiacenti, cosicché le liste di fratelli risultano doppiamente collegate;
bulletriferimenti al primo ed ultimo figlio, per l'accesso diretto ai due estremi della lista doppiamente collegata che rappresenta i figli.

E' inoltre previsto un campo dati di tipo Object per la memorizzazione in un nodo di eventuali informazioni di servizio, qualora ciò fosse ritenuto utile. I nodi dell'albero di input hanno il campo dati posto a null.

L'algoritmo da realizzare ha un input di tipo Nodo (la radice dell'albero) e lavora attraverso side effect. L'algoritmo restituisce void.

Specifiche

  1. La classe da realizzare si chiama InclinaAlbero e rappresenta i nodi dell'albero attraverso la classe Nodo, in cui i fratelli vengono rappresentati attraverso una lista doppiamente collegata e ogni nodo ha i riferimenti al primo ed ultimo figlio.
  2. La classe ha un metodo public static void inclina(Nodo radice) che, data la radice di un albero, esegue il riordinamento dei nodi fratelli (in ordine crescente) come specificato: dati due nodi fratelli (aventi stesso genitore) u e v, il riordinamento prevede che se |T(u)| < |T(v)| allora u deve precedere v, avendo indicato con T(x) il sottoalbero di radice x e con |T(x)| il suo numero di nodi.
  3. La classe ha un metodo public static String getMatricola() che restituisce la matricola dello studente partecipante.

invio contributi

 

horizontal rule

Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.37
by FdA