Il seguente algoritmo esegue l’attraversamento di un albero in pre-ordine e in modo iterativo. Per il corretto funzionamento dell’algoritmo, riscriviamo parte della funzione print_tr(), per la stampa di un grafo. Il cuore della procedura risiede nella funzione walk(), per memorizzare i nodi dell’albero e fare a meno dello ricorsione utilizzo una coda.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct tree {
  int id;
  int value;
  int walk;
  int nA;
  struct tree **ar;
};

typedef struct tree tree;

// Pila usata nell'atraversamento
struct node {
 int value;
 struct node *next;
};

typedef struct node node;

int view = 0;

void set_node(tree *tr, int nN);
void connect_node(tree *tr, int nN);
void walk(tree *tr, int nN);
void print_tr(tree *tr, int nN, int cmd);

int is_empty(node *first);
int top(node *first);
node *push(node *first, int val);
node *pop(node *first);

int main(void) {
  tree *tr = NULL; // seme dell'albero
  int nN; // numero nodi

  printf("Inserisci il numero di nodi: ");
  scanf("%d", &nN);

  tr = calloc(nN, sizeof(tree));
  if(tr == NULL) {
    printf("Allocazione 1 fallita");
    exit(1);
  }

  set_node(tr, nN);
  connect_node(tr, nN);

  printf("Visita albero in corso...\n");
  walk(tr, nN);
  print_tr(tr, nN, 3);

  return 1;
}

void set_node(tree *tr, int nN) {
  int i=0; // contatore
  int value; // numero nodi, valore
  tree *t;

  for(i=0; i<nN; i++) {
    printf("Inserisci il valore del nodo %d: ", i);
    scanf("%d", &value);

    t = malloc(sizeof(tree));
    if(t == NULL) {
      printf("Allocazione 2 fallita");
      exit(1);
    }

   t -> id = i;
   t -> value = value;
   memcpy(&tr[i], t, sizeof(tree));

   free(t);
  }
}

void connect_node(tree *tr, int nN) {
  int i, j; // contatori
  int nA; // numero archi
  int n1; // nodo da collegare

  for(i=0; i<nN; i++) {
    printf("Inserisci il numero degli archi del nodo %d: ", i);
    scanf("%d", &nA);

    tr[i].nA = nA;
    tr[i].ar = calloc(nA, sizeof(tree *));

    if(tr[i].ar == NULL) {
      printf("Allocazione 3 fallita");
      exit(1);
    }

    for(j=0; j<nA; j++) {
      printf("Definisci i collegamenti del nodo %d (da 0 a %d): ", i, nN-1);
      scanf("%d", &n1);
    
      tr[i].ar[j] = &(tr[n1]);
    }
  }
}

void walk(tree *tr, int nN) {
  int i, k, ex=0;
  int *j;  				// azzero il contatore degli archi dei nodi
  node *pl = NULL;

  j = calloc(nN, sizeof(int));
  if(j == NULL) {
    printf("Allocazione fallita");
    exit(1);
  }
  memset(j, 0, sizeof(int)*nN);

  i = 0;  
  tr[i].walk = view;
  view++;
  
  do {
    while(j[i]<tr[i].nA) {              // finchè non ho percorso tutti gli archi di tr[i]
      k = tr[i].ar[j[i]]->id;

      tr[k].walk = view;                // visito il nodo collegto
      view++;

      j[i]++;                           // incremento il contatore (passo all'arco successivo)
      if(j[i]<tr[i].nA) {               // se ho percorso tutti gli archi di tr[i]
        pl = push(pl, i);               // salvo il nodo corrente nella coda
      }
      
      i = k;                            // visito il nodo successivo
    }

    // se esco dal ciclo ho raggiuno una foglia

    if(is_empty(pl) == 0) {
      i = top(pl);
      pl = pop(pl);
    }
    else {
      ex = 1;
    }  
  }while(ex == 0);
}

void print_tr(tree *tr, int nN, int cmd) {
  int i, j;
  
  if(cmd == 1 || cmd == 3) {
    printf("\nLista nodi (%d):\n", nN);
    for(i=0; i<nN; i++) {
      printf("Nodo %d - Valore %d - Visitato %d\n", tr[i].id, tr[i].value, tr[i].walk);
    }
  }
  
  printf("\n");
        
  if(cmd == 2 || cmd == 3) {
    printf("\nLista archi: \n");
    for(i=0; i<nN; i++) {
      printf("Archi da %d: \n", tr[i].id);
      for(j=0; j<tr[i].nA; j++) {
        printf(" - %d \n", tr[i].ar[j]->id);
      }
      printf("\n");
    }
  }
}

int is_empty(node *first) {
  if(first == NULL) {
    return 1;
  }
  else {
    return 0;
  }
}

int top(node *first) {
  return first -> value;
}

node *push(node *first, int val) {
  node *new;

  new = malloc(sizeof(node));
  if(new == NULL) {
    printf("Allocazione fallita\n");
    return NULL;
  }

  new -> value = val;
  new -> next = first;
  
  first = new;
  return first;
}

node *pop(node *first) {
  node *temp = first -> next;

  free(first);
  return temp;
}

Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.