Piles et parcours en profondeur des arbres

Il est possible de transformer cette version récursive du parcours en profondeur en une version itérative, à l'aide d'une pile. Il faut d'abord définir le type des objets à empiler comme étant << pointeur de cellules >> :

typedef tree stack_data;

La version itérative empile les nuds de l'arbre, et traite chaque nud au dépilement :

void depth_first_iter(tree p, void f(data)) {
  stack s;

  mk_empty_stack(s);
  push(p, s);
  while (!is_empty_stack (s)) {
    p = pop(s);
    if (!is_empty_tree(p)) {
      f(p->label);
      push(p->right, s);
      push(p->left, s);
    }
  }
}