Un arbre binaire est une structure hiérarchique où chaque nœud a au maximum deux enfants, appelés left et . Il a une seule ; les nœuds sans enfants sont des . C'est la base des arbres de recherche binaires (BST), des tas, et des arbres d'expression.
right 1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
Un parcours level-order (BFS) utilise une file d'attente et visite l'arbre en profondeur.
| Parcours | Ordre | Utilisation courante |
|---|---|---|
| Inorder | G, N, D | sortie triée d'un BST |
| Preorder | N, G, D | copie/sérialisation d'un arbre |
| Postorder | G, D, N | suppression d'un arbre, évaluation d'expression |
| Level-order | par profondeur | BFS, plus court chemin dans un arbre |
Chaque parcours visite chaque nœud une fois → temps O(n), espace pile O(h) où h est la hauteur.
Les arbres binaires modélisent naturellement des données hiérarchiques (systèmes de fichiers, arbres d'analyse syntaxique, arbres de décision) et sont à la base de structures de recherche et de tri efficaces.
Maîtriser les quatre parcours est essentiel — la plupart des problèmes d'interview sur les arbres sont une variation de l'un d'entre eux.