Numérique et sciences informatiques · Terminale · Algorithmique · 5.º Período

Algorithmes sur les arbres

Parcours d'arbres (préfixe, infixe, suffixe, en largeur). Recherche, insertion et suppression dans un arbre binaire de recherche.

En bref:Les algorithmes sur les arbres sont essentiels pour manipuler efficacement les données hiérarchiques. Ce chapitre se concentre sur les différentes manières de parcourir un arbre (préfixe, infixe, suffixe en profondeur, ou parcours en largeur) et sur les opérations spécifiques aux arbres binaires de recherche (ABR) comme l'insertion et la recherche. Ces algorithmes sont presque toujours récursifs, ce qui en fait une application parfaite du chapitre sur la récursivité.

• Programmes Officiels
• BOEN spécial n°8 du 25 juillet 2019 - Algorithmique
• Compétence : Implémenter les parcours d'un arbre

À propos de ce thème

Les algorithmes sur les arbres sont essentiels pour manipuler efficacement les données hiérarchiques. Ce chapitre se concentre sur les différentes manières de parcourir un arbre (préfixe, infixe, suffixe en profondeur, ou parcours en largeur) et sur les opérations spécifiques aux arbres binaires de recherche (ABR) comme l'insertion et la recherche. Ces algorithmes sont presque toujours récursifs, ce qui en fait une application parfaite du chapitre sur la récursivité.

Comprendre ces parcours permet aux élèves de réaliser des tâches concrètes, comme l'affichage trié d'une base de données ou l'évaluation d'expressions mathématiques. L'apprentissage par la manipulation visuelle est ici primordial. En traçant manuellement les parcours sur des arbres dessinés ou en utilisant des jetons, les élèves intègrent la logique de l'algorithme avant de se confronter à sa complexité spatiale et temporelle.

Questions clés

1. Comment parcourir un arbre en profondeur ?
2. Quel parcours permet d'obtenir les valeurs triées d'un ABR ?
3. Comment insérer un nœud dans un arbre binaire de recherche ?

Attention à ces idées reçues

Idée reçue courante

Confondre les ordres de parcours en profondeur (préfixe, infixe, suffixe).

Ce qu'il faut enseigner à la place

La différence réside uniquement dans le moment où l'on traite la racine. Utiliser une règle visuelle (le contour de l'arbre) où l'on note la valeur à gauche, en bas ou à droite du nœud aide à ne plus se tromper.

Idée reçue courante

Penser que l'insertion dans un ABR donne toujours un arbre équilibré.

Ce qu'il faut enseigner à la place

Si on insère des valeurs déjà triées, l'arbre devient une simple liste (arbre dégénéré). Faire tester cette insertion 'catastrophique' aux élèves leur permet de comprendre l'importance de l'équilibre.

Idées d'apprentissage actif

Galerie marchande

Quel parcours pour quel arbre ?

Plusieurs arbres sont affichés avec une suite de valeurs. Les élèves doivent identifier quel type de parcours (infixe, préfixe...) a généré cette suite et justifier leur réponse.

45 min·Petits groupes

Jeu de simulation

L'insertion dans l'ABR

Un grand arbre est dessiné au sol. Un élève arrive avec un nouveau nombre et doit demander à chaque 'nœud' (un autre élève) s'il doit aller à gauche ou à droite pour trouver sa place.

40 min·Classe entière

Penser-Partager-Présenter

Parcours en largeur vs profondeur

Les élèves comparent l'ordre de visite des nœuds pour les deux types de parcours sur un même arbre. Ils discutent en binômes de l'utilité d'utiliser une file ou une pile pour l'implémentation.

30 min·Binômes

Questions fréquentes

Comment parcourir un arbre en profondeur ?

Il existe trois variantes : préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et suffixe (gauche, droite, racine). Le parcours infixe est particulièrement utile car il donne les valeurs d'un ABR dans l'ordre croissant.

Quelle est la différence entre un parcours en largeur et en profondeur ?

Le parcours en profondeur explore chaque branche le plus loin possible avant de revenir en arrière. Le parcours en largeur explore l'arbre étage par étage, en utilisant une file pour mémoriser les nœuds à visiter.

Comment insérer un nœud dans un arbre binaire de recherche ?

On part de la racine et on compare la valeur à insérer avec le nœud courant : si elle est plus petite, on va à gauche ; si elle est plus grande, on va à droite. On recommence jusqu'à trouver une place libre (une feuille).

Pourquoi le dessin est-il crucial pour apprendre les algorithmes d'arbres ?

Les algorithmes d'arbres sont intrinsèquement spatiaux. Dessiner l'arbre et tracer physiquement le chemin de l'algorithme permet de 'voir' la récursion en action. Cela transforme une suite d'appels de fonctions abstraits en un mouvement logique compréhensible, facilitant ensuite l'écriture du code Python.