Parcours en profondeur des arbres

   

Le parcours en profondeur est très facile à programmer dans sa version récursive ; s'il s'agit simplement d'imprimer les valeurs des n uds, on écrira :

void depth_first_rec(tree_cell *p) {
    if (!is_empty_cell(p)) {
      printf("%d\n", p->label);
      depth_first_rec(p->left);
      depth_first_rec(p->right);
    }
}

Pour une utilisation plus générale du parcours en profondeur, on peut passer une procédure en paramètre, qui opère sur la valeur de chaque n ud :

void depth_first_rec(tree_cell *p, void f(cell_data)) {
    if (!is_empty_cell(p)) {
      f(p->label);
      depth_first_rec(p->left, f);
      depth_first_rec(p->right, f);
    }
}

Il s'agit en fait de l'ordre préfixe de ce parcours, où chaque n ud de l'arbre est traité avant ses descendants.

L'application de cet ordre à l'arbre de la figure  donne comme résultat : 1, 2, 4, 8, 5, 3, 6, 9, 10, 12, 13, 7, 11. Pour obtenir l'ordre infixe, où chaque n ud est traité entre ses descendants gauches et ses descendants droits, et l'ordre postfixe, où chaque n ud est traité après tous ses descendants, il suffit de déplacer l'appel à la fonction f ; on obtient

    depth_first_rec(p->left, f);
    f(p->label);
    depth_first_rec(p->right, f);

pour l'ordre infixe, qui donne comme résultat sur l'arbre de la figure  4, 8, 2, 5, 1, 9, 6, 12, 10, 13, 3, 11, 7, ainsi que

    depth_first_rec(p->left, f);
    depth_first_rec(p->right, f);
    f(p->label);

pour l'ordre postfixe, qui donne comme résultat 8, 4, 5, 2, 9, 12, 13, 10, 6, 11, 7, 3, 1.