Chapitre 6 — Introduction aux arbres
Représenter des données hiérarchiques et parcourir leurs relations
| Positionnement dans le parcours — Après les structures linéaires et les tables de hachage, ce chapitre introduit les structures hiérarchiques. Il prépare l’étude des arbres binaires de recherche, des tas, des files de priorité et de nombreux algorithmes récursifs. |
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- utiliser correctement le vocabulaire associé aux arbres ;
- distinguer profondeur, hauteur, degré et niveau ;
- identifier les principales catégories d’arbres binaires ;
- représenter un arbre au moyen de nœuds chaînés ou d’un tableau ;
- concevoir les parcours préfixe, infixe, postfixe et en largeur ;
- choisir un parcours adapté au résultat attendu ;
- analyser les coûts temporels et spatiaux des parcours ;
- modéliser une expression, une arborescence, une hiérarchie ou un menu sous forme d’arbre.
Prérequis
- Maîtrise des fonctions et de la récursivité.
- Connaissance des listes chaînées, piles et files.
- Capacité à manipuler des références vers des nœuds.
- Compréhension des complexités O(1), O(n) et O(h).
Organisation proposée
Partie | Contenu principal | Durée indicative |
|---|---|---|
| 6.1 | Vocabulaire et mesures fondamentales | 2 h |
| 6.2 | Arbres binaires et principales familles | 2 h |
| 6.3 | Représentations chaînée et par tableau | 2 h |
| 6.4 | Parcours en profondeur et en largeur | 4 h |
| Applications | Expressions, fichiers, organisations et menus | 2 h |
| TD / TP | Construction, parcours, traces et modélisation | 4 à 6 h |
Introduction
Les tableaux, listes, piles et files organisent principalement les données de façon linéaire. Or, de nombreuses situations possèdent une structure hiérarchique : un dossier contient des sous-dossiers, une organisation comprend des services, une expression est composée de sous-expressions et un menu propose des sous-menus. Les arbres permettent de représenter ces relations de dépendance ou de composition.
Un arbre relie des nœuds sans former de cycle. À partir d’un nœud choisi comme racine, chaque autre nœud possède un unique parent. Cette organisation rend possibles des traitements récursifs naturels : traiter un nœud, puis appliquer la même opération à chacun de ses sous-arbres.
| Idée directrice — Un arbre transforme une organisation hiérarchique en une structure que l’on peut construire, parcourir, rechercher et modifier par des algorithmes systématiques. |
6.1 Vocabulaire
6.1.1 Nœud et racine
Un nœud est l’unité élémentaire d’un arbre. Il contient une donnée et des références vers ses enfants. La racine est le seul nœud qui ne possède pas de parent. Elle constitue le point d’entrée de la structure.
Exemple d’arbre enraciné A / | \ B C D / \ | E F G |
Terme | Dans l’exemple | Interprétation |
|---|---|---|
| Racine | A | Point de départ de l’arbre. |
| Nœuds | A, B, C, D, E, F, G | Éléments de la structure. |
| Arêtes | A-B, A-C, A-D, B-E, B-F, D-G | Relations directes entre les nœuds. |
| Taille | 7 | Nombre total de nœuds. |
6.1.2 Parent, enfant et frère
Si deux nœuds sont reliés et que le premier est plus proche de la racine, il est le parent du second. Le second est son enfant. Deux nœuds qui possèdent le même parent sont frères.
- A est le parent de B, C et D.
- B, C et D sont les enfants de A.
- B, C et D sont frères.
- E et F sont frères et ont B pour parent.
- Un nœud peut avoir zéro, un ou plusieurs enfants dans un arbre général.
| Attention — Les termes gauche et droite ne sont pertinents que lorsque l’ordre des enfants est défini, en particulier dans un arbre binaire. |
6.1.3 Feuille et nœud interne
Une feuille est un nœud sans enfant. Un nœud interne possède au moins un enfant. Dans l’exemple, C, E, F et G sont des feuilles ; A, B et D sont des nœuds internes.
Catégorie | Condition | Exemples |
|---|---|---|
| Feuille | Nombre d’enfants égal à 0 | C, E, F, G |
| Nœud interne | Nombre d’enfants supérieur ou égal à 1 | A, B, D |
| Nœud unaire | Un seul enfant | D |
| Nœud de branchement | Au moins deux enfants | A, B |
6.1.4 Sous-arbre
Le sous-arbre enraciné en un nœud x contient x et tous ses descendants. Le sous-arbre de B contient B, E et F. Cette notion est essentielle, car de nombreux algorithmes appliquent récursivement le même traitement au sous-arbre de chaque enfant.
| Propriété récursive — Un arbre est soit vide, soit constitué d’une racine reliée à zéro ou plusieurs sous-arbres. |
6.1.5 Ancêtre et descendant
Un nœud x est un ancêtre de y s’il se trouve sur le chemin reliant la racine à y. Inversement, y est un descendant de x. A est un ancêtre de tous les autres nœuds ; E est un descendant de A et de B.
6.1.6 Profondeur, niveau et hauteur
La profondeur d’un nœud correspond au nombre d’arêtes entre la racine et ce nœud. La racine a donc une profondeur de 0. Le niveau est parfois défini de la même façon ; dans d’autres conventions, la racine se trouve au niveau 1. Le cours utilise ici profondeur(racine) = 0.
La hauteur d’un nœud est le nombre maximal d’arêtes entre ce nœud et une feuille descendante. Une feuille a une hauteur de 0. La hauteur de l’arbre est la hauteur de sa racine.
Nœud | Profondeur | Hauteur |
|---|---|---|
A | 0 | 2 |
B | 1 | 1 |
C | 1 | 0 |
D | 1 | 1 |
E | 2 | 0 |
F | 2 | 0 |
G | 2 | 0 |
Pseudo-code — Calcul récursif de la taille Fonction Taille(noeud) : Entier Si noeud = NULL Alors Retourner 0 FinSi total <- 1 Pour chaque enfant de noeud Faire total <- total + Taille(enfant) FinPour Retourner total FinFonction |
Pseudo-code — Calcul récursif de la hauteur Fonction Hauteur(noeud) : Entier Si noeud = NULL Alors Retourner -1 FinSi hauteurMax <- -1 Pour chaque enfant de noeud Faire hauteurMax <- Maximum(hauteurMax, Hauteur(enfant)) FinPour Retourner 1 + hauteurMax FinFonction Convention utilisée : la hauteur de l’arbre vide vaut -1 et celle d’une feuille vaut 0. |
6.1.7 Degré d’un nœud et degré d’un arbre
Le degré d’un nœud est son nombre d’enfants. Le degré d’un arbre correspond au degré maximal observé parmi ses nœuds. Dans l’exemple, le degré de A vaut 3 et le degré de l’arbre vaut également 3.
Mesure | Définition | Valeur dans l’exemple |
|---|---|---|
| Taille | Nombre total de nœuds | 7 |
| Nombre d’arêtes | Taille − 1 pour un arbre non vide | 6 |
| Hauteur | Plus grande profondeur d’une feuille | 2 |
| Degré de l’arbre | Nombre maximal d’enfants | 3 |
| Nombre de feuilles | Nœuds sans enfant | 4 |
6.2 Arbres binaires
Un arbre binaire est un arbre dans lequel chaque nœud possède au plus deux enfants distingués : un enfant gauche et un enfant droit. La position des enfants fait partie de la structure : un nœud ayant seulement un enfant gauche est différent d’un nœud ayant seulement un enfant droit.
6.2.1 Enfant gauche et enfant droit
Exemple d’arbre binaire 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 |
Dans cet exemple, 3 est l’enfant gauche de 8 et 10 son enfant droit. Le nœud 10 ne possède pas d’enfant gauche, mais possède 14 comme enfant droit.
6.2.2 Définition récursive
| Définition — Un arbre binaire est soit vide, soit composé d’une racine, d’un sous-arbre binaire gauche et d’un sous-arbre binaire droit. |
Cette définition explique pourquoi les parcours et de nombreuses opérations sur les arbres binaires sont naturellement récursifs.
6.2.3 Arbre binaire strict ou plein
Un arbre binaire strict, parfois appelé plein selon les ouvrages, est un arbre dans lequel chaque nœud interne possède exactement deux enfants. Les nœuds ont donc zéro ou deux enfants, jamais un seul.
Arbre binaire strict A / \ B C / \ D E |
6.2.4 Arbre binaire complet
Un arbre binaire complet remplit tous les niveaux sauf éventuellement le dernier. Les nœuds du dernier niveau sont placés de gauche à droite sans laisser de trou. Cette organisation est particulièrement adaptée à une représentation compacte dans un tableau.
Arbre binaire complet A / \ B C / \ / D E F |
| Application — Les tas binaires utilisés pour les files de priorité sont des arbres binaires complets. |
6.2.5 Arbre binaire parfait
Un arbre binaire parfait possède tous ses niveaux entièrement remplis. Toutes les feuilles ont la même profondeur et chaque nœud interne possède deux enfants.
Arbre binaire parfait de hauteur 2 A / \ B C / \ / \ D E F G |
Hauteur h | Nombre de nœuds | Nombre de feuilles |
|---|---|---|
0 | 1 = 2¹ − 1 | 1 = 2⁰ |
1 | 3 = 2² − 1 | 2 = 2¹ |
2 | 7 = 2³ − 1 | 4 = 2² |
3 | 15 = 2⁴ − 1 | 8 = 2³ |
h | 2^(h+1) − 1 | 2^h |
6.2.6 Arbre équilibré
De manière générale, un arbre est considéré comme équilibré lorsque sa hauteur reste proche du minimum possible, c’est-à-dire de l’ordre de log n. La définition exacte dépend de la famille étudiée. Dans un arbre AVL, par exemple, les hauteurs des sous-arbres gauche et droit de chaque nœud diffèrent d’au plus 1.
Forme | Hauteur pour n nœuds | Conséquence |
|---|---|---|
| Équilibrée | O(log n) | Les opérations guidées par une branche peuvent être rapides. |
| Dégénérée | O(n) | L’arbre se comporte comme une liste chaînée. |
| Parfaite | ⌊log₂ n⌋ | Hauteur minimale pour le nombre de nœuds. |
Comparaison des formes Équilibré : Dégénéré : 4 1 / \ \ 2 6 2 / \ / \ \ 1 3 5 7 3 \ 4 |
6.2.7 Relations utiles
- Un arbre binaire de hauteur h contient au maximum 2^(h+1) − 1 nœuds.
- Le niveau d contient au maximum 2^d nœuds.
- Un arbre binaire complet à n nœuds a une hauteur ⌊log₂ n⌋.
- Dans un arbre binaire strict non vide, si I est le nombre de nœuds internes et F le nombre de feuilles, alors F = I + 1.
| Point de vigilance — Les termes complet, parfait, strict et équilibré ne sont pas synonymes. Il faut toujours vérifier la définition utilisée dans le cours ou l’ouvrage. |
6.3 Représentation
6.3.1 Représentation chaînée
Dans la représentation chaînée d’un arbre binaire, chaque nœud contient une donnée et deux références : gauche et droite. Une référence NULL indique l’absence de sous-arbre correspondant.
Pseudo-code — Type d’un nœud binaire Type NoeudBinaire donnee : Element gauche : Reference vers NoeudBinaire droite : Reference vers NoeudBinaire FinType |
Pseudo-code — Création d’un nœud Fonction CreerNoeud(valeur) : Reference nouveau <- Allouer un NoeudBinaire nouveau.donnee <- valeur nouveau.gauche <- NULL nouveau.droite <- NULL Retourner nouveau FinFonction |
La variable racine contient la référence du premier nœud. Si racine = NULL, l’arbre est vide. Chaque référence donne directement accès au sous-arbre correspondant.
Avantage | Explication |
|---|---|
| Structure dynamique | Les nœuds sont ajoutés selon les besoins. |
| Sous-arbres irréguliers | Aucune case n’est réservée pour les enfants absents. |
| Modifications locales | Une insertion ou suppression peut modifier quelques références. |
| Récursivité naturelle | Chaque référence désigne un arbre binaire complet ou vide. |
Limite | Explication |
|---|---|
| Mémoire des références | Chaque nœud stocke deux références en plus de la donnée. |
| Localité mémoire | Les nœuds peuvent être dispersés en mémoire. |
| Gestion dynamique | L’allocation et la libération doivent être maîtrisées. |
| Accès par position | Il n’existe pas d’indice direct vers le k-ième nœud d’un parcours. |
6.3.2 Représentation dans un tableau
Un arbre binaire complet peut être stocké sans références explicites. Avec des indices commençant à 0, les relations sont calculées par des formules simples.
Relation | Formule pour un nœud d’indice i |
|---|---|
Enfant gauche | 2i + 1 |
Enfant droit | 2i + 2 |
Parent, si i > 0 | ⌊(i − 1) / 2⌋ |
Arbre et indices A(0) / \ B(1) C(2) / \ / \ D(3) E(4) F(5) G(6)
Tableau : [ A | B | C | D | E | F | G ] |
Pseudo-code — Accès aux indices Fonction IndiceGauche(i) : Entier Retourner 2 * i + 1 FinFonction
Fonction IndiceDroit(i) : Entier Retourner 2 * i + 2 FinFonction
Fonction IndiceParent(i) : Entier Retourner (i - 1) DIV 2 FinFonction |
6.3.3 Cas des arbres incomplets
La représentation par tableau devient coûteuse lorsqu’un arbre est très irrégulier. Les positions correspondant aux enfants absents restent inutilisées. Un arbre dégénéré vers la droite pourrait nécessiter des indices qui croissent exponentiellement alors qu’il ne contient que quelques nœuds.
Gaspillage possible Arbre : A \ B \ C
Indices : A(0), B(2), C(6) Cases inutilisées : 1, 3, 4, 5 |
6.3.4 Comparaison des représentations
Critère | Représentation chaînée | Représentation par tableau |
|---|---|---|
| Forme adaptée | Arbre quelconque ou irrégulier | Arbre complet ou presque complet |
| Mémoire | Nœuds + références | Cases contiguës ; trous possibles |
| Accès aux enfants | Par références en O(1) | Par calcul d’indice en O(1) |
| Accès au parent | Référence supplémentaire ou recherche | Formule immédiate |
| Insertion structurelle | Flexible | Peut nécessiter redimensionnement ou déplacement |
| Localité mémoire | Souvent plus faible | Très bonne |
| Applications typiques | Arbres de recherche, syntaxe, fichiers | Tas binaires |
| Choix de représentation — La forme de l’arbre et les opérations dominantes doivent guider la représentation. Il n’existe pas de représentation universellement meilleure. |
6.3.5 Représentation d’un arbre général
Un arbre général peut être représenté par une liste d’enfants dans chaque nœud. Une autre technique utilise deux références par nœud : premierEnfant et frereSuivant. Elle transforme conceptuellement l’arbre général en structure binaire tout en conservant l’ordre des enfants.
Pseudo-code — Nœud d’un arbre général Type NoeudGeneral donnee : Element enfants : Liste de References FinType |
Pseudo-code — Représentation premier enfant / frère suivant Type NoeudGeneralCompact donnee : Element premierEnfant : Reference frereSuivant : Reference FinType |
6.4 Parcours
Parcourir un arbre consiste à visiter chacun de ses nœuds une fois selon un ordre déterminé. Les parcours en profondeur explorent complètement un sous-arbre avant de passer au suivant. Le parcours en largeur traite les nœuds niveau par niveau.
6.4.1 Parcours préfixe
Le parcours préfixe visite d’abord la racine, puis le sous-arbre gauche et enfin le sous-arbre droit. Il est noté Racine-Gauche-Droite.
Pseudo-code — Parcours préfixe récursif Procedure ParcoursPrefixe(noeud) Si noeud != NULL Alors Traiter(noeud.donnee) ParcoursPrefixe(noeud.gauche) ParcoursPrefixe(noeud.droite) FinSi FinProcedure |
Pour l’arbre binaire d’exemple : 8, 3, 1, 6, 4, 7, 10, 14, 13.
- Copier ou sérialiser la structure d’un arbre.
- Produire une expression préfixée.
- Afficher une hiérarchie en traitant le responsable avant ses subordonnés.
- Construire une liste où chaque parent précède ses descendants.
6.4.2 Parcours infixe
Le parcours infixe visite le sous-arbre gauche, la racine, puis le sous-arbre droit. Il est noté Gauche-Racine-Droite. Dans un arbre binaire de recherche, ce parcours produit les clés dans l’ordre croissant.
Pseudo-code — Parcours infixe récursif Procedure ParcoursInfixe(noeud) Si noeud != NULL Alors ParcoursInfixe(noeud.gauche) Traiter(noeud.donnee) ParcoursInfixe(noeud.droite) FinSi FinProcedure |
Pour l’arbre d’exemple : 1, 3, 4, 6, 7, 8, 10, 13, 14.
| Spécificité — Le parcours infixe est défini naturellement pour les arbres binaires, car il utilise la distinction entre sous-arbre gauche et sous-arbre droit. |
6.4.3 Parcours postfixe
Le parcours postfixe visite le sous-arbre gauche, le sous-arbre droit, puis la racine. Il est noté Gauche-Droite-Racine. Les enfants sont donc traités avant leur parent.
Pseudo-code — Parcours postfixe récursif Procedure ParcoursPostfixe(noeud) Si noeud != NULL Alors ParcoursPostfixe(noeud.gauche) ParcoursPostfixe(noeud.droite) Traiter(noeud.donnee) FinSi FinProcedure |
Pour l’arbre d’exemple : 1, 4, 7, 6, 3, 13, 14, 10, 8.
- Supprimer un arbre en libérant les enfants avant le parent.
- Évaluer une expression postfixée.
- Calculer une propriété du parent à partir des résultats des enfants.
- Calculer la taille ou la hauteur d’un sous-arbre.
6.4.4 Parcours en largeur
Le parcours en largeur visite les nœuds par niveaux successifs, de gauche à droite. Il utilise une file : la racine est enfilée, puis chaque nœud défilé ajoute ses enfants à la fin de la file.
Pseudo-code — Parcours en largeur Procedure ParcoursLargeur(racine) Si racine = NULL Alors Retourner F <- FileVide() Enfiler(F, racine) TantQue NON EstVide(F) Faire noeud <- Defiler(F) Traiter(noeud.donnee) Si noeud.gauche != NULL Alors Enfiler(F, noeud.gauche) FinSi Si noeud.droite != NULL Alors Enfiler(F, noeud.droite) FinSi FinTantQue FinProcedure |
Pour l’arbre d’exemple : 8, 3, 10, 1, 6, 14, 4, 7, 13.
Étape | Nœud traité | File après ajout des enfants |
|---|---|---|
1 | 8 | [3, 10] |
2 | 3 | [10, 1, 6] |
3 | 10 | [1, 6, 14] |
4 | 1 | [6, 14] |
5 | 6 | [14, 4, 7] |
6 | 14 | [4, 7, 13] |
7 | 4 | [7, 13] |
8 | 7 | [13] |
9 | 13 | [] |
6.4.5 Versions itératives des parcours en profondeur
La récursivité utilise implicitement la pile d’appels. Une version itérative peut utiliser explicitement une pile, ce qui donne davantage de contrôle sur la mémoire et évite un dépassement de pile pour les arbres très profonds.
Pseudo-code — Parcours préfixe itératif Procedure PrefixeIteratif(racine) Si racine = NULL Alors Retourner P <- PileVide() Empiler(P, racine) TantQue NON EstVide(P) Faire noeud <- Depiler(P) Traiter(noeud.donnee) Si noeud.droite != NULL Alors Empiler(P, noeud.droite) Si noeud.gauche != NULL Alors Empiler(P, noeud.gauche) FinTantQue FinProcedure Le sous-arbre droit est empilé avant le gauche, car la pile restitue le dernier élément ajouté en premier. |
Pseudo-code — Parcours infixe itératif Procedure InfixeIteratif(racine) P <- PileVide() courant <- racine TantQue courant != NULL OU NON EstVide(P) Faire TantQue courant != NULL Faire Empiler(P, courant) courant <- courant.gauche FinTantQue courant <- Depiler(P) Traiter(courant.donnee) courant <- courant.droite FinTantQue FinProcedure |
6.4.6 Complexité des parcours
Parcours | Temps | Mémoire auxiliaire |
|---|---|---|
| Préfixe récursif | O(n) | O(h) pour la pile d’appels |
| Infixe récursif | O(n) | O(h) |
| Postfixe récursif | O(n) | O(h) |
| Préfixe / infixe itératif | O(n) | O(h) en général |
| Largeur | O(n) | O(w), où w est la largeur maximale |
| Analyse — Chaque parcours visite chaque nœud une fois : le temps est donc O(n). La mémoire dépend de la forme de l’arbre et de la stratégie de parcours. |
6.4.7 Choisir le parcours adapté
Besoin | Parcours conseillé | Justification |
|---|---|---|
| Traiter un parent avant ses descendants | Préfixe | La racine est visitée en premier. |
| Obtenir l’ordre des clés d’un arbre de recherche | Infixe | Gauche, racine, droite. |
| Traiter les enfants avant le parent | Postfixe | La racine est visitée en dernier. |
| Explorer par distance à la racine | Largeur | Les niveaux sont parcourus successivement. |
| Trouver un nœud le moins profond | Largeur | Le premier résultat est à profondeur minimale. |
Applications
Application 1 — Expression arithmétique
Une expression peut être représentée par un arbre binaire dont les feuilles contiennent les opérandes et les nœuds internes les opérateurs. Pour l’expression (3 + 5) × (10 − 4) :
Arbre d’expression × / \ + − / \ / \ 3 5 10 4 |
Parcours | Résultat |
|---|---|
| Préfixe | × + 3 5 − 10 4 |
| Infixe parenthésé | ((3 + 5) × (10 − 4)) |
| Postfixe | 3 5 + 10 4 − × |
Pseudo-code — Évaluation d’un arbre d’expression Fonction Evaluer(noeud) : Reel Si noeud est une feuille Alors Retourner ValeurNumerique(noeud.donnee) FinSi gauche <- Evaluer(noeud.gauche) droite <- Evaluer(noeud.droite) Retourner Appliquer(noeud.donnee, gauche, droite) FinFonction |
L’évaluation de l’exemple donne (3 + 5) × (10 − 4) = 8 × 6 = 48.
Application 2 — Arborescence de fichiers
Un système de fichiers hiérarchique peut être modélisé par un arbre général. Les dossiers sont des nœuds internes et les fichiers sont généralement des feuilles.
Exemple d’arborescence Projet/ ├── src/ │ ├── main.py │ └── utils.py ├── tests/ │ └── test_main.py └── README.md |
Pseudo-code — Affichage indenté Procedure AfficherArborescence(noeud, profondeur) Afficher Repeter(" ", profondeur), noeud.nom Pour chaque enfant de noeud Faire AfficherArborescence(enfant, profondeur + 1) FinPour FinProcedure |
Le parcours préfixe convient, car le dossier doit être affiché avant son contenu. Le paramètre profondeur contrôle l’indentation.
Application 3 — Hiérarchie organisationnelle
Une organisation peut être modélisée par un arbre général : la direction constitue la racine, les divisions sont ses enfants et les équipes apparaissent aux niveaux inférieurs.
Exemple de hiérarchie Direction générale ├── Direction technique │ ├── Développement │ └── Infrastructure ├── Direction financière └── Ressources humaines |
- Le parcours préfixe produit un organigramme du haut vers le bas.
- Le parcours en largeur affiche les responsables niveau par niveau.
- La hauteur mesure le nombre maximal de niveaux hiérarchiques sous la direction.
- La taille d’un sous-arbre indique l’effectif d’une unité si chaque nœud représente une personne.
Pseudo-code — Effectif d’une unité Fonction Effectif(unite) : Entier total <- 1 Pour chaque sousUnite de unite Faire total <- total + Effectif(sousUnite) FinPour Retourner total FinFonction |
Application 4 — Menu de navigation
Un menu peut être représenté par un arbre dont chaque nœud possède un libellé, une action éventuelle et une liste de sous-menus. Les feuilles déclenchent une action, tandis que les nœuds internes ouvrent un nouveau niveau.
Exemple de menu Accueil ├── Cours │ ├── Algorithmique │ └── Programmation ├── Articles └── Contact |
Pseudo-code — Recherche d’une option Fonction ChercherOption(noeud, libelle) : ReferenceOuNULL Si noeud.libelle = libelle Alors Retourner noeud FinSi Pour chaque enfant de noeud Faire resultat <- ChercherOption(enfant, libelle) Si resultat != NULL Alors Retourner resultat FinPour Retourner NULL FinFonction |
| Limite — Si les libellés ne sont pas uniques, la recherche doit retourner plusieurs résultats ou utiliser un chemin complet comme « Cours/Algorithmique ». |
Applications guidées complémentaires
A. Compter les feuilles
Pseudo-code — Nombre de feuilles Fonction NombreFeuilles(noeud) : Entier Si noeud = NULL Alors Retourner 0 Si noeud.gauche = NULL ET noeud.droite = NULL Alors Retourner 1 FinSi Retourner NombreFeuilles(noeud.gauche) + NombreFeuilles(noeud.droite) FinFonction |
B. Rechercher une valeur
Pseudo-code — Recherche dans un arbre binaire quelconque Fonction Contient(noeud, valeur) : Booleen Si noeud = NULL Alors Retourner FAUX Si noeud.donnee = valeur Alors Retourner VRAI Retourner Contient(noeud.gauche, valeur) OU Contient(noeud.droite, valeur) FinFonction |
C. Compter les nœuds d’un niveau
Pseudo-code — Nombre de nœuds à la profondeur d Fonction CompterNiveau(noeud, d) : Entier Si noeud = NULL Alors Retourner 0 Si d = 0 Alors Retourner 1 Retourner CompterNiveau(noeud.gauche, d - 1) + CompterNiveau(noeud.droite, d - 1) FinFonction |
Travaux dirigés
TD 1 — Vocabulaire
À partir de l’arbre suivant, déterminer la racine, les feuilles, les nœuds internes, les frères de E, les ancêtres de H, le sous-arbre de C, la profondeur de chaque nœud et la hauteur de l’arbre.
Arbre du TD 1 A / \ B C / \ / \ D E F G / \ H I |
TD 2 — Catégories d’arbres binaires
Pour chacun des arbres proposés par l’enseignant, préciser s’il est strict, complet, parfait et/ou équilibré. Justifier chaque réponse à partir des définitions.
TD 3 — Formules
Un arbre binaire parfait a une hauteur h = 5. Calculer le nombre de feuilles et le nombre total de nœuds. Déterminer ensuite la hauteur minimale d’un arbre binaire contenant 100 nœuds.
TD 4 — Représentation par tableau
Le tableau suivant représente un arbre binaire complet : [A, B, C, D, E, F, G, H]. Donner le parent, l’enfant gauche et l’enfant droit des nœuds d’indices 1, 2, 3 et 7 lorsqu’ils existent. Dessiner l’arbre correspondant.
TD 5 — Ordres de parcours
Pour l’arbre du TD 1, donner les parcours préfixe, infixe, postfixe et en largeur.
TD 6 — Reconstruire un arbre
Reconstruire l’arbre binaire dont le parcours préfixe est A, B, D, E, C, F, G et le parcours infixe D, B, E, A, F, C, G.
TD 7 — Tracer le parcours en largeur
Présenter, étape par étape, le contenu de la file lors du parcours en largeur de l’arbre du TD 1.
TD 8 — Écrire une fonction
Écrire une fonction récursive qui calcule la somme des valeurs numériques contenues dans un arbre binaire.
TD 9 — Vérifier l’équilibre
Proposer une fonction qui retourne VRAI si, pour chaque nœud, la différence entre les hauteurs des sous-arbres gauche et droit est au plus égale à 1. La fonction doit éviter de recalculer inutilement les hauteurs.
TD 10 — Modélisation
Concevoir la structure d’un menu de formation contenant des catégories, sous-catégories et cours. Définir le type d’un nœud, puis proposer les opérations AjouterEnfant, RechercherParTitre et AfficherMenu.
Corrigés indicatifs des travaux dirigés
Correction du TD 1
- Racine : A.
- Feuilles : D, F, H, I.
- Nœuds internes : A, B, C, E, G.
- Frère de E : D.
- Ancêtres de H : A, B et E.
- Sous-arbre de C : C, F, G et I.
- Profondeurs : A=0 ; B=C=1 ; D=E=F=G=2 ; H=I=3.
- Hauteur de l’arbre : 3.
Correction du TD 2
La correction dépend des arbres proposés. Pour chaque arbre, vérifier séparément : zéro ou deux enfants pour la propriété stricte ; remplissage de gauche à droite pour la propriété complète ; niveaux entièrement remplis pour la propriété parfaite ; hauteur proche de log n et critère local précisé pour la propriété équilibrée.
Correction du TD 3
Pour h = 5 : nombre de feuilles = 2^5 = 32 ; nombre total de nœuds = 2^6 − 1 = 63. Pour 100 nœuds, la hauteur minimale h vérifie 2^(h+1) − 1 ≥ 100. Comme 2^6 − 1 = 63 et 2^7 − 1 = 127, la hauteur minimale est 6.
Correction du TD 4
Indice i | Nœud | Parent | Gauche | Droite |
|---|---|---|---|---|
1 | B | A (0) | D (3) | E (4) |
2 | C | A (0) | F (5) | G (6) |
3 | D | B (1) | H (7) | Absent |
7 | H | D (3) | Absent | Absent |
Arbre reconstruit A / \ B C / \ / \ D E F G / H |
Correction du TD 5
Parcours | Ordre |
|---|---|
| Préfixe | A, B, D, E, H, C, F, G, I |
| Infixe | D, B, H, E, A, F, C, G, I |
| Postfixe | D, H, E, B, F, I, G, C, A |
| Largeur | A, B, C, D, E, F, G, H, I |
Correction du TD 6
La première valeur du préfixe, A, est la racine. Dans l’infixe, les valeurs situées avant A appartiennent au sous-arbre gauche : D, B, E ; les valeurs après A appartiennent au sous-arbre droit : F, C, G. Le même raisonnement est appliqué récursivement.
Arbre obtenu A / \ B C / \ / \ D E F G |
Correction du TD 7
Nœud défilé | File après traitement |
|---|---|
A | [B, C] |
B | [C, D, E] |
C | [D, E, F, G] |
D | [E, F, G] |
E | [F, G, H] |
F | [G, H] |
G | [H, I] |
H | [I] |
I | [] |
Correction du TD 8
Pseudo-code — Somme des valeurs Fonction Somme(noeud) : Reel Si noeud = NULL Alors Retourner 0 Retourner noeud.donnee + Somme(noeud.gauche) + Somme(noeud.droite) FinFonction |
Correction du TD 9
Une solution efficace retourne simultanément la hauteur et l’état d’équilibre. Ainsi, chaque nœud est visité une seule fois.
Pseudo-code — Vérification en O(n) Fonction HauteurOuErreur(noeud) : Entier Si noeud = NULL Alors Retourner -1 hg <- HauteurOuErreur(noeud.gauche) Si hg = ERREUR Alors Retourner ERREUR hd <- HauteurOuErreur(noeud.droite) Si hd = ERREUR Alors Retourner ERREUR Si ValeurAbsolue(hg - hd) > 1 Alors Retourner ERREUR FinSi Retourner 1 + Maximum(hg, hd) FinFonction
Fonction EstEquilibre(racine) : Booleen Retourner HauteurOuErreur(racine) != ERREUR FinFonction |
Correction du TD 10
Pseudo-code — Structure et opérations du menu Type NoeudMenu titre : Chaine typeElement : {CATEGORIE, COURS} enfants : Liste de References vers NoeudMenu FinType
Procedure AjouterEnfant(parent, enfant) AjouterFin(parent.enfants, enfant) FinProcedure
Fonction RechercherParTitre(noeud, titre) : ReferenceOuNULL Si noeud.titre = titre Alors Retourner noeud Pour chaque enfant de noeud Faire r <- RechercherParTitre(enfant, titre) Si r != NULL Alors Retourner r FinPour Retourner NULL FinFonction
Procedure AfficherMenu(noeud, profondeur) Afficher Repeter(" ", profondeur), noeud.titre Pour chaque enfant de noeud Faire AfficherMenu(enfant, profondeur + 1) FinPour FinProcedure |
Travail pratique — Construction et exploration d’un arbre
Objectif
Développer une petite bibliothèque d’arbres binaires permettant de construire un arbre, de l’afficher et de calculer plusieurs propriétés. Le TP peut être réalisé en Python, C ou Java après écriture du pseudo-code.
Données de départ
Construire manuellement l’arbre suivant :
Arbre du TP 15 / \ 8 20 / \ / \ 4 11 17 25 / \ 9 30 |
Travail demandé
1. Définir la structure d’un nœud binaire.
2. Créer les nœuds et relier correctement les références gauche et droite.
3. Afficher les parcours préfixe, infixe, postfixe et en largeur.
4. Calculer la taille, la hauteur et le nombre de feuilles.
5. Rechercher une valeur quelconque dans l’arbre.
6. Afficher les valeurs situées à une profondeur donnée.
7. Vérifier si l’arbre satisfait le critère local d’équilibre.
8. Tester chaque fonction sur un arbre vide, une feuille et l’arbre complet du sujet.
Jeux d’essai attendus
Test | Résultat attendu |
|---|---|
| Préfixe | 15, 8, 4, 11, 9, 20, 17, 25, 30 |
| Infixe | 4, 8, 9, 11, 15, 17, 20, 25, 30 |
| Postfixe | 4, 9, 11, 8, 17, 30, 25, 20, 15 |
| Largeur | 15, 8, 20, 4, 11, 17, 25, 9, 30 |
| Taille | 9 |
| Hauteur | 3 |
| Nombre de feuilles | 4 : 4, 9, 17 et 30 |
| Recherche de 17 | VRAI |
| Recherche de 100 | FAUX |
Correction indicative du TP
Pseudo-code — Fonctions principales Fonction Taille(noeud) : Entier Si noeud = NULL Alors Retourner 0 Retourner 1 + Taille(noeud.gauche) + Taille(noeud.droite) FinFonction
Fonction Hauteur(noeud) : Entier Si noeud = NULL Alors Retourner -1 Retourner 1 + Maximum(Hauteur(noeud.gauche), Hauteur(noeud.droite)) FinFonction
Fonction Feuilles(noeud) : Entier Si noeud = NULL Alors Retourner 0 Si noeud.gauche = NULL ET noeud.droite = NULL Alors Retourner 1 Retourner Feuilles(noeud.gauche) + Feuilles(noeud.droite) FinFonction
Fonction Contient(noeud, valeur) : Booleen Si noeud = NULL Alors Retourner FAUX Si noeud.donnee = valeur Alors Retourner VRAI Retourner Contient(noeud.gauche, valeur) OU Contient(noeud.droite, valeur) FinFonction |
Pseudo-code — Affichage d’un niveau Procedure AfficherNiveau(noeud, profondeur) Si noeud = NULL Alors Retourner Si profondeur = 0 Alors Afficher noeud.donnee Sinon AfficherNiveau(noeud.gauche, profondeur - 1) AfficherNiveau(noeud.droite, profondeur - 1) FinSi FinProcedure |
Critères d’évaluation
Critère | Points |
|---|---|
Structure du nœud et construction correcte | 3 |
Quatre parcours | 5 |
Taille, hauteur et feuilles | 4 |
Recherche et affichage par niveau | 3 |
Tests et cas particuliers | 3 |
Lisibilité, modularité et commentaires | 2 |
Synthèse du chapitre
- Un arbre est une structure hiérarchique constituée de nœuds reliés sans cycle.
- La racine n’a pas de parent ; les feuilles n’ont pas d’enfant.
- La profondeur se mesure depuis la racine ; la hauteur se mesure vers la feuille la plus éloignée.
- Un arbre binaire possède au plus un enfant gauche et un enfant droit par nœud.
- Les notions strict, complet, parfait et équilibré décrivent des propriétés différentes.
- La représentation chaînée convient aux arbres irréguliers ; le tableau convient aux arbres complets.
- Les parcours préfixe, infixe et postfixe sont des parcours en profondeur.
- Le parcours en largeur utilise une file et traite les nœuds niveau par niveau.
- Tous les parcours complets s’exécutent en O(n).
- Les arbres modélisent naturellement les expressions, fichiers, organisations et menus.
Glossaire
Terme | Définition |
|---|---|
| Ancêtre | Nœud situé sur le chemin de la racine vers un autre nœud. |
| Arbre binaire | Arbre dont chaque nœud possède au plus deux enfants ordonnés. |
| Degré | Nombre d’enfants d’un nœud. |
| Descendant | Nœud appartenant au sous-arbre d’un autre nœud. |
| Feuille | Nœud sans enfant. |
| Hauteur | Distance maximale d’un nœud à une feuille descendante. |
| Nœud interne | Nœud possédant au moins un enfant. |
| Parcours en largeur | Visite des nœuds niveau par niveau à l’aide d’une file. |
| Parcours infixe | Sous-arbre gauche, racine, sous-arbre droit. |
| Parcours postfixe | Sous-arbre gauche, sous-arbre droit, racine. |
| Parcours préfixe | Racine, sous-arbre gauche, sous-arbre droit. |
| Profondeur | Nombre d’arêtes entre la racine et un nœud. |
| Racine | Nœud sans parent qui constitue l’entrée de l’arbre. |
| Sous-arbre | Nœud et ensemble de ses descendants. |
Auto-évaluation
Je suis capable de… | Oui | À revoir |
|---|---|---|
identifier la racine, les feuilles, les parents et les enfants ; | ☐ | ☐ |
calculer la profondeur, la hauteur et le degré ; | ☐ | ☐ |
distinguer un arbre complet, parfait et équilibré ; | ☐ | ☐ |
représenter un arbre par des nœuds chaînés ; | ☐ | ☐ |
utiliser les formules d’indices d’une représentation par tableau ; | ☐ | ☐ |
écrire les quatre parcours fondamentaux ; | ☐ | ☐ |
choisir un parcours adapté à une application ; | ☐ | ☐ |
analyser la complexité temporelle et spatiale d’un parcours ; | ☐ | ☐ |
modéliser une hiérarchie réelle sous forme d’arbre. | ☐ | ☐ |
| Transition vers le chapitre suivant — Les arbres binaires de recherche ajoutent une propriété d’ordre aux arbres binaires afin d’accélérer la recherche, l’insertion et la suppression. |