Newsgroup: it.comp.lang.c++
Titolo: stampa di un albero binario

Esiste un modo per implementare iterativamente l'algoritmo di
attraversamento simmetrico per la stampa di un albero binario? Se si
(come immagino), potreste darmi una qualche linea guida? Grazie,
Cecco

 wrote in message 3BA39B3D...@tin.it...

perché iterativo? ricorsivo non va bene?
Pela

> perché iterativo? ricorsivo non va bene?
Certo che va bene, le ragioni sono due: primo perchè ho tentato di farlo
per esercizio, ma dopo averci battuto la testa un pò mi sono arreso ed
ho chiesto aiuto, e poi perchè in effetti mi è venuto un dubbio: poichè
gli algoritmi ricorsivi eseguono una serie di chiamate annidate a
sottoprogrammi, utilizzando quindi una grande quantità di memoria, non è
che se l'albero è troppo grosso si rischia di esaurirla?
Cecco


wrote:

Ho letto un posting di questo tipo qualche tempo fa su comp.lang.cpp
(credo) e per sfizio ho provato ad implementare la visita anticipata,
simmetrica e posticipata senza ricorsione. La cosa non e' banale
ma nemmeno molto complessa; in pratica si tratta di passare da un
nodo al successivo in ordine di visita... per prendere la decisione
non serve altro che il nodo corrente e il tipo di visita che si
vuole effettuare (non servono cioe' variabili di stato addizionali).
Una cosa che ho visto necessaria e' pero' ovviamente la possibilita'
di "risalire" al padre e anche di sapere se si sta risalendo tramite
il ramo sinistro oppure tramite il ramo destro.
La visita simmetrica che ho implementato io e' la seguente:
  void in1(Node *n)
  {
    while (n!=0 && n->child[0]!=0)
      n=n->child[0];
    while(n!=0)
    {
      std::cout << "[" << n->value << "]";
      if (n->child[1])
      {
        n=n->child[1];
        while (n->child[0])
          n=n->child[0];
      }
      else
      {
        while (n->pop!=0 && n->pop->child[1]==n)
          n=n->pop;
        n=n->pop;
      }
    }
  }
Il primo while serve a trovare il nodo di partenza
e in pratica scende l'albero se esistono dei figli
a sinistra. Il primo nodo che non ha figli a sinistra e'
quello da elaborare inizialmente.
Il loop principale e' fatto in questo modo:
  1) "visita" del nodo (in questo caso l'operazione
     svolta e' una stampa)
  2) Se esiste un sottoalbero di destra allora
     cerco il primo nodo da elaborare nel sottoalbero
     di destra (il loop per trovare questo primo nodo
     nel sottoalbero e' simile a quello iniziale)
  3) Se non esiste un sottoalbero di destra allora
     devo "salire": se arrivo al padre dal suo
     ramo sinistro allora mi fermo (il prossimo
     nodo da elaborare e' il padre) altrimenti
     proseguo la risalita.
Nota che dopo (2) non viene considerato il sottalbero
di sinistra perche' e' sicuramente gia' stato elaborato
visto che ho appena compiuto la visita del nodo corrente.
Le versioni anticipata e posticipata sono simili: si
tratta sempre di un posizionamento iniziale e di capire
quale e' il prossimo nodo dato il nodo corrente
(buon divertimento ;))
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 che se l'albero è troppo grosso si rischia di esaurirla?
Forse 10 anni fa (solo su Pc Dos però)
E comunque una chiamata ricorsiva ( ameno che tu non passi i dati per
valore ) non è così pesante.
Byes
FusionFai