PDA

Visualizza la versione completa : Alberi: procedura altezza nodi


ferra03
22-01-2010, 13:51
Ciao a tutti mi servirebbe una mano per scrivere una procedura in pseudocodice per calcolare l'altezza di ogni nodo di un albero rappresentato mediante lista di adiacenza, sapendo che l'altezza di un nodo è il più lungo cammino da esso a una foglia. copio e incollo il testo dell'esercizio:

Esercizio 4.
a) Definire la nozione di albero con radice. Definire inoltre l’altezza di un nodo in tale albero.

b) Descrivere una procedura per risolvere il seguente problema:

Istanza : un albero con radice T di n nodi, rappresentato mediante liste di adiacenza.
Soluzione : l’altezza di ciascun nodo di T.

c) Assumendo il criterio di costo uniforme, valutare l’ordine di grandezza del tempo di calcolo
e dello spazio di memoria richiesti dalla procedura precedente in funzione del parametro n.
Giustificare le soluzioni fornite.

Grazie mille

Stoicenko
22-01-2010, 15:21
letto il regolamento? non si fanno gli esercizi per casa..

se hai scritto qualcosa postalo, se hai pensato ad una soluzione postale..

poi si discute

ferra03
22-01-2010, 20:47
io ho pensato ad una soluzione ma non riesco a metterla in pseudo codice, praticamente utilizzerei la procedura di visita standard partendo dalla radice e marcando ogni nodo in modo tale da "accorgermi" se sto rivisitando un nodo(e questa è la parte più o meno semplice) le difficoltà iniziano quando devo stampare l'altezza di ciascun nodo, perchè avevo pensato di creare una variabile contatore che partendo da 0 incrementa ogni volta che incontra un nuovo fino alla foglia più lontana, e questo è un'altro problema dire al programma di considerare il cammino più lungo.

xnavigator
23-01-2010, 01:46
leggendo solo il titolo:

usa l'algo di BFS, al suo interno crea un array contente le distanze dal nodo di origine

Loading