Arbres et arbres binaires
Décrire une structure hiérarchique, distinguer gauche et droite, calculer taille et hauteur et encadrer les mesures d’un arbre binaire.
Environ 40 minutes
- Identifier racine, nœuds, feuilles et sous-arbres
- Mesurer taille, profondeur et hauteur selon une convention explicite
- Représenter un arbre binaire en Python
Six éléments organisés en arbre ont-ils forcément la même hauteur ?
Un dossier peut contenir des sous-dossiers, une décision peut ouvrir plusieurs branches et une expression peut être organisée en opérations imbriquées. Dans ces situations, l’ordre linéaire ne suffit plus : on décrit une hiérarchie. Tu vas définir un arbre enraciné, puis un arbre binaire, et mesurer leur forme. Prérequis : références d’objets, classes simples et puissances de deux. Les parcours détaillés et les arbres binaires de recherche seront étudiés plus tard.
1. Décrire une hiérarchie sans cycle
Un arbre enraciné non vide possède une racine et des nœuds reliés par des liens parent-enfant. La racine n’a pas de parent ; chaque autre nœud en a exactement un. Il existe un unique chemin descendant depuis la racine jusqu’à chaque nœud. Cette propriété exclut un retour vers un ancêtre et le partage d’un même enfant entre deux parents. Une feuille est un nœud qui n’a aucun enfant. Un nœud interne possède au moins un enfant. Un descendant peut être un enfant, un petit-enfant ou un nœud situé plus bas.
La profondeur d’un nœud est ici le nombre d’arêtes du chemin depuis la racine jusqu’à lui. La racine a donc une profondeur nulle. La taille de l’arbre est son nombre de nœuds. Sa hauteur est la plus grande profondeur atteinte, mesurée en arêtes. Une racine seule a une taille 1 et une hauteur 0. D’autres textes comptent les niveaux et donnent une hauteur 1 à une racine seule. Aucune des deux conventions n’est à deviner : annonce celle du cours ou utilise celle du sujet.
Exemple résolu
Détermine la taille, la hauteur, les feuilles et le parent de E dans cet arbre.
- Étape 1 : Compte les nœuds A, B, C, D, E et F : la taille est 6.
- Étape 2 : Les chemins les plus longs depuis A comportent deux arêtes, par exemple A vers B puis E. La hauteur est 2.
- Étape 3 : Les nœuds sans enfant sont D, E et F. Le lien qui atteint E vient de B : son parent est B.
Résultat : L’arbre a une taille 6, une hauteur 2 et trois feuilles. Le nombre de feuilles n’est ni la taille ni la hauteur.
Piège à éviter : Compter les trois nœuds du chemin A, B, E donnerait une hauteur en niveaux ; notre convention compte ses deux arêtes.
À toi d'essayer
Un schéma montre une racine R, deux enfants U et V, puis un même nœud W relié à U et à V. Est-ce un arbre enraciné au sens du cours ?
Voir la réponseMasquer la réponse
Non. W possède deux parents et deux chemins depuis la racine. Le schéma peut représenter un graphe, mais il ne respecte pas la structure d’arbre définie ici.
2. Gauche et droite sont deux places distinctes
Un arbre binaire est vide, ou formé d’une racine et de deux sous-arbres binaires disjoints, l’un gauche et l’autre droit. Un nœud peut donc avoir zéro, un ou deux enfants. Les places gauche et droite sont distinguées même si une seule est occupée. Un nœud ayant seulement un enfant gauche ne représente pas la même structure qu’un nœud ayant seulement un enfant droit. Les étiquettes peuvent être des nombres, des chaînes ou d’autres données ; elles ne sont pas obligatoirement toutes distinctes. Les nœuds sont des objets de la structure, leurs étiquettes sont leurs contenus.
Binaire ne signifie pas que tous les nœuds possèdent exactement deux enfants. Cela ne signifie pas non plus que les valeurs sont triées. Un arbre binaire de recherche ajoute une propriété d’ordre qui n’appartient pas à la définition générale. La taille se décompose en un nœud pour la racine, plus les tailles des sous-arbres gauche et droit. La hauteur dépend du plus haut sous-arbre, pas de la somme de leurs hauteurs. Pour prolonger ces formules au vide, on fixe ici sa taille à 0 et sa hauteur à −1. Cette convention technique donne bien une hauteur 0 pour une feuille.
À chaque profondeur, un arbre binaire possède au plus deux fois plus de nœuds qu’au niveau précédent. Il peut donc avoir au plus 1 nœud à profondeur 0, 2 à profondeur 1, 4 à profondeur 2 et ainsi de suite. Pour une hauteur h, le maximum total est 1 + 2 + … + 2^h = 2^(h + 1) − 1. Le minimum pour atteindre cette hauteur est une chaîne de h + 1 nœuds. Ces bornes décrivent des formes possibles, pas une taille unique imposée par la hauteur.
Exemple résolu
Un arbre binaire contient 6 nœuds. Quelle est sa hauteur minimale et sa hauteur maximale, en arêtes ?
- Étape 1 : Une hauteur 1 permet au plus 1 + 2 = 3 nœuds : elle est insuffisante pour en placer 6.
- Étape 2 : Une hauteur 2 permet au plus 7 nœuds. L’arbre de la première figure montre qu’une taille 6 avec cette hauteur est possible.
- Étape 3 : Une chaîne de 6 nœuds a 5 arêtes. Aucun chemin ne peut contenir plus de 6 nœuds distincts dans cet arbre.
Résultat : La hauteur minimale est 2 et la maximale est 5. Les deux extrêmes correspondent à des répartitions différentes des mêmes six nœuds.
Piège à éviter : Appliquer le nombre maximal de nœuds d’un niveau comme s’il était obligatoire exclurait à tort les arbres déséquilibrés.
À toi d'essayer
Un arbre binaire de hauteur 3 peut-il contenir 3 nœuds ? Peut-il en contenir 16 ?
Correction détaillée pas à pasDans ce chapitre : 2 corrections détaillées.
3. Relier la définition à une représentation
Une représentation par objets associe à chaque nœud une valeur, une référence vers le sous-arbre gauche et une référence vers le sous-arbre droit. None représente l’arbre vide. Une feuille possède donc deux références None. Il faut distinguer une référence vers un objet Noeud et la valeur de cet objet. Affecter la chaîne "B" à gauche ne crée pas un nœud portant cette chaîne. La représentation doit rester cohérente pour que les opérations puissent retrouver les mêmes attributs à chaque nœud.
Exemple résolu
Construis l’arbre de la première figure en plaçant F comme enfant droit de C, puis lis l’étiquette de E.
- Étape 1 : Définis les nœuds et leurs liens.class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
a = Noeud('A',
Noeud('B', Noeud('D'), Noeud('E')),
Noeud('C', None, Noeud('F'))) - Étape 2 : Depuis a, la référence gauche atteint B. Depuis ce nœud, la référence droit atteint E.
- Étape 3 : Consulte la valeur et teste une place vide.etiquette = a.gauche.droit.valeur
vide = a.droit.gauche is None
Résultat : etiquette vaut E et vide vaut True. La construction précise que C n’a pas d’enfant gauche et que F occupe sa place droite.
Piège à éviter : Remplacer a.gauche.droit par la chaîne E conserverait une étiquette mais supprimerait l’objet nœud attendu à cet endroit.
La classe ne garantit pas automatiquement la propriété d’arbre. Il reste possible d’affecter un même objet enfant à deux parents ou de créer un cycle en reliant un descendant à la racine. Ces affectations produiraient un autre type de graphe et rendraient certaines opérations sur les arbres incorrectes. Il faut donc respecter l’invariant de représentation : chaque nœud non racine a un seul parent et aucun lien descendant ne ramène à un ancêtre. Construire des objets ne dispense jamais de vérifier le modèle qu’ils sont censés représenter.
À toi d'essayer
On ajoute une nouvelle racine au-dessus de tout un arbre non vide, l’ancien arbre devenant son seul sous-arbre gauche. Comment évoluent taille, hauteur et nombre de feuilles ?
Correction détaillée pas à pasDans ce chapitre : 2 corrections détaillées.
4. Au bac : annoncer puis appliquer la convention
Au bac : mesurer et contrôler un arbre
- Identifie la racine et les liens parent-enfant. Vérifie que le dessin ne partage pas un enfant entre deux parents.
- Annonce la mesure de hauteur : ici en arêtes, avec une feuille de hauteur 0.
- Compte les nœuds pour la taille, puis suis les chemins jusqu’aux feuilles pour la hauteur. Le chemin le plus long détermine cette dernière.
- Pour un arbre binaire de hauteur h, contrôle h + 1 ≤ taille ≤ 2^(h + 1) − 1.
- Dans le code, suis une référence à la fois et vérifie le cas None avant de lire un attribut de nœud.
La forme du dessin peut tromper : allonger un trait ne change pas la hauteur, car nous comptons des arêtes et non une longueur géométrique. De même, déplacer visuellement un sous-arbre pour rendre le dessin lisible ne modifie pas la structure si les liens et les places gauche-droite sont conservés. Pour contrôler une réponse, compare le comptage direct avec la décomposition en sous-arbres. Deux méthodes cohérentes valent mieux qu’une formule appliquée sans savoir quelle grandeur elle décrit.
Vocabulaire
- Racine :
- Nœud de départ de l’arbre enraciné, sans parent.
- Feuille :
- Nœud qui ne possède aucun enfant.
- Sous-arbre :
- Arbre formé d’un nœud et de tous ses descendants dans les places correspondantes.
- Hauteur :
- Plus grande profondeur selon la convention choisie ; ici un nombre d’arêtes.
Cas de référence
| Structure | Taille | Hauteur |
|---|---|---|
| Vide | 0 | −1 par convention. |
| Racine seule | 1 | 0. |
| Chaîne de n nœuds non vide | n | n − 1. |
S’entraîner : ouvre l’espace Exercices du site.
À retenir
- La taille compte les nœuds ; la hauteur compte ici les arêtes du plus long chemin depuis la racine.
- Un arbre binaire distingue les sous-arbres gauche et droit, éventuellement vides.
- Un nœud peut avoir un seul enfant dans un arbre binaire.
- Un arbre binaire non vide de hauteur h a entre h + 1 et 2^(h + 1) − 1 nœuds.
Fiche de révision
Fixe d’abord le zéro de la hauteur : une feuille vaut ici 0, un arbre vide −1.
Une place vide à gauche ne se confond pas avec une place vide à droite.
Pour une taille donnée, étaler les branches peut réduire la hauteur ; les aligner en chaîne peut l’augmenter.
Avant de lire valeur, gauche ou droit, assure-toi que la référence atteint bien un nœud.
Questions fréquentes
Binaire signifie-t-il trié ?
Non. Une propriété de recherche ordonnée est une contrainte supplémentaire.
La hauteur dépend-elle de la longueur des traits ?
Non. Avec notre convention, elle dépend du nombre de liens sur les chemins.
Et maintenant ?
Tu as lu le cours. L’étape suivante tient en une action.
Relis le coursReprends l’essentiel avant de passer à la suite.Prolonge l’expérience !
Continue à explorer ce chapitre à travers de nouvelles activités, des défis et des expériences interactives. Avec Premium, l’apprentissage continue !
Ici, tu débloques aussi 2 corrections détaillées.
Parent ? Suivez les progrès de votre enfant.
