Parcourir un arbre binaire

Fixer un arbre et une convention

Utilisons l’arbre de racine 8, avec à gauche 3 et à droite 10. Le nœud 3 possède les enfants 1 et 6 ; le nœud 10 possède uniquement un enfant droit 14. Pour tous les parcours présentés, gauche précède droite lorsque deux choix sont possibles.

Visiter signifie ici écrire l’étiquette du nœud dans le résultat. Traverser une structure peut demander d’entrer dans un sous-arbre, d’y réaliser plusieurs visites puis de revenir à son parent. Le moment où l’on écrit le parent donne trois parcours récursifs fondamentaux : préfixe, infixe et suffixe.

Une façon de travailler sur papier consiste à écrire trois emplacements autour de chaque nœud : avant le parcours gauche, entre gauche et droite, après le parcours droit. Choisir le même emplacement pour toutes les visites produit respectivement préfixe, infixe ou suffixe. Il ne faut pas changer de règle en descendant.

Placer la racine avant, entre ou après

En préfixe, on visite la racine, puis tout le sous-arbre gauche, puis tout le sous-arbre droit. Notre résultat est 8,3,1,6,10,14. En infixe, on parcourt d’abord le sous-arbre gauche, puis on visite la racine, puis le sous-arbre droit : 1,3,6,8,10,14.

En suffixe, on traite les deux sous-arbres avant leur racine : 1,6,3,14,10,8. Les mots « gauche » et « droite » désignent ici des parcours complets, pas seulement les enfants immédiats. Appliquer une règle une seule fois à la racine ne suffit donc pas ; la même règle est répétée récursivement dans chaque sous-arbre.

Le code suivant représente chaque nœud par (étiquette, gauche, droite), avec None pour le vide. Le paramètre ordre fixe la position du seul ajout au résultat. Les trois branches ne s’exécutent pas ensemble : une seule correspond à l’ordre choisi.

def parcours(arbre, ordre="in"):
    assert ordre in ("pre", "in", "post")
    resultat = []
    def visiter(a):
        if a is None:
            return
        if ordre == "pre":
            resultat.append(a[0])
        visiter(a[1])
        if ordre == "in":
            resultat.append(a[0])
        visiter(a[2])
        if ordre == "post":
            resultat.append(a[0])
    visiter(arbre)
    return resultat

Explorer niveau par niveau avec une file

Le parcours en largeur visite d’abord la racine, puis ses enfants, puis leurs enfants. Pour notre arbre, cela donne 8,3,10,1,6,14. Une file conserve les nœuds découverts dont les enfants n’ont pas encore été ajoutés. On défile un nœud, on le visite et on enfile ses enfants existants, gauche puis droite.

La file respecte l’ordre d’arrivée : les nœuds d’un niveau ont été ajoutés avant ceux du suivant. Remplacer cette file par une pile change le comportement et ne conserve pas cette progression par niveaux. Les choix de structure et d’ordre d’ajout doivent être explicités pour obtenir une trace reproductible.

Choisir un parcours pour un besoin

Le suffixe convient lorsque le résultat d’un parent dépend de résultats déjà calculés pour ses enfants, comme une expression arithmétique représentée par un arbre. Le préfixe peut servir à décrire une hiérarchie en annonçant le parent avant son contenu. La largeur permet de travailler par niveaux.

Un parcours infixe d’un arbre binaire quelconque ne trie pas ses étiquettes. Il donne un ordre croissant lorsque l’arbre respecte la propriété d’un arbre binaire de recherche avec une convention cohérente sur les doublons. Les quatre parcours visitent chaque nœud une fois, mais ne demandent pas nécessairement la même mémoire auxiliaire.

Exemple suivi : une expression arithmétique

Représentons (2+3)×4 par une racine ×, un enfant gauche + portant les feuilles 2 et 3, et un enfant droit 4. Le préfixe donne ×,+,2,3,4 : chaque opération est annoncée avant ses opérandes. Le suffixe donne 2,3,+,4,× : quand + arrive, ses deux opérandes sont déjà disponibles ; quand × arrive, la somme et 4 le sont également.

Pour évaluer le suffixe avec une pile, on empile 2 puis 3, on les remplace par 5 lors de +, on empile 4 puis on remplace 5 et 4 par 20 lors de ×. L’ordre infixe donne 2,+,3,×,4, mais des parenthèses sont nécessaires pour retrouver sans ambiguïté l’expression originale. Le seul ordre des étiquettes n’exprime pas toujours toute la structure : annoncer une convention de représentation est indispensable.

Exemple suivi : observer la file et la mémoire

Sur l’arbre A avec enfants B et C, B ayant enfants D et E, et C ayant un seul enfant F, la file débute par [A]. Après A elle vaut [B,C] ; après B, [C,D,E] ; après C, [D,E,F]. Le résultat déjà écrit est alors A,B,C. Les nœuds D et E ne passent pas avant C, même si on les découvre pendant le traitement de B.

Une chaîne n’a qu’un nœud à chaque niveau, donc la file reste petite. Un arbre très large peut au contraire conserver beaucoup de nœuds simultanément. Pour un parcours récursif en profondeur, la pile d’appels suit principalement un chemin et dépend de la hauteur. Tous les parcours visitent le même nombre de nœuds, mais le stockage temporaire diffère. Dans l’atelier, les visites futures sont masquées : utilisez le dessin et la règle du parcours pour prévoir la prochaine étiquette.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Visiter seulement les enfants immédiats avant de passer à la suite.

Chaque sous-arbre est parcouru intégralement selon la même règle.

Confondre profondeur et largeur.

La largeur utilise une file pour préserver les niveaux.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Métropole · Jour 1 : Plateforme de débats : arbres d’arguments et base relationnelle
• Bac 2026 · Centres étrangers groupe 1 · Jour 1 : Classement d’athlètes : tri par sélection et ABR
• Bac 2026 · Amérique du Nord · Jour 1 : Puissance 4 : scores, arbre de coups et min-max
• Bac 2026 · Amérique du Nord · Jour 2 : Tennis : objets, tri et arbre du tournoi

Le prochain pas

• Arbres binaires de recherche : rechercher et insérer
• Parcourir un graphe en profondeur : DFS

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.