[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]

Originariamente inviato da clockover

Ma devi visitare solo le foglie?

E' vero...scusa ho letto male...dal titolo avevo pensato ad una ricerca sull'albero completo.

[dierre]

E controlla che la profondità non sia infinita