Fiche de révision : Arbres binaires et parcours

📋 Plan du Cours

1. Notions générales sur les arbres
2. Mesures et repères dans l’arbre
3. Formes particulières des arbres binaires
4. Arbres binaires étiquetés
5. Représentation chaînée en C++
6. Création et affichage des arbres
7. Parcours en largeur
8. Parcours en profondeur

📖 1. Notions générales sur les arbres

🔑 Notions clés & Définitions

• Arbre : Graphe connexe et acyclique.
• Arbre enraciné : Arbre muni d’un nœud particulier appelé racine.

★ À maîtriser

• En informatique, un arbre enraciné sert de modèle hiérarchique de représentation de l’information ou de structure de données.

Compléments

• Le système de fichiers sous UNIX et les rencontres d’un tournoi sportif sont des exemples de structures représentables par des arbres.

• Les relations hiérarchiques comprennent :

  • prédécesseur-successeur
  • ancêtre-descendant
  • parent-enfant

• Les arêtes d’un arbre peuvent être orientées du haut vers le bas en partant de la racine.

💡 Astuce mémo

Imaginez la racine en haut et les liens hiérarchiques qui descendent vers les feuilles.

📖 2. Mesures et repères dans l’arbre

🔑 Notions clés & Définitions

• Taille d’un arbre : Nombre de nœuds de l’arbre ; un arbre vide a une taille de 0.
• Degré d’un nœud : Nombre de fils que possède le nœud.
• Arbre binaire : Arbre dont tous les nœuds ont un degré d’au plus 2 ; ses fils sont distingués comme fils gauche et fils droit.
• Profondeur d’un nœud : Distance du chemin qui relie la racine au nœud ; la racine est à la profondeur 0 et chaque fils a une profondeur supérieure d’une unité à celle de son père.
• Hauteur d’un arbre : Profondeur maximale des nœuds ; elle vaut 0 pour un arbre de taille 1 et −1 pour un arbre vide.
• Niveau d’un arbre : Ensemble des nœuds dont la profondeur est k.

★ À maîtriser

📌 Une feuille est un nœud de degré 0, tandis qu’un nœud interne est de degré au moins 1.

Compléments

📐 Formule - Pour un arbre binaire de taille $n \geq 1$ et de hauteur $h$, la hauteur vérifie $\log_2 n \leq h \leq n - 1$.

💡 Astuce mémo

Depuis la racine, la profondeur augmente d’un cran par père ; la hauteur est la profondeur maximale.

📖 3. Formes particulières des arbres binaires

🔑 Notions clés & Définitions

• Arbre localement complet : Arbre binaire sans aucun nœud de degré 1.
• Arbre filiforme : Arbre binaire dont tous les nœuds ont un degré d’au plus 1.
• Arbre complet : Arbre binaire dont toutes les feuilles sont à la même profondeur et dont chaque niveau est entièrement rempli.
• Arbre parfait : Arbre binaire dont les niveaux jusqu’à l’avant-dernier sont complètement remplis et dont les nœuds du dernier niveau sont alignés à gauche.
• Peigne gauche : Arbre binaire localement complet dans lequel tout fils droit est une feuille.

★ À maîtriser

📐 Formule - Un arbre binaire localement complet de taille $n$ possède $\frac{n+1}{2}$ feuilles et $\frac{n-1}{2}$ nœuds internes.

Compléments

• Un arbre filiforme possède toujours une seule feuille.

• Dans un arbre complet de profondeur P, le niveau k comporte $2^k$ nœuds pour chaque $k \in [0..P]$.

📐 Formule - Le cours donne pour un arbre binaire parfait de taille $n$ la relation $h = \log_2 n$ entre sa hauteur et sa taille.

📐 Formule - La taille d’un arbre binaire complet de hauteur $h$ vérifie $n = 2^{h+1} - 1$.

💡 Astuce mémo

Le filiforme n’a que des degrés 0 ou 1 ; le localement complet exclut le degré 1.

📖 4. Arbres binaires étiquetés

🔑 Notions clés & Définitions

• Arbre binaire étiqueté : Arbre binaire soit vide, noté (), ∅ ou Λ, soit de la forme (r, T1, T2), où r est une valeur de type Element et T1 et T2 sont ses sous-arbres gauche et droit.

📝 Points essentiels

📌 Dans la représentation (r, T1, T2), les arbres (r, T′, Λ) et (r, Λ, T′) sont distincts, car la position gauche ou droite du fils est conservée.

💡 Astuce mémo

Dans (r, T1, T2), T1 est à gauche et T2 à droite : les deux positions ne sont pas interchangeables.

📖 5. Représentation chaînée en C++

★ À maîtriser

• Dans l’implémentation chaînée présentée, chaque nœud contient une valeur et deux pointeurs, sag et sad, vers les sous-arbres gauche et droit.

• Dans cette implémentation chaînée, un arbre vide est représenté par un pointeur Null.

Compléments

• Les opérations dépendantes du type d’arbre sont :

  • l’ajout
  • la suppression
  • l’accès

• Les arbres parfaits peuvent être implémentés au moyen d’un tableau, comme les tas binaires.

📖 6. Création et affichage des arbres

★ À maîtriser

• La fonction estVide teste si l’arbre vaut nullptr ; creerArbre() renvoie nullptr, tandis que creerArbre(e, G, D) alloue un nœud contenant e et les pointeurs G et D.

• La fonction detruire détruit récursivement les sous-arbres gauche et droit d’un nœud non nul, puis libère ce nœud avec delete.

Compléments

• La fonction affichage_parenthese encadre l’arbre de parenthèses et affiche récursivement la valeur de chaque nœud, son sous-arbre gauche puis son sous-arbre droit.

💡 Astuce mémo

Construire un nœud avec sa valeur et ses deux sous-arbres, puis afficher récursivement gauche et droite.

📖 7. Parcours en largeur

🔑 Notions clés & Définitions

• Parcours en largeur : Traitement des nœuds par niveaux croissants, puis de gauche à droite au sein de chaque niveau.

📝 Points essentiels

• Le parcours en largeur s’implémente itérativement au moyen d’une file.

💡 Astuce mémo

Niveau après niveau, puis de gauche à droite : une file accompagne l’exploration.

📖 8. Parcours en profondeur

🔑 Notions clés & Définitions

• Parcours en profondeur : Parcours entier du sous-arbre gauche de chaque nœud avant celui du sous-arbre droit.

★ À maîtriser

• Un parcours en profondeur s’implémente naturellement par récursion ou, de manière itérative, au moyen d’une pile.

📌 En préfixe, la racine est traitée avant le sous-arbre gauche ; en infixe, elle est traitée après le sous-arbre gauche et avant le sous-arbre droit ; en postfixe, elle est traitée après le sous-arbre droit.

Compléments

• Chaque nœud est visité : en descendant, en remontant après le parcours du sous-arbre gauche, éventuellement vide, en remontant après le parcours du sous-arbre droit, éventuellement vide

• Par convention, un parcours en profondeur explore le sous-arbre gauche avant le sous-arbre droit ; une variante dite main droite explore d’abord les sous-arbres droits.

💡 Astuce mémo

Préfixe : racine avant gauche ; infixe : entre gauche et droite ; postfixe : après droite.

📊 Tableaux de synthèse

Comparaison des parcours

Ordres du parcours en profondeur