Files et parcours en largeur des arbres

     

L'autre façon de parcourir un arbre est en largeur (d'abord). Les n uds de la figure ont été numérotés dans l'ordre du parcours en largeur : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

On ne peut pas programmer récursivement ce parcours de façon naturelle. La version itérative utilise la structure de file au lieu de celle de pile.

void breadth_first(tree_cell *p, void f(cell_data)) {
  queue q;
  mk_empty_queue (&q);
  in(p, &q);
  while (!is_empty_queue (&q)) {
    p = out(&q);
    if (!is_empty_cell(p)) {
      f(p->label);
      in(p->left, &q);
      in(p->right, &q);
    }
  }
}

Cette fonction a exactement la même forme que depth_first_iter, les piles étant simplement remplacées par les files, avec leurs opérations : ceci est un indice du pouvoir << structurant >> des structures de données.