next up previous contents index
suivant: Files et parcours en monter: main précédent: Parcours en profondeur des   Table des matières   Index


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 n\oeuds de l'arbre, et traite chaque n\oeud 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);
    }
  }
}



R Lalement