[JAVA] Ricerca in albero n-ario

[topix93]

Cio che volevo sapere è come si possa fare a livello di programmazione un accesso a tutte le foglie dell'albero...
grazie in anticipo

[franksisca]

dipende...in parole spicciole fai ricorsivamente un controllo sul figlio sinistro, setti una variabile di "cheching" e passi al destro.

ovvimanet prima devi scendere e poi risali (bottom up).


questa è la prima cosa che mi viene in emnte

[__ZERO_UNO__]

DFS(Albero):
Foglie <- 0; //insieme vuoto
DFS_visit(Albero[radice], Foglie);
end

DFS_visit(v, S):
if Adj[v] == 0 then
S <- S unione v
return;
for w in Adj[v] do
if Adj[w] == 0 then S <- S unione w;
else DFS_visit(w, S);
end
end


Al termine dell' algoritmo S conterrà le foglie dell'albero.
Probabilmente si può fare meglio.

[Floris]

Puoi farlo con una ricerca ricorsiva in profondità o in larghezza.
Supposto che tu abbia definito la classe nodo in modo opportuno con almeno un campo chiave la ricerca in profondità dovrebbe essere più o meno così:

public class Nodo{
public:
int chiave;
Vector<Nodo> figli;
}

nodo ricercaDF(Nodo n, int valore){
if(n.chiave == valore) return n;
for(Iterator<Vector<Nodo>> it = n.figli.iterator(); it.hasNext();){
Nodo esito = ricercaDF(it.next(), valore);
if(esito != null) return esito;
}
return null;
}

Invocando:

ricercaDF(radice,valore);

Non l'ho verificato. Si suppone che figli sia al più vuoto e mai null e che radice non sia null; Ritorna null se non trova la chiave.

Per la ricerca in larghezza dovresti prima scorrere tutti i figli di ogni nodo ricercando la chiave e poi eseguire la ricorsione su di essi.

[clockover]

Ma devi visitare solo le foglie?

[Floris]

Ma devi visitare solo le foglie?
E' vero...scusa ho letto male...dal titolo avevo pensato ad una ricerca sull'albero completo.:doh:

[dierre]

E controlla che la profondità non sia infinita :asd: