Introduction : Pourquoi ces structures sont-elles essentielles ?
Si tu es en spécialité NSI, tu as déjà manipulé des listes, des dictionnaires ou des tuples. Ce sont des structures linéaires. Mais le monde qui nous entoure est rarement linéaire ! Pense à l'arbre généalogique de ta famille, au réseau des métros d'une grande ville ou à la structure des dossiers sur ton ordinateur. Pour modéliser ces relations complexes, on a besoin de structures plus évoluées : les arbres et les graphes. Maîtriser ces concepts est un passage obligé pour le bac et pour comprendre l'informatique fondamentale. Prêt à explorer ces nouveaux territoires ?
Les arbres binaires : la hiérarchie organisée
Un arbre est une structure de données hiérarchique et non linéaire. L'élément le plus haut est la racine. Chaque élément est un nœud, et les nœuds sont reliés par des arêtes. Un nœud sans enfant est une feuille.
Qu'est-ce qu'un arbre binaire ?
Un arbre binaire est un cas particulier où chaque nœud possède au maximum deux enfants, traditionnellement appelés enfant gauche et enfant droit. Cette contrainte simplifie beaucoup d'opérations et d'algorithmes.
À retenir : Dans un arbre binaire, l'ordre des enfants (gauche/droite) a une importance ! Ce n'est pas la même chose d'insérer une valeur à gauche ou à droite.
Implémentation en Python (Approche POO)
La façon la plus intuitive de représenter un arbre binaire en NSI est d'utiliser la Programmation Orientée Objet. On définit une classe Noeud.
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
# Création d'un petit arbre
racine = Noeud("Racine")
racine.gauche = Noeud("Sous-arbre gauche")
racine.droite = Noeud("Sous-arbre droit")
racine.gauche.gauche = Noeud("Feuille gauche")
Les parcours d'arbres : explorer méthodiquement
Parcourir un arbre, c'est visiter chacun de ses nœuds une et une seule fois. Il existe trois principaux ordres de parcours récursifs essentiels en NSI :
- Parcours préfixe (ou pré-ordre) : On traite la racine, puis le sous-arbre gauche, puis le sous-arbre droit. Racine - Gauche - Droit.
- Parcours infixe : On traite le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Gauche - Racine - Droit. Pour un arbre binaire de recherche, ce parcours donne les valeurs dans l'ordre croissant !
- Parcours postfixe (ou post-ordre) : On traite le sous-arbre gauche, puis le sous-arbre droit, puis la racine. Gauche - Droit - Racine. Utile pour évaluer des expressions arithmétiques.
Les graphes : modéliser les relations complexes
Un graphe est une structure encore plus générale qu'un arbre. Il est constitué d'un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs). Contrairement à un arbre, il n'y a pas de notion de racine, et il peut y avoir des cycles (des boucles).
Deux grandes familles de graphes
- Graphe non orienté : Les arêtes n'ont pas de sens. Comme un réseau social d'amis (si Alice est amie avec Bob, c'est réciproque).
- Graphe orienté (digraphe) : Les arêtes, appelées arcs, ont un sens. Comme les abonnements sur un réseau social (Alice peut suivre Bob sans que Bob ne suive Alice).
Comment représenter un graphe en Python ?
Il existe deux méthodes principales au programme de NSI :
- Matrice d'adjacence : Une matrice (liste de listes) de taille n x n (n = nombre de sommets). L'élément à la ligne i, colonne j vaut 1 (ou le poids) s'il y a une arête du sommet i vers j, 0 sinon. Efficace pour les graphes denses.
- Liste d'adjacence : Un dictionnaire où les clés sont les sommets, et les valeurs sont des listes des sommets voisins. Plus économe en mémoire pour les graphes peu denses (creux). C'est souvent la représentation privilégiée.
# Exemple de liste d'adjacence pour un graphe non orienté
graphe = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B"],
"D": ["B"]
}
# Cela signifie : A est relié à B et C, B est relié à A, C et D, etc.
Algorithmes fondamentaux sur les graphes
Une fois ton graphe modélisé, tu vas vouloir l'explorer ou y chercher des informations.
Parcours en profondeur (DFS - Depth-First Search)
Le principe est d'explorer un chemin le plus loin possible avant de revenir en arrière (backtracking). On utilise souvent une pile (implicite avec la récursivité) ou explicite. Idéal pour trouver un chemin, détecter des cycles.
Parcours en largeur (BFS - Breadth-First Search)
Ici, on explore tous les voisins d'un sommet avant de passer aux voisins des voisins. On utilise une file (FIFO). Cet algorithme est parfait pour trouver le plus court chemin (en nombre d'arêtes) dans un graphe non pondéré.
Astuce NSI : Pour retenir la différence, pense à DFS comme "Descends d'abord !" (comme dans un labyrinthe, tu prends un couloir jusqu'au bout). Pour BFS, pense à "Étale-toi !" (comme une tache d'encre qui s'étend de manière uniforme).
Applications concrètes : où les retrouve-t-on ?
Ces structures ne sont pas que des exercices abstraits ! Elles sont partout en informatique :
- Arbres binaires de recherche (ABR) : Pour stocker des données de manière triée et permettre une recherche, insertion, suppression rapides (complexité moyenne O(log n)). C'est le principe derrière de nombreuses structures comme les
setoudicten Python. - Arbres d'expression : Pour évaluer ou compiler des expressions mathématiques (comme (3 + 4) * 5).
- Graphes et réseaux : Le web est un gigantesque graphe orienté (les pages sont les sommets, les liens hypertextes sont les arcs). Les algorithmes de recommandation d'amis, de calcul d'itinéraire (Google Maps), ou même le fonctionnement d'un réseau neuronal simple reposent sur la théorie des graphes.
- Jeux vidéo : Les arbres sont utilisés pour l'IA (arbres de décision, arbres de comportement) et les graphes pour la génération de cartes ou le pathfinding (algorithme A*).
Conclusion et conseils pour les révisions
Les arbres et les graphes sont des pierres angulaires de l'informatique. En NSI, on attend de toi que tu :
- Comprennes les concepts (nœud, arête, racine, feuille, cycle, etc.).
- Saches les implémenter en Python avec des classes ou des dictionnaires/listes.
- Maîtrises les algorithmes de parcours (préfixe/infixe/postfixe pour les arbres, DFS/BFS pour les graphes) et saches les coder de manière récursive ou itérative.
- Sois capable de choisir la bonne structure pour modéliser un problème simple.
Pour t'entraîner, commence par coder un arbre binaire simple et implémente les trois parcours. Ensuite, modélise le réseau de ton lycée (les salles sont des sommets, les couloirs des arêtes) et écris un algorithme BFS pour trouver le chemin le plus court entre la cantine et la salle d'informatique ! Bon courage pour tes révisions.
