L'algorithme itératif du parcours en profondeur préfixe d'un arbre binaire est presque le même que celui du parcours en largeur, sauf qu'il utilise une pile et qu'il faut d'abord empiler le fils droit. 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
traiter s
si s possède un fils droit :
empiler ce fils droit sur P
si s possède un 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 prefixe(A):
si A est non vide :
traiter la racine de A
prefixe(sous-arbre gauche de A)
prefixe(sous-arbre droit de A)
Dans cet exercice, le parcours est toujours le même : le parcours préfixe. L'arbre est aléatoire.
Cliquez sur les nœuds de l'arbre binaire en suivant l'ordre de traitement du parcours préfixe.
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".