Pour l'algorithme itératif du parcours en profondeur suffixe (ou postfixe) d'un arbre binaire, on laisse le nœud courant dans la pile, il sera traité après ses fils s'il en a. 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
empiler s sur P
si s ne possède aucun fils qui n'est pas marqué :
traiter 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é :
s sur P
marquer ce fils gauche
empiler ce fils gauche sur P
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 suffixe(A):
si A est non vide :
suffixe(sous-arbre gauche de A)
suffixe(sous-arbre droit de A)
traiter la racine de A
Dans cet exercice, le parcours est toujours le même : le parcours suffixe. L'arbre est aléatoire.
Cliquez sur les nœuds de l'arbre binaire en suivant l'ordre de traitement du parcours suffixe.
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".