Ce que vous allez apprendre
- Définir racine, enfants, feuilles, profondeur et hauteur.
- Un arbre binaire possède au plus un enfant gauche et un enfant droit par nœud.
- La profondeur compte les arêtes depuis la racine ; la hauteur est la plus grande profondeur.
Prérequis. Avoir étudié les chapitres DSA précédents ; connaître liens, piles et appels récursifs.
Partir d’un besoin
Une arborescence de dossiers possède des relations parent-enfant. Une simple suite de noms ne montre pas directement ces liens. Un arbre représente une hiérarchie sans cycle.
Définir la structure et les conventions
Un arbre enraciné possède une racine sans parent ; chaque autre nœud possède exactement un parent et est accessible depuis la racine. Un nœud sans enfant est une feuille. La profondeur compte les arêtes depuis la racine, de profondeur 0. La hauteur de l’arbre est ici la plus grande profondeur ; un arbre réduit à sa racine a hauteur 0.
Un arbre binaire donne au plus deux enfants par nœud, distingués en gauche et droite. Cela n’impose aucun ordre sur les valeurs. Un parcours préfixe visite le nœud, puis son sous-arbre gauche, puis son sous-arbre droit. Un sous-arbre est un nœud accompagné de tous ses descendants.
L’exemple possède une racine de valeur 8, un enfant gauche 3 et un enfant droit 10. values stocke les valeurs ; left et right stockent les indices des enfants. L’absence d’enfant vaut -1 en Python et 0 en MATLAB. Chaque appel teste cette sentinelle avant de lire un tableau. Le contrat exclut cycles et liens invalides.
Suivre les états
| Appel | Action |
|---|---|
| Racine 8 | Visiter 8 |
| Enfant gauche 3 | Visiter 3 puis ses enfants absents |
| Enfant droit 10 | Visiter 10 puis ses enfants absents |
Comparer les réalisations
La sortie est [8, 3, 10]. En Python, + concatène les listes renvoyées. Le script MATLAB est enregistré dans preorder_tree.m ; sa fonction locale se place après les instructions du script. Elle reçoit explicitement les tableaux nécessaires.
// example.pseudo
// preorder_tree
PROCEDURE VISIT(node)
IF node == -1 THEN
RETURN
END IF
PRINT values[node]
VISIT(left[node])
VISIT(right[node])
END PROCEDURE# preorder_tree.py
values = [8, 3, 10]
left = [1, -1, -1]
right = [2, -1, -1]
def preorder(node):
if node == -1:
return []
return [values[node]] + preorder(left[node]) + preorder(right[node])
order = preorder(0)
print(order)% preorder_tree.m
values = [8, 3, 10];
left = [2, 0, 0];
right = [3, 0, 0];
order = preorder(1, values, left, right);
disp(order);
function order = preorder(node, values, left, right)
if node == 0
order = [];
return;
end
order = [values(node), preorder(left(node), values, left, right), preorder(right(node), values, left, right)];
endJustifier et compter
Un parcours qui effectue une action constante à chaque nœud visite n nœuds en Θ(n), avec O(h) appels simultanés pour une hauteur h. Les exemples construisent la sortie par concaténations récursives : ils ne garantissent pas ce temps linéaire de bout en bout. Sur un arbre en chaîne, les copies peuvent totaliser Θ(n²). La sortie elle-même occupe Θ(n). Une accumulation dans un stockage préalloué évite ces copies répétées.
Prévoir puis expérimenter
Inversez les enfants de la racine : l’ordre préfixe devient [8, 10, 3]. Identifiez les feuilles et la hauteur. Un arbre binaire n’est donc pas nécessairement ordonné par valeur.
Exercice corrigé
Quelle différence entre profondeur et hauteur ?
La profondeur dépend du nœud choisi et se mesure depuis la racine. La hauteur de l’arbre est la plus grande de ces profondeurs selon notre convention en nombre d’arêtes.
À retenir
- Un arbre binaire possède au plus un enfant gauche et un enfant droit par nœud.
- La profondeur compte les arêtes depuis la racine ; la hauteur est la plus grande profondeur.
- Visiter chaque nœud une fois ne garantit pas un temps linéaire si chaque retour recopie une longue sortie.