Qu'est-ce qu'un parcours d'arbre ?
Un arbre binaire est une structure où chaque nœud possède au plus deux enfants : un fils gauche et un fils droit. Le nœud supérieur s'appelle la racine.
Un parcours consiste à visiter tous les nœuds exactement une fois dans un ordre précis. Les trois parcours classiques diffèrent par le moment où l'on « lit » la racine d'un sous-arbre par rapport à ses fils.
Les trois parcours
① Préfixe
- Visiter la racine
- Parcourir le sous-arbre gauche
- Parcourir le sous-arbre droit
Racine · Gauche · Droit
② Infixe
- Parcourir le sous-arbre gauche
- Visiter la racine
- Parcourir le sous-arbre droit
Gauche · Racine · Droit
③ Postfixe
- Parcourir le sous-arbre gauche
- Parcourir le sous-arbre droit
- Visiter la racine
Gauche · Droit · Racine
Technique de l'enrobage
Il existe une technique graphique simple pour lire les trois parcours d'un coup : on enrobe l'arbre d'un trait continu qui longe tous les nœuds. Chaque nœud est alors frôlé trois fois : à gauche, en dessous et à droite. On note le nœud lors du passage qui correspond au parcours souhaité.
Préfixe
On note le nœud au passage par sa gauche
Infixe
On note le nœud au passage par son dessous
Postfixe
On note le nœud au passage par sa droite
Exemple interactif
Étape 0 / 0
Préfixe
· · · · · · ·
Infixe
· · · · · · ·
Postfixe
· · · · · · ·
Astuce mnémotechnique : le parcours infixe d'un arbre binaire de recherche donne toujours les valeurs dans l'ordre croissant. C'est pourquoi on l'appelle aussi parcours symétrique.
Pour retenir l'ordre des trois parcours : imaginez la position du Racine dans RGD (pré), GRD (in), GDR (post) — la racine se déplace de gauche à droite !
Pour retenir l'ordre des trois parcours : imaginez la position du Racine dans RGD (pré), GRD (in), GDR (post) — la racine se déplace de gauche à droite !