Au programme de ce chapitre
- I. Vocabulaire des arbres
- II. Représenter un arbre en Python
- III. Parcourir un arbre : préfixe, infixe, suffixe et en largeur
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Un arbre est une structure hiérarchique composée de nœuds reliés par des arêtes, sans cycle : il existe un unique chemin entre la racine (le nœud du haut, sans parent) et chaque autre nœud. Un nœud sans enfant est une feuille. Le nombre d'enfants d'un nœud est son arité ; un arbre binaire est un arbre où chaque nœud a au plus deux enfants.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3, un arbre représentant l'organisation d'un lycée :
>>> class Noeud:
... def __init__(self, valeur, enfants=None):
... self.valeur = valeur
... self.enfants = enfants if enfants is not None else []
...
>>> direction = Noeud("Direction", [
... Noeud("Vie scolaire", [Noeud("CPE"), Noeud("Surveillants")]),
... Noeud("Enseignement", [Noeud("Sciences"), Noeud("Lettres"), Noeud("Langues")]),
... ])Les erreurs fréquentes à éviter
Piège. Profondeur (d'un nœud) ≠ hauteur (de l'arbre) : ne les confonds pas.
Attention Ne confonds pas « profondeur d'un nœud » (distance depuis la racine) et « hauteur d'un arbre » (profondeur maximale). Pour un arbre à une seule racine sans enfant, la hauteur vaut 0, pas 1 : il n'y a aucune arête à traverser.
L'astuce du prof
Astuce. Racine en haut, feuilles en bas : un arbre informatique est à l'envers.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Définis la racine et une feuille.
Voir la correction
Racine : nœud initial sans parent ; feuille : nœud sans enfant.
Exercice 2
Différence entre profondeur d'un nœud et hauteur d'un arbre ?
Voir la correction
Profondeur = distance à la racine ; hauteur = plus grande profondeur.