Newsgroup: it.comp.java
Titolo: Aiuto algoritmo per visitare albero n-ario

Qualcuno mi sa dire un semplice modo per visitare un albero n-ario senza
ausilio di classi prefatte che già lo implementano?
Ho provato parecchio tempo e ancora non riesco a "scorrerlo"
correttamente.Eppure ho scritto un metodo per aggiungere nodi che
funziona a dovere!
Ho usato una struttura con un "puntatore" al figlio e uno agli eventuali
fratelli.
Grazie
luca


Domanda: che tipo di visita devi fare? Pre-ordine, post-ordine, in-
ordine? Casuale?
Laboratorio di Algoritmi e Strutture Dati, eh ;)
--
www.megadix.it

Ti scrivo l'algoritmo in pseudo-codice che implementa la visita per
livelli, in cui usi una lista l come coda (aggiungi in coda e rimuovi
dalla testa). Per effettuare la visita in profondità puoi usare la
lista l come pila (aggiungi in testa e rimuovi dalla testa).
LinkedList<Nodo> l=new LinkedList<Nodo>();
c.add(albero.radice);
while (!c.isEmpty()) {
   Nodo n=c.removeFirst();
   //qui fai quello che devi fare con n
   for (Nodo f:n.figli) {
      l.addLast(f); //cambiare con addFirst(f) se vuoi la visita in
profondità
   }
}
Ovviamente, quello che devi specializzare è la scansione dei figli del
nodo n. Tu dici che usi un puntatore al figlio (il "primo", suppongo)
e un puntatore ai fratelli (anche qui suppongo al "primo" fratello).
In questo modo la visita dei figli del nodo n diventa un po' meno
compatta ed elegante da scrivere, ma ovviamente si può fare. :)
Ciao,
Massimo



Conosco quest'algoritmo ma non mi è chiaro cosa hai scritto..cosa
sarebbe c.add, non hai nominato la lista con l?
Per me va benissimo la visita per livelli ma ancora non mi è molto
chiaro come implementarla,forse ho complicato tutto in quanto ho
impostato male la funzione che crea un nuovo nodo e lo aggiunge
all'albero.
Cmq si ho usato un puntatore al primo figlio e un puntatore al primo
fratello.
Allego il codice che ho scritto per aggiungere un nodo:
public void add(String name,String supcode){
    Nodo temp=radice;
    while(temp!=null){
      if(supcode.equals(temp.parola)){
        if(temp.figlio==null){
        Nodo t=new Nodo(name,temp.figlio);
        temp.figlio=t;
        break;
        }
        else{
          temp=temp.figlio;
          while(temp.fratello!=null){
            temp=temp.fratello;
          }
          Nodo t=new Nodo(name,temp.fratello);
          temp.fratello=t;
          break;
        }
      }
      else{
        if(temp.fratello!=null){
          temp=temp.fratello;
        }
        else{
          temp=temp.figlio;
        }
      }
    }
  }
  Supcode sarebbe una stringa che contiene il nome del nodo padre del
nuovo nodo da inserire.
Saluti,
luca

 fratelli.
Senza entrare nel dettaglio del codice che ti è già stato suggerito 
(anche se non condivido tutti i suggerimenti), segnalo un paio di dubbi:
- se l'albero è n-ario può avere per definizione n figli, per cui ha 
poco senso conservare un riferimento al figlio E eventuali riferimenti 
altri. Nel nodo ti serve l'identificativo univoco e una lista dei figli;
- per visitarlo usi un algoritmo ricorsivo: parti dalla radice e scorri 
i figli. Nel caso abbiano a loro volta dei figli li scorri e così via.
In sostanza (e molto in sintesi):
class Nodo
   int id;
   List childs;
   Nodo search(int id)
     Nodo found;
     if 
this.id
 == id
       return this
     for child in childs  // da verificare anche che childs sia != null
       found = child.search(id)
       if found != null
         return found
     return null
Ciao.

 .....
La funzione che hai scritto, se ha l'obiettivo di aggiungere un nuovo
nodo come figlio di un nodo il cui nome è dato in input, va bene.
Quindi, se tu nell'oggetto Nodo hai una parola (String), un figlio
(Nodo) e un fratello (Nodo), lo pseudo-codice che ti ho suggerito
diventa il seguente:
Nodo r è la radice dell'albero.
LinkedList<Nodo> c=new LinkedList<Nodo>(); //prima ho scritto l invece
di c, forse per questo non ti era chiaro
c.add(r); //aggiungi alla lista il nodo radice
while (!c.isEmpty()) {
   Nodo n=c.removeFirst(); //rimuovi il primo nodo nella lista
   //qui fai quello che devi fare con n ad esempio scrivi n.parola
   Nodo f=n.figlio;
   while (f!=null) {
      c.addLast(f); //cambiare con addFirst(f) se vuoi la visita in
profondità
      f=f.fratello;
   }
}
Per qualunque visita (in ampiezza o profondità) tu debba fare hai
bisogno di una struttura ausiliaria. In questo caso hai una coda,
implementata semplicemente mediante una lista nella quale inserisci in
coda e rimuovi dalla testa. Nel caso di visita in profondità ti serve
una pila, che puoi semplicemente implementare mediante una lista nella
quale inserisci in testa e rimuovi in coda. Quando scrivi il metodo in
modo ricorsivo (per la visita in profondità) hai comunque una
struttura dati ausiliaria, ovvero lo stack (pila) della ricorsione.
Quindi non fare l'errore di pensare che la complessità spaziale sia
migliore! :)
L'algoritmo è ottimale, sia dal punto di vista temporale che spaziale.
Dal punto di vista temporale, hai complessità O(n), dove n è il numero
di nodi, poiché fai un numero costante di operazioni per ciascun nodo
visitato.
Dal punto di vista della complessità spaziale, la lista (che funge da
coda) non sarà mai più "grande" di n, in particolare avrà cardinalità
massimo al momento della visita del livello più ampio.
Resta il fatto che l'implementazione del Nodo che ti è stata
suggerita, ovvero tenere nel nodo una Collection, ad esempio una
LinkedList di nodi figli, anziché un riferimento al primo figlio e al
primo fratello, è più elegante (sebbene la tua non sia errata).
Ciao,
Massimo


Molte grazie per l'aiuto,
alla fine mi sono accorto che era sbagliata la funzione che aggiungeva
un nodo perchè da un certo livello in poi dell'albero non funzionava
più,quindi l'ho sostituita usando il metodo che mi hai suggerito tu con
la lista e ora sembra andare alla grande.
Grazie ancora per la disponibilità!
Saluti,
Luca

On May 23, 5:01 pm, Pablo Xon <pablo....@NIENTESPAMconcavi.net> wrote:
concordo con le tue affermazioni.
Inoltre non ho chiaro perché la rappresentazione debba tenere conto
dei figli.
Poiché il nodo padre di un intero sotto albero è e può essere un solo
nodo, il legame si mantiene con il padre
Nodo{
     id_nodo;
     id_padre;
     altre_informazioni_nodo }
queste sono tutte le info che servono al nodo;
mettendo i nodi in una qualche struttura che preferisci (es Lista) che
rappresenti l'albero n-ario.
AlberoNArio{
   List<Nodi>
}
su questo albero implementi List<Nodi> getSonsOf(Nodo n);
che restituisce i figli di un certo nodo;
Le visite depth-first o breadth-first sono banalmente
l'implementazione degli algoritmi di visita che puoi trovare sia in
forma ricorsiva che iterativa.
(
http://en.wikipedia.org/wiki/Depth-first_search
 o
http://en.wikipedia.org/wiki/Breadth-first_search
 )
Ciao Gianmarco

 dei figli.
Sostanzialmente perch�, esclusi casi estremi, � molto pi� rapido 
effettuare un ciclo in una lista di figli piuttosto che nell'unica lista 
che contiene tutti i nodi, cercando l'id_padre.
Inoltre un albero, per definizione, non consente che un nodo abbia pi� 
di un padre, per cui � solo tempo di elaborazione sprecato.