Quelle est la différence entre un parcours préfixe, infixe et suffixe d’un arbre ?

Réponse courte

Ces parcours en profondeur visitent les mêmes nœuds, mais placent le traitement de la racine à des moments différents : avant les sous-arbres en préfixe, entre eux en infixe, après eux en suffixe.

Comprendre

L’ordre de la racine change

Pour chaque nœud, on parcourt entièrement le sous-arbre gauche puis le droit. En préfixe, on traite la racine avant les deux appels récursifs : racine, gauche, droit. En infixe, on la traite entre eux : gauche, racine, droit. En suffixe, on l’ajoute après : gauche, droit, racine. Le traitement peut ajouter la clé dans une liste plutôt que l’afficher.

Un exemple concret

Considère un arbre de racine 8, avec 3 à gauche et 10 à droite ; 3 a pour enfants 1 et 6, et 10 a pour enfant droit 14. Le préfixe donne 8, 3, 1, 6, 10, 14. L’infixe donne 1, 3, 6, 8, 10, 14. Le suffixe donne 1, 6, 3, 14, 10, 8. Dans un arbre binaire de recherche à clés distinctes, l’infixe produit les clés dans l’ordre croissant.

Bien distinguer les structures

Ces trois ordres sont des parcours en profondeur ; le parcours en largeur visite plutôt niveau par niveau avec une file. Un arbre binaire quelconque ne garantit pas que son infixe soit croissant : la propriété d’ABR est nécessaire. Pour appliquer les parcours à un arbre vide, l’appel ne traite aucun nœud.

Exemples

  • Pour un nœud 2 avec 1 à gauche et 3 à droite, le préfixe vaut 2, 1, 3 ; l’infixe 1, 2, 3 ; le suffixe 1, 3, 2.
  • Dans l’arbre décrit de racine 8, le suffixe traite 1 et 6 avant 3, puis 14 et 10 avant 8.
  • Un arbre quelconque de racine 2 avec un enfant gauche 5 donne l’infixe 5, 2 : il n’est pas croissant, car ce n’est pas un ABR.

Pièges fréquents

  • Lire préfixe comme un parcours qui visite seulement la racine en premier, sans parcourir ensuite chaque sous-arbre récursivement, omet des nœuds.
  • Supposer que tout parcours infixe est croissant oublie que seul un ABR impose l’ordre des clés entre sous-arbres.

Pourquoi ça marche

La position du traitement de la racine par rapport aux deux appels récursifs suffit à définir l’ordre complet dans chaque sous-arbre.

Et maintenant ?

Questions proches

← Toutes les questions-réponses