Come si fa a sapere un nodo foglia di un albero ennario- java

[Mitele]

salve ,
dovrei scorrere un albero ennario memorizzato in una lista e dovrei sapere quando mi trovo su un nodo foglia.....nel mio caso dovrei creare un menu ad albero, ho la seguente lista
List list = CmsJspNavBuilder.getSiteNavigation(cms,"/Italian/", -1);

dove in lista possiamo avere
/Italian/Notizie
/Italian/Notizie/notizia1.html
Italian/Notizie/notizia2.html
/Italian/Notizie/Allegato


/Italian/Bando
/Italian/Bando/Bando1.html
/Italian/Bando/Bando2.html

dovrei riuscire a creare una struttura grafica del tipo:

°Italian/
Notizie/
notizia1.html
notizia2.html
Allegato/
Bando/
Bando1.html
Bando2.html

Il mio problema è riuscire a capire quando la cartella è vuota oppure qual è il suo ultimo file(directory), poichè ho gia' visto in rete che c'è gia' qualcosa svolto per il menu ad albero..e dovrei solo capire quando chiudere la cartella...in pratica se il contenuto che leggo dalla lista è una cartella allora stampa <div>...se mi trovo sull'ultimo file della cartella corrente (che potrebbe essere a sua volta un'altra cartella) allora devorei stampare </div>


grazie

[desa]

La soluzione che ti suggerisco, visto che devi modellare un albero, è utilizzare proprio una struttura dati di questo tipo: esegui un ciclo sulla lista per completare il popolamento dell'albero, che poi andrai a visitare con metodo depth-first per costruire la pagina HTML di risposta.
In pratica, analizzando sequenzialmente la lista che hai fornito:

/Italian/Notizie: crei il nodo radice "Italian" e il figlio "Notizie";
/Italian/Notizie/notizia1.html: "Italian" e "Notizie" esistono già, crei solo il nodo figlio di "Notizie", "notizia1.html";
/Italian/Notizie/notizia2.html: come sopra, crei solo il nodo figlio di "Notizie", "notizia2.html";
/Italian/Notizie/Allegato: idem, solo il nodo "Allegato";
ecc.

Come detto sopra, completato il popolamento dell'albero lo utilizzerai per produrre la pagina HTML.

Con questa tecnica (parlando soprattutto - ma non solo -in termini computazionali) è inoltre perfettamente superfluo che gli elementi della lista siano ordinati in base alla loro "profondità".

[Mitele]

l'albero in questo modo è binario?
se si con quale criterio?

la lista mi viene gia' fornita ed è gia' riempita con i valori che ho descritto sopra..
Devo scorrere la lista e creare un menu ad albero, le difficoltà sono:
1)individuare le cartelle
2)Individuare l'ultimo file di una cartella

[desa]

No, l'albero è ennario ed è giusto che sia così, visto che stai modellando un file system: sarà binario solo nel caso in cui ogni directory contenga al più due elementi... ma, salvo casi particolari, non è la situazione in cui ti trovi a lavorare di solito.

Quello che fa l'algoritmo che ti ho suggerito è "riversare" in una struttura dati ad albero il contenuto della tua lista: è una scelta coerente con la rappresentazione grafica che vuoi visualizzare e ti consente di realizzare in maniera naturale tutta una serie di operazioni.
Ad esempio, puoi verificare se una cartella è vuota semplicemente controllando se il nodo corrispondente non ha figli. Oppure, puoi costruire come preferisci la sua rappresentazione grafica semplicemente applicando all'albero un algoritmo di visita.

Prova a rifletterci - magari seguendo con carta e penna l'algoritmo che ti delineato - e vedrai che funziona.

[Mitele]

non conosce bene gli alberi ennari nel senso che non ci ho lavorato...
Come faccio ad inserire i nodi?

citazione

/Italian/Notizie: crei il nodo radice "Italian" e il figlio "Notizie";
/Italian/Notizie/notizia1.html: "Italian" e "Notizie" esistono già, crei solo il nodo figlio di "Notizie", "notizia1.html";

come faccio a sapere che il nodo Italian e Notizie gia' esistono e che notizia1.html deve essere messo sotto Italin/Notizie/???

Mi potresti fornire una struttura semplice di come costruire un albero ennario e come inserire i nodi?
Ho cercato in rete , ma ho le idee molto confuse..

grazie per l'attenzione

[bstefano79]

è possibile realizzare un albero ennari come albero binario tramite la tecnica "figlio a sinistra fratello a destra" trovi come farlo anche su wikipedia http://it.wikipedia.org/wiki/Albero_n-ario

[Mitele]

grazie l'ho letto , ma non ho capito il metodo:

public boolean insert(NTreeNode parent, NTreeNode[] sons).....

io creo l'albero, poi come si fa a passare "sons"...da dove li ricavo?

Inizialmente l'albero sara' composto da un solo nodo con parent==null, sons quanto vale???

grazie per ogni tua possibile risposta

[desa]

Non so bene che tipo di strutture dati ad albero sono disponibili nelle API standard Java: quando ne ho avuto bisogno in passato ho sempre preferito implementarmele da me (anche perchè è un tipo di progettazione che mi ha sempre appassionato).

Senza scendere nei dettagli implementativi (su cui ti lascio riflettere), devi definire un albero che, all'avvio dell'applicazione, contenga il solo nodo "root" e in cui ogni nodo ammetta una lista di nodi figli. Crei poi un metodo, eventualmente ricorsivo, che lavori su un nodo di partenza e sul path che vuoi inserire, nel seguente modo.
Ipotizziamo che l'albero contenga già il percorso "/Italian/Notizie/notizia1.html":

* Prima chiamata: inserisci(root_node, "Italian/Notizie/notizia2.html")
Tramite una substring() ricavi che l'elemento che stai analizzando è "Italian". Ricerchi tale stringa tra i figli di root_node e scopri che esiste già. Richiami quindi:
* Seconda chiamata: inserisci(nodo_Italian, "Notizie/notizia2.html")
Tramite una substring() ricavi che l'elemento che stai analizzando è "Notizie". Ricerchi tale stringa tra i figli di nodo_Italian e scopri che esiste già. Richiami quindi:
* Terza chiamata: inserisci(nodo_Notizie, "notizia2.html")
Tramite una substring() ricavi che l'elemento che stai analizzando è "notizie2.html". Ricerchi tale stringa tra i figli di root_nodo_Notizie e scopri che NON esiste. A questo punto lo inserisci nell'albero e ritorni.

Prova a pensare a una soluzione di questo tipo. Fammi sapere se dovessi avere altri dubbi!

[Mitele]

Grazie Desa per la soluzione che mi hai consigliato,
io infatti ho pensato di splittare la stringa /Italian/Notizie/notizia1.html con l'operatore '/' andando a creare un array di stringhe contenete Italian,Notizie e notizia1.html....
Poichè l'albero deve esere ennario(ed io non mi so muovere proprio bene) e anche essendomi documentato in rete , ho tutt'ora le idee molto confuse sulla realizzazione di un albero ennario, in particolare sul metodo public boolean insert(NTreeNode parent, NTreeNode[] sons).....non c'ho capito nulla...

Una volta creato l'albero, poi come si fa a passare "sons"...da dove li ricavo?

Inizialmente l'albero sara' composto da un solo nodo con parent==null, sons quanto vale???

non riesco a capire la gestione....mi potresti postare il codice ?

grazie per l'aiuto

[bstefano79]

la metodologia figlio a sinistra fratello a destra è così fatta

per ogni nodo hai 2 puntatori... nel puntatore a sinistra metti il primo figlio per esempio A , questo figlio (B) avrà come puntatore destro la lista dei propri fratelli (e quindi figli del nodo A)

esempio pratico

                            A  
                          / |   \
                       /     |    \
                     /       |    |
                   /        |     |
                  B       C      D  
               /     \           / | \
             E        F       G   H   I

l'albero binario saraà così rappresentato

A---null
|
B-------C--------D
|       |null    |
|                 G-------H------I
|                 |null   |null  |null
E-------F
|null   |null

dove | rappresenta il puntatore sinistro e ----- il puntatore destro

le foglie sono quelle senza figli (puntatore sinistro a null)