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_cell *stack_data;

La version itérative empile les n uds de l'arbre, et traite chaque n ud au dépilement :

void depth_first_iter(tree_cell *p, void f(cell_data)) {
  stack s;
  mk_empty_stack(&s);
  push(p, &s);
  while (!is_empty_stack (&s)) {
    p = pop(&s);
    if (!is_empty_cell(p)) {
      f(p->label);
      push(p->right, &s);
      push(p->left, &s);
    }
  }
}