Ricerca di un nodo all'interno di un albero

[elly0909]

Salve !
Sto cercando di gestire un metodo in java che, data la radice di un albero e una parola da ricercare, scorra in maniera ricorsiva tutti i suoi elementi figli. Vorrei che il metodo mi restituisse un ArrayList con tutti i nodi figli contenenti la parola ricercata.
In parole povere dovrei partire dalla radice e scendere, verificando che ogni nodo abbia a sua volta dei figli (ma questi figli possono a loro volta avere dei sotto figli) e per ognuno di questi verificare che contengano la parola ricercata...

Qualcuno sa darmi una dritta? Non sono pratico dei metodi ricorsivi... sono all'inizio....

HO INIZIATO COSI'

public ArrayList ricercaNodo(final Nodo radice, final String keyRicercata) {
ArrayList lista = new ArrayList();
final JAlbero.Nodo nodoRadice = radice;
String elementoInEsame = (String) nodoRadice.getDescrizione();

if (elementoInEsame != null) {
if (elementoInEsame.contains(keyRicercata)) {

listaFinale.add(elementoInEsame);
}
}
.............................
.......................................... NON SO COME FARE

return listaFinale;
}

[andbin]

Originariamente inviato da elly0909
Qualcuno sa darmi una dritta?

Per la ricorsione è molto semplice: nel metodo fai una "iterazione" sui figli del nodo e con ognuno invochi il metodo ricorsivamente passando il nodo.
Come iterare sui figli .... dipende dalla API offerta dalla classe del Nodo ... non lo posso sapere io, non so cosa è quel tipo Nodo.

Per la questione della lista ci sono almeno 2 soluzioni. La soluzione più pratica sarebbe quella di definire un metodo privato che riceve in input l'ArrayList. Il metodo ricercaNodo() che hai fatto continua ad esserci e con quella esatta signature ma tutta la gestione e la ricorsione la fa il metodo privato.

Se invece non puoi/vuoi usare un metodo privato per la ricorsione, devi per forza di cose nel metodo creare l'ArrayList, quando invochi in modo ricorsivo il metodo ottieni altri ArrayList che dovrai aggiungere al tuo ArrayList che poi restituisci e così via ....

[elly0909]

Innanzitutto ti ringrazio per la risposta.

Ho compreso cosa mi hai voluto dire...

ho provato ad agire in questo modo:



public ArrayList ricercaNodo(final Nodo nodo, final String keyRicercata) {

ArrayList listaFinale = new ArrayList();
final JAlbero.Nodo nodoInEsame = nodo;
if (nodoInEsame.getDescrizione().contains(keyRicercat a)) {
listaFinale.add(nodoInEsame);
}
// verifico se possiede figli
Nodo[] figliAlbero = nodoInEsame.getFigli();

if (figliAlbero != null) {
for (int i = 0; i < figliAlbero.length; i++) {
// ricorsione
ArrayList listaInterna = ricercaNodo(figliAlbero[i], keyRicercata);
if (listaInterna != null && listaInterna.size() > 0) {
listaFinale.addAll(listaInterna);
}
}
}
return listaFinale;

}

[andbin]

Originariamente inviato da elly0909
ho provato ad agire in questo modo:

Tecnicamente mi sembra corretto.

Non ho capito perché fai:

final JAlbero.Nodo nodoInEsame = nodo;

(vedo un tipo Nodo e un tipo JAlbero.Nodo ??)

E poi il test:

if (listaInterna != null && listaInterna.size() > 0) {

è superfluo. listaInterna non è mai null e se anche fosse vuoto, il addAll() non dà alcun problema. Al massimo puoi lasciare solo il test del size().

P.S. Metti il codice tra i tag [ CODE ] (senza spazi)!!!

[elly0909]

Ti ringrazio! Sono riuscito ad ottenere il risultato che volevo raggiunfere!

Grazie per l'aiuto!