Structures de données (listes, piles, files, arbres, graphes) en Terminale
Cours complet, points clés à retenir et exercices d'entraînement de structures de données (listes, piles, files, arbres, graphes) pour les élèves de Terminale. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Listes chaînées : implémentation et opérations
- Piles et files : LIFO, FIFO, applications
- Arbres binaires : parcours (préfixe, infixe, suffixe)
- Arbres binaires de recherche (ABR)
- Graphes : représentation (matrice d'adjacence, liste d'adjacence)
Listes chaînées : implémentation et opérations
Une liste chaînée est une structure où chaque élément (nœud) contient une donnée et un lien vers l'élément suivant. Contrairement aux listes classiques, les éléments ne sont pas stockés de façon contiguë en mémoire.
Exemple
Une chaîne de wagons de train : chaque wagon connaît le wagon suivant, mais ils ne sont pas attachés au même endroit. Pour accéder au dernier wagon, tu dois passer par tous les précédents.
À retenir : Accès en O(n) car il faut traverser depuis le début, mais insertion/suppression en O(1) si on connaît la position.
Piles (LIFO) : dernier entré, premier sorti
Une pile fonctionne sur le principe LIFO (Last In First Out) : le dernier élément ajouté est le premier à être retiré. Les opérations principales sont push (ajouter) et pop (retirer).
Exemple
Une pile d'assiettes à la cantine : tu ajoutes une assiette sur le dessus, et tu retires aussi depuis le dessus. La dernière assiette posée est la première servie.
À retenir : En pile, on n'accède qu'à l'élément du sommet ; pour atteindre un élément au milieu, il faut d'abord retirer tous ceux au-dessus.
Files (FIFO) : premier entré, premier sorti
Une file fonctionne sur le principe FIFO (First In First Out) : le premier élément ajouté est le premier à être retiré. Les opérations sont enqueue (ajouter à l'arrière) et dequeue (retirer l'avant).
Exemple
Une file d'attente à la caisse du supermarché : le premier client arrivé est le premier servi. Les nouveaux clients arrivent par l'arrière et sont traités par l'avant.
À retenir : En file, on ajoute à l'arrière et on retire l'avant ; c'est l'ordre naturel des attentes.
Arbres binaires : structure et parcours
Un arbre binaire est une structure hiérarchique où chaque nœud a au maximum deux enfants (gauche et droit). Le nœud du haut s'appelle la racine.
Exemple
L'arborescence d'une entreprise : le PDG est la racine, chaque manager a deux équipes (gauche et droite), et on descend jusqu'aux employés aux feuilles.
À retenir : Il existe trois façons de parcourir un arbre binaire : préfixe (racine d'abord), infixe (gauche-racine-droit), suffixe (enfants d'abord).
Parcours préfixe, infixe et suffixe
Les trois parcours d'un arbre binaire définissent l'ordre de visite des nœuds : préfixe visite la racine en premier, infixe la visite entre ses enfants, suffixe la visite en dernier.
Exemple
Pour un arbre simple avec racine A, enfant gauche B et enfant droit C : préfixe donne A-B-C, infixe donne B-A-C, suffixe donne B-C-A.
À retenir : Infixe est utilisé pour les expressions mathématiques (donne l'ordre naturel), préfixe pour copier un arbre, suffixe pour le supprimer.
Arbres binaires de recherche (ABR)
Un ABR est un arbre binaire où chaque nœud satisfait : tous les nœuds du sous-arbre gauche sont plus petits, tous ceux du droit sont plus grands. Cela permet une recherche rapide.
Exemple
Un dictionnaire organisé en arbre : le mot au milieu est la racine, les mots avant alphabétiquement vont à gauche, les mots après vont à droite.
À retenir : Un ABR bien équilibré permet une recherche en O(log n), mais un ABR dégénéré (comme une liste) en O(n).
Graphes : matrice d'adjacence et liste d'adjacence
Un graphe est composé de nœuds (sommets) reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). On peut le représenter par une matrice d'adjacence (tableau 2D) ou une liste d'adjacence (dictionnaire).
Exemple
Un réseau social : chaque personne est un nœud, une amitié est une arête. La matrice dit si deux personnes sont amies (1 oui, 0 non), la liste d'adjacence énumère les amis de chaque personne.
À retenir : Matrice d'adjacence : accès rapide O(1) mais espace O(n²). Liste d'adjacence : espace O(n+m) où m est le nombre d'arêtes, plus efficace pour graphes creux.
Les points clés
- Listes chaînées : chaque nœud contient donnée + pointeur vers le suivant ; opérations d'insertion/suppression O(1) mais accès O(n)
- Piles LIFO : push et pop au même endroit (sommet) ; applications : évaluation d'expressions, undo/redo
- Files FIFO : enqueue à l'arrière, dequeue l'avant ; applications : gestion de tâches, files d'attente
- Parcours d'arbres : préfixe (préordre), infixe (ordre symétrique), suffixe (postordre) ; implémentation récursive naturelle
- ABR : propriété d'ordre sur sous-arbres gauche/droit ; permet recherche rapide si équilibré
- Graphes : deux représentations principales ; choix selon densité des arêtes et opérations fréquentes
L'essentiel
Les structures de données organisent les données selon un principe d'accès : listes chaînées pour traversée linéaire, piles et files pour l'ordre, arbres pour la hiérarchie et recherche rapide, graphes pour les relations complexes.
Exercices d'entraînement
Entraîne-toi sur ces exercices, puis fais-toi corriger pas à pas par le tuteur.
Exercice 1
On considère un ABR contenant les valeurs 50, 30, 70, 20, 40, 60, 80. Dessinez l'arbre puis donnez le parcours infixe. Quel est l'intérêt du parcours infixe sur un ABR ?
Corrige cet exercice avec le tuteur →Exercice 2
Représentez le graphe suivant par (1) une matrice d'adjacence, (2) une liste d'adjacence. Sommets : A, B, C, D Arêtes : A-B, A-C, B-C, B-D, C-D Le graphe est-il orienté ou non orienté ? Quel mode de représentation est le plus efficace ici ?
Corrige cet exercice avec le tuteur →