💻 NSITleTerminaleSans inscription

Arbres et ABR — parcours et recherche

Programme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte

NSI terminale : vocabulaire des arbres binaires, taille et hauteur, parcours préfixe, infixe, suffixe et en largeur, arbres binaires de recherche, recherche et insertion.

La règle d'or

Un arbre binaire organise des données hiérarchiques ; un ABR range à gauche les plus petites valeurs et à droite les plus grandes, ce qui accélère la recherche.

L'erreur que tout le monde fait

Confondre parcours préfixe et infixe.

Le préfixe traite le nœud avant ses fils, l'infixe entre le fils gauche et le fils droit.

Repérer à quel moment on traite le nœud.

Notions à maîtriser

  • arbre binaire
  • arbre binaire de recherche
  • parcours
  • récursivité
  • NSI terminale
  • NSI
  • Python
1

Réviser

L'arborescence des dossiers, l'arbre généalogique, le tableau d'un tournoi : beaucoup de données sont hiérarchiques. Les arbres binaires les représentent, et les arbres binaires de recherche permettent de retrouver une valeur très vite.

1Vocabulaire

Définition

arbre binaire — Structure formée de nœuds ; chaque nœud a au plus deux fils (gauche et droit). Le nœud de départ est la racine, un nœud sans fils est une feuille.

Définition

taille et hauteur — La taille est le nombre de nœuds ; la hauteur est le nombre de nœuds (ou d'arêtes, selon la convention annoncée) sur la plus longue branche de la racine à une feuille.

2Parcours

Règle

Préfixe : nœud, gauche, droit. Infixe : gauche, nœud, droit. Suffixe : gauche, droit, nœud. En largeur : niveau par niveau (avec une file). Les parcours en profondeur s'écrivent naturellement de façon récursive.

3Arbre binaire de recherche

Définition

ABR — Arbre binaire où, pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit supérieures.

Règle

Recherche et insertion : comparer à la racine et descendre à gauche ou à droite ; le coût dépend de la hauteur. Le parcours infixe d'un ABR donne les valeurs triées.

Exemple

Insère 8, 3, 10, 1, 6 dans un ABR vide.

  1. 8 est la racine.
  2. 3 < 8 : à gauche ; 10 > 8 : à droite.
  3. 1 < 8 puis 1 < 3 : gauche de 3 ; 6 < 8 puis 6 > 3 : droite de 3.

On descend en comparant à chaque nœud ; le parcours infixe donnera 1, 3, 6, 8, 10.

Piège

Confondre parcours préfixe et infixe.

Pourquoi — Le préfixe traite le nœud avant ses fils, l'infixe entre le fils gauche et le fils droit.

Le réflexe — Repérer à quel moment on traite le nœud.

Écrire un parcours récursif

  1. Traiter le cas de l'arbre vide.
  2. Appeler la fonction sur le sous-arbre gauche.
  3. Traiter le nœud au moment voulu (avant, entre, après).
  4. Appeler la fonction sur le sous-arbre droit.
  • ▢Ai-je défini le vocabulaire ?
  • ▢Mon code est-il testé sur un exemple ?
  • ▢Ai-je traité les cas limites ?
  • ▢Ai-je justifié la complexité ou le résultat ?

L'essentiel en 3 points

  • ·Racine, nœud, feuille ; taille, hauteur (convention à préciser).
  • ·Parcours préfixe, infixe, suffixe, en largeur (file).
  • ·ABR : gauche < nœud < droite ; coût lié à la hauteur ; infixe = valeurs triées.
2

Imprimer

Fiche PDF — Arbres et ABR — parcours et recherche

Gratuit · sans compte

Trois documents à imprimer, 4 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.

Au sommaire du cours

  1. 1. Vocabulaire
  2. 2. Parcours
  3. 3. Arbre binaire de recherche

Conforme au programme officiel · version 2026.2.

3

Exercices corrigés

1

Vocabulaire

Connaître
  1. a.Définis : racine, feuille, hauteur.
›Voir le corrigé
  1. Nœud sans parent.
  2. Nœud sans fils.
  3. Longueur de la plus longue branche (convention précisée).
2

Parcours

Analyser
  1. a.Arbre : racine A, fils B (gauche) et C (droit). Donne les trois parcours.
›Voir le corrigé
  1. Préfixe A B C ; infixe B A C ; suffixe B C A.
3

ABR

Analyser
  1. a.Combien de comparaisons pour trouver 6 dans l'ABR de l'exemple ?
›Voir le corrigé
  1. Trois : 8, 3, 6.
4

Taille

Programmer
  1. a.Écris taille(a) récursivement.
›Voir le corrigé
  1. if a is None: return 0 puis return 1 + taille(a.gauche) + taille(a.droit).
5

Tri

Analyser
  1. a.Pourquoi le parcours infixe d'un ABR donne-t-il une liste triée ?
›Voir le corrigé
  1. On visite d'abord les plus petites (gauche), puis le nœud, puis les plus grandes (droite).
6

Déséquilibre

Analyser
  1. a.Que devient un ABR où l'on insère 1, 2, 3, 4, 5 dans l'ordre ?
›Voir le corrigé
  1. Une branche unique, de hauteur 5 : la recherche devient aussi lente qu'une liste.

Ce qui rapporte des points, ce qui en coûte

  • Vocabulaire2 ptsPerdu si : Définitions floues
  • Code juste et testé2 ptsPerdu si : Cas limites oubliés
  • Justification1 ptPerdu si : Résultat non expliqué
4

La méthode

Écrire un parcours récursif

  1. 1

    Traiter le cas de l'arbre vide.

  2. 2

    Appeler la fonction sur le sous-arbre gauche.

  3. 3

    Traiter le nœud au moment voulu (avant, entre, après).

5

Se tester

NSITerminale
Question 1
Quelle est la complexité de la recherche dans un ABR équilibré à nn nœuds ?

Aucun compte requis — réponds, la correction s'affiche aussitôt.

Signaler une erreur

Garder ta progression ?

Tes réponses sont déjà comptées dans ce navigateur. Un compte gratuit les conserve d'un appareil à l'autre et débloque le suivi de tes points faibles.

Avec un compte gratuit

La fiche et les exercices restent ouverts. Le compte, lui, te dit quoi travailler.

1 · Ta séance du jour

Arbres et ABR — parcours et recherche

3 minutes, sur ce qui résiste

Commencer

2 · Ta progression, vue aussi par tes parents

  • Maths72 %
  • Français58 %
  • Histoire-géo41 %
  • SVT64 %

3 · Tes erreurs, rejouées

  • Ta réponse, et où elle déraille
  • La bonne, avec l'explication
Rejouer

Gratuit, sans carte bancaire. Les chiffres ci-dessus sont un exemple d'affichage.

Questions fréquentes

Arbres et ABR — parcours et recherche : c'est en quelle classe ?

Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.

Que faut-il savoir sur Arbres et ABR — parcours et recherche ?

NSI terminale : vocabulaire des arbres binaires, taille et hauteur, parcours préfixe, infixe, suffixe et en largeur, arbres binaires de recherche, recherche et insertion. Les notions à maîtriser sont : arbre binaire, arbre binaire de recherche, parcours, récursivité, NSI terminale, NSI.

Où télécharger la fiche PDF de Arbres et ABR — parcours et recherche ?

Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 4 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.

Le corrigé de Arbres et ABR — parcours et recherche est-il fourni ?

Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.

Arbres et ABR — parcours et recherche peut-il tomber au Baccalauréat ?

Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.

Comment réviser Arbres et ABR — parcours et recherche efficacement ?

Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.

Faut-il un compte pour s'entraîner sur Arbres et ABR — parcours et recherche ?

Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.

Notions voisines

Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.

Un ordinateur pour le lycée

Python dès la seconde, exposés, espace numérique de travail : un portable qui suit jusqu'au bac.

  • Petit budget, 16 Go

    Acer Aspire Go 15 (Ryzen 5 7430U, 16 Go, 512 Go)

  • Le prix de référence

    HP 15 (Core i5-1334U, 16 Go, 512 Go)

  • Léger, pour le cartable

    Acer Swift Go 14 AI

En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.

Pour réviser le bac

Les annales de la matière, et le grand oral.

  • Grand oral

    Prépabac Le Grand Oral, terminale générale, bac 2027

    Hatier

  • Réviser la philosophie

    Prépabac philosophie, terminale générale, bac 2027

    Hatier

En tant que Partenaire Amazon, ProgresSchool réalise un bénéfice sur les achats remplissant les conditions requises.