On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?

Réponse : B. 20, 40, 30, 60, 80, 70, 50

La racine est 50 ; son enfant gauche est 30 (avec les enfants 20 et 40) et son enfant droit est 70 (avec les enfants 60 et 80). Le parcours postfixe visite le sous-arbre gauche sous la forme 20, 40, 30 et le sous-arbre droit sous la forme 60, 80, 70, et seulement ensuite la racine 50. 50, 30, 20, 40, 70, 60, 80 est le résultat du parcours préfixe, qui visite chaque nœud en premier, et 20, 30, 40, … celui du parcours infixe. Le parcours postfixe sert quand les enfants doivent être traités d'abord, par exemple pour supprimer un arbre ou pour produire la notation postfixée à partir d'un arbre d'expression.