Pour l'algorithme itératif du parcours en profondeur infixe d'un arbre binaire il faut marquer des nœuds afin de pouvoir les traiter plus tard, sans les traiter deux fois. L'algorithme peut être écrit ainsi :
créer une pile vide P
empiler la racine de l'arbre sur P
tant que P est non vide, faire :
s ← dépiler P
si s possède un fils droit qui n'est pas marqué :
marquer ce fils droit
empiler ce fils droit sur P
si s possède un fils gauche qui n'est pas marqué :
empiler s sur P
marquer ce fils gauche
empiler ce fils gauche sur P
sinon :
traiter s
Ici s ← dépiler P signifie qu'on affecte le sommet de la pile P à s et que cette valeur est retirée de la pile.
L'algorithme récursif est plus court. Il peut être écrit ainsi :
Fonction infixe(A):
si A est non vide :
infixe(sous-arbre gauche de A)
traiter la racine de A
infixe(sous-arbre droit de A)
Dans cet exercice, le parcours est toujours le même : le parcours infixe. L'arbre est aléatoire.
Cliquez sur les nœuds de l'arbre binaire en suivant l'ordre de traitement du parcours infixe.
Vous pouvez revenir en arrière en cliquant à nouveau sur le dernier nœud sélectionné, ou supprimer tout votre parcours avec le bouton "annuler".