Newsgroup: it.comp.lang.c
Titolo: Help su alberi

Ciao a tutti....
Io avrei un problema: non ho idea di come si facciano le visite degli alberi
in modo iterativo...
Per esempio se la visita in ordine simmetrico fosse cosě
void inorder(nodo *root)
{
    inorder(root->left)
    printf("\n%d",root->dato);
    inorder(root.>right);
}
come potrei farla in maniera iterativa?
Grazie in anticipo per le eventuali risposte...
Stefano

come potrei farla in maniera iterativa?
Devi costruirti uno stack dei nodi precedentemente visitati, e usarlo
per ritornare sui tuoi passi.
L'uso di una lista che vedi sotto è meno veloce di un vettore, ma non
limita a priori la profondità massima.
Non ho testato il codice, quindi non garantisco che sia esente da
errori... ma una volta capito il programma, penso che non avrai alcun
problema a debuggarlo. :-)
(correggi eventualmente lo struct sotto, perché non conosco come hai
definito il tipo di dato 'nodo', visto che non l'hai postato)
struct stack_node    /* questa struttura serve per lo stack */
{
  struct nodo *questo;
  struct nodo *prev;  
};
  struct stack_node *top == NULL; /* questa variabile globale serve
per conoscere la cima dello stack, se è NULL lo stack è vuoto */
/* Poi ti serviranno due funzioni push e pop.
Ovviamente il primo elemento valido dello stack (quello alla base
della pila) dovrà avere il puntatore *prev che punta a NULL.
(nota: ho messo come valore restituito da push un char che può
assumere valore 0 se tutto va bene, altrimenti errore, tuttavia nella
funzione inorder non ho fatto uso di questi controlli... se vuoi,
occupatene tu stesso ;-))  ) */
char push(nodo *elemento)	/* inserisce elemento in cima allo
stack */
{
  struct stack_node *temp;
 
  if(elemento == NULL)
    return 1;	/* errore elemento nullo */
  temp = malloc(sizeof(stack_node));
  if(temp == NULL)
    return 2;	/* errore stack overflow (memoria esaurita) */
  temp->prev = top;	/* aggiorna top e inserisce */
  top = temp;
  temp->questo = elemento;
  return 0;		/* inserimento avvenuto correttamente */
}
nodo *pop()	/* restuisce NULL se lo stack è vuoto, un puntatore al
nodo in cima allo stack in caso contrario */
{
  nodo *temp;
  struct stack_node *old_top;
  if(top == NULL)	/* controllo stack underflow */
    return top;
  /* aggiorna top, libera la memoria dal vecchio top e restituisce il
puntatore al nodo cui esso puntava */
  temp = top->questo;	
  old_top = top;
  top = top->prev;
  free(old_top);
  return temp;
}
/* una volta sistemato lo stack, posso finalmente scrivere inorder in
maniera iterativa */
void inorder_iterativo(nodo *root)
{
    inorder(root->left);
    printf("\n%d",root->dato);
    inorder(root.>right);
  nodo *temp; /* questa variabile non è necessaria, ma è più chiaro
così IMHO. Si poteva usare direttamente *root al suo posto, nelle
righe che seguono  */
  temp = root;
  while(temp != NULL)	/* finché non hai finito l'albero...  */
  {
    while(temp->left != NULL)	/* finché c'è un ramo sx... */
    {
      push(temp);	/* metti l'elemento nello stack */
      temp = temp->left;  /* visita il suo ramo sx */
    }
    printf("\n%d",temp->dato);	/* stampa */
 
    do
    {
      temp = pop();		/*risale lo stack */
      if(temp == NULL)	/* se lo stack non è vuoto... */
        printf("\n%d", temp->dato);	/* ... stampa */
    }while(temp != NULL && temp->right == NULL);
/* continua fino a trovare un elemento che abbia ramo dx, o fino ad
esaurire l'albero */
    if(temp != NULL)
      temp = temp->right;    /* si posiziona sul ramo sx e riparte */
  }
}