Arbre binaire
Dernière mise à jour
Un arbre binaire est une hiérarchie où chaque nœud possède au plus deux enfants, appelés enfant gauche et enfant droit. Le nœud supérieur est la racine, les nœuds sans enfant sont des feuilles, et le nombre d'arêtes de la racine jusqu'à la feuille la plus profonde est la hauteur de l'arbre. Contrairement à un arbre binaire de recherche, un arbre binaire simple n'a aucune règle d'ordre : ce n'est que la forme. Appuyez sur lecture ci-dessus pour voir un arbre se remplir niveau par niveau, puis être parcouru en infixe (gauche, nœud, droite).
Les arbres binaires sont à la base de nombreuses structures : arbres binaires de recherche, tas, arbres d'expression et bien d'autres. Les parcours visitent chaque nœud dans un ordre défini : infixe, préfixe et postfixe sont les trois parcours en profondeur, chacun utile pour des tâches différentes.
Terminologie
| Terme | Signification |
|---|---|
| Racine | Le nœud supérieur, sans parent |
| Feuille | Un nœud sans enfant |
| Hauteur | Le plus long chemin racine-feuille (en arêtes) |
| Profondeur | Distance d'un nœud par rapport à la racine |
| Complet | Tous les niveaux pleins sauf peut-être le dernier, rempli de gauche à droite |
Les trois parcours en profondeur
| Parcours | Ordre | Usage courant |
|---|---|---|
| Infixe | Gauche, nœud, droite | Sortie triée d'un BST |
| Préfixe | Nœud, gauche, droite | Copier / sérialiser un arbre |
| Postfixe | Gauche, droite, nœud | Supprimer / évaluer un arbre |
Exemple détaillé
Parcours infixe de l'arbre construit à partir de [4, 2, 6, 1, 3, 5] (rempli niveau par niveau) :
| Étape | Au nœud | Action |
|---|---|---|
| 1 | 4 | Récursion dans le sous-arbre gauche de 4 avant de le visiter |
| 2 | 2 | Récursion dans le sous-arbre gauche de 2 avant de le visiter |
| 3 | 1 | Feuille, pas d'enfant gauche : on visite 1, sortie [1] |
| 4 | 2 | Gauche terminée : on visite 2, sortie [1, 2], puis récursion à droite |
| 5 | 3 | Feuille : on visite 3, sortie [1, 2, 3] |
| 6 | 4 | Sous-arbre gauche terminé : on visite 4, sortie [1, 2, 3, 4], puis récursion à droite |
| 7 | 5 | Enfant gauche de 6, une feuille : on visite 5, sortie [1, 2, 3, 4, 5] |
| 8 | 6 | Gauche terminée, pas d'enfant droit : on visite 6, sortie [1, 2, 3, 4, 5, 6] |
Quand utiliser un arbre binaire
| À utiliser quand | À éviter quand |
|---|---|
| Vous devez modéliser des données intrinsèquement hiérarchiques (systèmes de fichiers, arbres d'expression, DOM) | Les données sont plates et une liste ou un tableau suffirait : un arbre ne fait qu'ajouter de la surcharge |
| Vous voulez des opérations ordonnées et pouvez le maintenir équilibré (un BST ou un arbre auto-équilibré) | Vous avez besoin d'une recherche par clé en O(1) en moyenne : une table de hachage surpasse tout arbre |
| Vous devez traiter des données structurées en infixe, préfixe ou postfixe | Les nœuds sont insérés en ordre croissant dans un BST non équilibré : il dégénère en une liste O(n) |
| Les requêtes par plage ou l'itération ordonnée comptent, ce que les tables de hachage ne fournissent pas | La mémoire est limitée : chaque nœud porte deux pointeurs vers ses enfants en plus des données |
Code de Binary Tree
Une implémentation propre et exécutable de Binary Tree en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Binary Tree en Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Code de Binary Tree en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Code de Binary Tree en Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Code de Binary Tree en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Code de Binary Tree en C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}FAQ sur les arbres binaires
Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?
Un arbre binaire limite simplement chaque nœud à au plus deux enfants, sans aucun ordre. Un arbre binaire de recherche ajoute la règle selon laquelle tout dans le sous-arbre gauche est plus petit et tout dans le sous-arbre droit est plus grand, ce qui rend la recherche rapide.
Qu'est-ce qu'un parcours infixe ?
Le parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit, de façon récursive. Pour un arbre binaire de recherche, cela produit les valeurs en ordre croissant, c'est pourquoi c'est le parcours le plus courant à démontrer.
Qu'est-ce qu'un arbre binaire complet ?
Un arbre binaire complet a tous ses niveaux entièrement remplis sauf peut-être le dernier, qui est rempli de gauche à droite. Cette forme permet de stocker l'arbre de manière compacte dans un tableau (sans pointeurs vers les enfants), ce qui est la façon dont les tas binaires sont implémentés.
Quand devrais-je utiliser un arbre binaire plutôt qu'un tableau ou une table de hachage ?
Optez pour un arbre lorsque vos données sont naturellement hiérarchiques ou lorsque vous avez besoin d'opérations ordonnées comme les requêtes par plage et l'itération triée, ce que les tables de hachage ne peuvent pas offrir. Si vous n'avez besoin que d'une recherche rapide par clé sans ordre, l'accès moyen en
O(1) d'une table de hachage surpasse un arbre, et pour des données plates un tableau est plus simple et plus favorable au cache.Quelle est la différence entre la hauteur et la profondeur d'un arbre binaire ?
La profondeur se mesure depuis la racine vers le bas jusqu'à un nœud précis : le nombre d'arêtes sur le chemin de la racine à ce nœud. La hauteur se mesure depuis un nœud vers le bas jusqu'à sa feuille la plus profonde, de sorte que la hauteur de tout l'arbre est la profondeur de son nœud le plus profond. Un arbre à un seul nœud a une hauteur de
0, et son unique nœud a aussi une profondeur de 0.Pourquoi un arbre binaire non équilibré est-il si peu performant ?
Rechercher, insérer et supprimer dans un arbre binaire de recherche coûtent
O(h), où h est la hauteur. Lorsque les clés sont insérées en ordre croissant, l'arbre devient une ligne droite, donc h croît jusqu'à n et chaque opération dégénère en O(n), pas mieux qu'une liste chaînée. Les arbres auto-équilibrés comme les arbres AVL ou rouge-noir maintiennent la hauteur à O(log n) pour éviter cela.Ressources associées
Plus de visualisations
