33. Algorithmes de Parcours d'Arbre (Tree Traversal)

Le parcours est le processus de visite de chaque nœud de l'arbre exactement une fois. Les trois principaux parcours en profondeur sont définis par le moment où le nœud racine est visité par rapport à ses enfants.

Soit N le Nœud, L le Sous-arbre Gauche et R le Sous-arbre Droit.

1. Parcours Inorder (L N R)

• Visiter le Sous-arbre Gauche, puis visiter le Nœud, puis visiter le Sous-arbre Droit.
• Résultat : Pour un BST, le parcours Inorder donne les éléments dans l'ordre trié.

2. Parcours Preorder (N L R)

• Visiter le Nœud, puis le Sous-arbre Gauche, puis le Sous-arbre Droit.
• Résultat : Utilisé pour créer une copie de l'arbre ou pour obtenir l'expression préfixée de l'arbre.

3. Parcours Postorder (L R N)

• Visiter le Sous-arbre Gauche, puis le Sous-arbre Droit, puis visiter le Nœud.
• Résultat : Utilisé pour supprimer l'arbre (doit supprimer les enfants avant de supprimer le parent) ou pour les expressions postfixées.