Fiche de révision : Introduction aux arbres et leurs parcours

📋 Plan du Cours

1. Définition arbre
2. Caractéristiques arbres
3. Arbres binaires
4. Parcours arbres binaires
5. Implémentation en POO
6. Représentation par tuples
7. Tas binaire
8. Arbre binaire de recherche
9. Arbres de jeu
10. Arbres d'expressions arithmétiques
11. Arbres syntaxiques
12. Parcours largeur

📖 1. Définition arbre

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique composée de nœuds, où chaque nœud peut avoir un ou plusieurs fils, organisé de façon à représenter une hiérarchie ou une relation parent-enfant.

• Nœud racine : Nœud principal d’un arbre, sans parent, point de départ de la hiérarchie.

• Feuille (ou nœud externe) : Nœud sans fils, situé en extrémité de l’arbre.

• Nœud interne : Nœud ayant au moins un fils, représentant une étape intermédiaire ou une décision dans la hiérarchie.

• Arité (ou degré d’un nœud) : Nombre de fils d’un nœud. La taille d’un arbre est le nombre total de nœuds qu’il contient.

• Profondeur : Distance (en nombre d’arcs) entre un nœud et la racine. La racine a une profondeur 0.

📝 Points essentiels

• Chaque nœud a un seul père, sauf la racine qui n’en a pas.
• La hauteur d’un arbre correspond à la profondeur du nœud le plus profond ou à la longueur du plus long chemin de la racine à une feuille.
• Les arbres binaires sont un cas particulier où chaque nœud a au plus deux fils, généralement appelés gauche et droit.
• La structure d’un arbre peut être représentée par des listes ou des tuples imbriqués, ou en programmation orientée objet avec des classes.
• Les parcours d’un arbre (largeur ou profondeur) permettent de visiter tous ses nœuds dans un ordre précis.

💡 À retenir

Un arbre est une structure hiérarchique composée de nœuds reliés par des relations parent-enfant, permettant de représenter efficacement des données organisées en niveaux ou en branches.

📖 2. Caractéristiques arbres

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique constitué de nœuds, où chaque nœud peut avoir un ou plusieurs fils, et un seul nœud racine. Chaque nœud, sauf la racine, possède un seul père.
• Nœud racine : Nœud en haut de l’arbre, sans père.
• Feuille (nœud externe) : Nœud sans fils, situé en extrémité de l’arbre.
• Nœud interne : Nœud ayant au moins un fils.
• Arité ou degré d’un nœud : Nombre de fils d’un nœud.
• Profondeur d’un nœud : Distance en nombre d’arêtes entre ce nœud et la racine (racine = profondeur 0).
• Hauteur d’un arbre : Longueur du plus long chemin de la racine à une feuille. Peut être définie comme le nombre de niveaux ou la profondeur maximale d’un nœud.

📝 Points essentiels

• Organisation hiérarchique : Un arbre est une structure non linéaire où chaque nœud, sauf la racine, a un seul père, mais peut avoir plusieurs fils.
• Caractéristiques des nœuds :
  • La racine n’a pas de père.
  • Les feuilles n’ont pas de fils.
  • La relation entre nœuds frères : deux nœuds ayant le même père.
• Types d’arbres spécifiques :
  • Arbre binaire : chaque nœud a au plus deux fils (gauche et droit).
  • Arbre équilibré : différence de hauteur entre sous-arbres gauche et droit ≤ 1.
  • Arbre complet : tous les niveaux sauf éventuellement le dernier sont remplis, et les feuilles du dernier niveau sont tassées à gauche.
• Parcours d’un arbre :
  • Largeur d’abord (niveau par niveau) : exploration étage par étage, de gauche à droite.
  • Profondeur d’abord : exploration complète d’un sous-arbre avant de passer au suivant, avec trois types :
    • Préfixe (préordre) : visiter le nœud avant ses fils.
    • Infixe (inordre) : visiter le fils gauche, puis le nœud, puis le fils droit.
    • Postfixe (postordre) : visiter les fils avant le nœud.

💡 À retenir

Un arbre est une structure hiérarchique où chaque nœud a un seul père, sauf la racine, et où la hauteur et la profondeur permettent de caractériser la position des nœuds. Les parcours permettent d’explorer l’arbre selon différents ordres, essentiels pour diverses applications en informatique.

📖 3. Arbres binaires

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique constitué de nœuds, où chaque nœud peut avoir zéro ou plusieurs fils, avec un seul nœud racine.
• Nœud : Élément de l’arbre, pouvant contenir une étiquette ou valeur.
• Feuille (Noeud externe) : Nœud sans fils, en fin de branche.
• Nœud interne : Nœud ayant au moins un fils.
• Arité (degré) : Nombre de fils d’un nœud.
• Profondeur d’un nœud : Distance entre ce nœud et la racine (niveau).
• Hauteur d’un arbre : Longueur du plus long chemin de la racine à une feuille.
• Arbre binaire : Arbre où chaque nœud possède au plus deux fils, généralement appelés fils gauche et droit.
• Parcours en largeur : Visite des nœuds niveau par niveau, de gauche à droite.
• Parcours en profondeur : Exploration complète d’un sous-arbre avant de passer à un autre, avec trois types : préfixe, infixe, postfixe.

📝 Points essentiels

• La racine est le seul nœud sans père, profondeur = 0.
• La taille d’un arbre correspond au nombre total de nœuds.
• La hauteur d’un arbre binaire équilibré est logarithmique en fonction du nombre de nœuds, ce qui optimise la recherche.
• Les parcours permettent de visiter tous les nœuds dans un ordre précis :
  • Préfixe (préordre) : racine, sous-arbre gauche, sous-arbre droit.
  • Infixe (ordre) : sous-arbre gauche, racine, sous-arbre droit.
  • Postfixe (postordre) : sous-arbre gauche, sous-arbre droit, racine.
• La représentation en POO d’un arbre binaire se fait via une classe avec attributs pour l’étiquette, fils gauche et fils droit.

💡 À retenir

Les arbres binaires sont des structures hiérarchiques essentielles en informatique, permettant notamment la recherche efficace, la représentation d’expressions arithmétiques et la modélisation de jeux ou de syntaxe. Leur organisation et parcours optimisent la manipulation et l’analyse des données.

📖 4. Parcours arbres binaires

🔑 Notions clés & Définitions

• Arbre binaire : Un arbre dans lequel chaque noeud possède au plus deux fils, généralement appelés fils gauche et droit.
• Parcours en largeur (niveau) : Parcours qui visite les noeuds étage par étage, de gauche à droite à chaque niveau.
• Parcours en profondeur : Parcours qui explore complètement un sous-arbre avant de passer à un autre, selon l’ordre (préfixe, infixe, postfixe).
• Parcours préfixe (préordre) : Visite le noeud racine, puis le sous-arbre gauche, puis le sous-arbre droit.
• Parcours infixe (ordre) : Visite le sous-arbre gauche, le noeud racine, puis le sous-arbre droit.
• Parcours postfixe (postordre) : Visite le sous-arbre gauche, le sous-arbre droit, puis le noeud racine.

📝 Points essentiels

• La structure d’un arbre binaire peut être représentée en POO ou via des tuples imbriqués.
• La représentation en tuple : chaque noeud est un tuple (valeur, sous-arbre gauche, sous-arbre droit).
• La recherche dans un arbre binaire de recherche (ABR) se fait en comparant la clé avec la racine, puis en se déplaçant récursivement à gauche ou à droite selon le cas, avec une complexité en temps en O(h).
• Le parcours en largeur utilise une file, tandis que le parcours en profondeur peut être implémenté récursivement ou avec une pile.
• La structure d’un arbre binaire est essentielle pour des applications comme les tas, arbres de recherche, arbres d’expression, etc.

💡 À retenir

Les parcours d’un arbre binaire permettent d’accéder à ses noeuds dans un ordre précis, essentiel pour l’algorithmique et la manipulation de structures hiérarchiques. La distinction entre parcours en largeur et en profondeur est fondamentale pour leur utilisation dans différents contextes.

📖 5. Implémentation en POO

🔑 Notions clés & Définitions

• Classe : Modèle ou plan de construction d’un objet en programmation orientée objet (POO). Elle définit les attributs (données) et méthodes (fonctions) associées à un type d’objet.

• Objet : Instance concrète d’une classe, représentant une entité avec ses propres valeurs d’attributs. C’est la réalisation pratique du modèle défini par la classe.

• Encapsulation : Principe de POO consistant à regrouper données et méthodes dans une même unité (classe), tout en contrôlant l’accès à ces données via des méthodes spécifiques (getters, setters).

• Héritage : Mécanisme permettant de créer une nouvelle classe (sous-classe) à partir d’une classe existante (super-classe), en héritant ses attributs et méthodes, tout en pouvant en ajouter ou modifier.

• Polymorphisme : Capacité d’une méthode ou d’un opérateur à prendre différentes formes selon le contexte ou la classe de l’objet concerné, permettant une utilisation flexible et dynamique.

📝 Points essentiels

• La POO permet une modélisation intuitive des objets du monde réel via des classes et objets.
• La classe définit la structure et le comportement d’un type d’objet, tandis que l’objet est une instance concrète.
• La méthode est une fonction définie dans une classe, manipulant ses attributs ou réalisant des actions.
• La gestion de l’héritage facilite la réutilisation du code et la hiérarchisation des classes.
• La méthode d’accès (getters/setters) permet de contrôler la lecture et la modification des attributs privés.
• La relation "est-un" (héritage) favorise la spécialisation et la généralisation dans la conception.

💡 À retenir

L’implémentation en POO repose sur la définition de classes pour modéliser des objets, en utilisant l’héritage pour la réutilisation, l’encapsulation pour la sécurité, et le polymorphisme pour la flexibilité.

📖 6. Représentation par tuples

🔑 Notions clés & Définitions

• Tuple : Structure de données immuable en Python, permettant de stocker une collection ordonnée d’éléments. Utilisé pour représenter des arbres binaires de manière hiérarchique.

• Représentation par tuples d’un arbre binaire : Chaque nœud est un tuple de trois éléments : (étiquette, sous-arbre gauche, sous-arbre droit). Un arbre vide est représenté par un tuple vide ().

• Noeud : Élément d’un arbre, constitué d’une étiquette (valeur ou clé) et de deux sous-arbres (gauche et droit).

• Arbre vide : Représenté par un tuple vide (), indiquant l’absence de nœud ou de sous-arbre.

• Parcours d’un arbre : Méthode pour visiter tous les nœuds selon un ordre précis (préfixe, infixe, postfixe), permettant d’extraire ou d’afficher les données.

📝 Points essentiels

• La structure en tuples permet une représentation simple et efficace des arbres binaires, facilitant leur manipulation en programmation sans classes.
• La récursivité est essentielle pour parcourir ou manipuler ces arbres, notamment pour les parcours (préfixe, infixe, postfixe).
• La représentation par tuples est particulièrement adaptée pour l’implémentation de structures comme les tas, arbres de recherche, ou arbres d’expression.
• La fonction récursive de parcours préfixe affiche ou traite les nœuds dans l’ordre : racine, sous-arbre gauche, sous-arbre droit.
• La structure hiérarchique en tuples permet de facilement imbriquer des arbres pour représenter des expressions arithmétiques ou des arbres syntaxiques.

💡 À retenir

La représentation d’un arbre binaire par tuples offre une méthode simple, efficace et facilement manipulable pour modéliser des structures hiérarchiques en programmation, en utilisant la récursion pour leur parcours et leur traitement.

📖 7. Tas binaire

🔑 Notions clés & Définitions

• Tas binaire : Un arbre binaire complet où chaque nœud respecte la propriété de priorité (max ou min), c’est-à-dire que la valeur du nœud racine est supérieure (tas max) ou inférieure (tas min) à celles de ses enfants, et que ses sous-arbres sont également des tas.
• Tas-max / Tas-min : Structure de tas binaire où la racine possède la valeur maximale (tas max) ou minimale (tas min) par rapport à ses descendants, permettant une gestion efficace des files de priorité.
• Arbre binaire complet : Un arbre binaire où tous les niveaux sont remplis sauf éventuellement le dernier, qui est tassé à gauche.
• Propriété de heap : La propriété qui garantit que pour chaque nœud, sa valeur est supérieure ou égale (tas max) ou inférieure ou égale (tas min) à celles de ses enfants.
• Utilisations : Tri par tas (tri efficace), gestion de files de priorité, implémentation efficace de structures de données dynamiques.

📝 Points essentiels

• Un tas binaire est une structure d’arbre binaire complet respectant la propriété de priorité.
• La racine d’un tas max est toujours le maximum de l’arbre, et celle d’un tas min est le minimum.
• La construction et la maintenance d’un tas se font via des opérations d’insertion, de reheapification (descente ou montée), et de suppression de la racine.
• La complexité des opérations principales (insertion, suppression) est en O(log n), grâce à la hauteur logarithmique de l’arbre.
• Le tri par tas consiste à construire un tas, puis à échanger la racine avec le dernier nœud, réduire la taille du tas, et rétablir la propriété de heap.

💡 À retenir

Un tas binaire est une structure hiérarchique permettant de gérer efficacement des priorités, notamment dans le tri et la gestion de files de priorité, grâce à ses opérations en logarithmique.

📖 8. Arbre binaire de recherche

🔑 Notions clés & Définitions

• Arbre binaire : Structure hiérarchique composée de nœuds, chaque nœud ayant au plus deux fils, appelés fils gauche et droit.
• Arbre binaire de recherche (ABR) : Arbre binaire où, pour chaque nœud, les clés du sous-arbre gauche sont inférieures ou égales à la clé du nœud, et celles du sous-arbre droit sont strictement supérieures.
• Noeud racine : Nœud supérieur d’un arbre, point de départ des parcours.
• Feuille : Nœud sans fils, situé en extrémité de l’arbre.
• Parcours en profondeur : Visite des nœuds selon un ordre spécifique (préfixe, infixe, postfixe), explorant entièrement un sous-arbre avant de passer à un autre.
• Parcours en largeur : Exploration étage par étage, de la racine vers les feuilles, de gauche à droite.

📝 Points essentiels

• La structure d’un ABR permet une recherche efficace d’un élément en temps logarithmique si l’arbre est équilibré.
• La propriété de l’ordre (gauche ≤ nœud < droit) facilite l’insertion, la suppression et la recherche.
• La hauteur de l’arbre influence la complexité : un arbre équilibré a une hauteur proche de log₂(n), assurant une recherche rapide.
• Les parcours (préfixe, infixe, postfixe, largeur) permettent d’explorer ou de traiter tous les nœuds dans un ordre spécifique.
• La représentation d’un arbre peut se faire via des objets en programmation orientée ou par des tuples imbriqués.

💡 À retenir

L’arbre binaire de recherche est une structure hiérarchique optimisée pour la recherche, l’insertion et la suppression d’éléments, grâce à ses propriétés d’ordre et d’équilibre. Son efficacité dépend de sa hauteur, qui doit être maintenue la plus faible possible.

📖 9. Arbres de jeu

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique composée de nœuds où chaque nœud peut avoir un ou plusieurs fils, avec un seul nœud racine. Chaque nœud peut contenir une information ou une étiquette.
• Nœud racine : Nœud supérieur de l’arbre, sans père.
• Feuille (noeud externe) : Nœud sans fils, représentant une fin de branche ou une position terminale.
• Nœud interne : Nœud ayant au moins un fils, représentant une position intermédiaire ou un coup dans un jeu.
• Arbre binaire de jeu : Arbre où chaque nœud a au plus deux fils, représentant les coups possibles dans un jeu.
• Profondeur d’un nœud : Distance entre ce nœud et la racine, en comptant le nombre d’arcs.
• Hauteur d’un arbre : La profondeur maximale parmi tous les nœuds, correspondant au nombre de coups jusqu’à une position terminale.

📝 Points essentiels

• Les arbres de jeu modélisent toutes les positions possibles d’un jeu, chaque branche représentant une séquence de coups.
• La construction d’un arbre de jeu permet d’analyser toutes les stratégies possibles, notamment pour déterminer le coup optimal.
• La notion de nœud terminal correspond à une position finale où le jeu se termine, souvent associée à une victoire ou une défaite.
• La recherche dans un arbre de jeu peut se faire par parcours en largeur (niveau par niveau) ou en profondeur (exploration complète d’une branche avant de passer à la suivante).
• La structure d’un arbre binaire de jeu est souvent utilisée pour représenter des jeux à deux joueurs, avec des stratégies minimax pour déterminer le meilleur coup.

💡 À retenir

Les arbres de jeu sont des outils essentiels pour analyser toutes les possibilités d’un jeu, permettant d’anticiper les coups adverses et de déterminer la stratégie optimale.

📖 10. Arbres d'expressions arithmétiques

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique composée de nœuds, où chaque nœud peut avoir un ou plusieurs fils, organisé de façon à représenter une relation parent-enfant.
• Nœud racine : Nœud supérieur d’un arbre, sans parent.
• Feuille : Nœud sans fils, généralement représentant une valeur ou une donnée terminale.
• Nœud interne : Nœud ayant au moins un fils, souvent représentant un opérateur dans une expression arithmétique.
• Arbre binaire : Arbre où chaque nœud a au plus deux fils, souvent ordonnés (gauche/droit).
• Arbre d’expression : Arbre représentant une expression arithmétique, où les nœuds internes sont des opérateurs et les feuilles des opérandes (nombres).

📝 Points essentiels

• Représentation des expressions : Les arbres d’expression permettent de visualiser la priorité des opérations sans parenthèses, en organisant les opérateurs et opérandes selon leur hiérarchie.
• Parcours d’un arbre :
  • Préfixe (préordre) : Visite le nœud parent avant ses fils (ex : +, puis ses deux opérandes).
  • Infixe (ordre) : Visite le fils gauche, le nœud, puis le fils droit (ex : opérande, opérateur, opérande).
  • Postfixe (postordre) : Visite les fils avant le nœud (ex : opérandes, puis opérateur).
• Utilisation dans l’évaluation : La structure permet d’évaluer facilement une expression en parcourant l’arbre dans l’ordre postfixe ou en utilisant une pile.
• Construction : Peut être réalisée à partir d’une expression en notation infixe ou postfixe, ou directement via un algorithme de construction.
• Opérations sur arbres : Insertion, suppression, parcours, évaluation, simplification.

💡 À retenir

Les arbres d’expression arithmétiques structurent efficacement les opérations pour une évaluation claire, en respectant la priorité et la associativité des opérateurs, facilitant leur traitement algorithmique.

📖 11. Arbres syntaxiques

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique constitué de nœuds, où chaque nœud peut avoir un ou plusieurs fils, organisé de façon à représenter des relations hiérarchiques ou syntaxiques.
• Noeud racine : Nœud supérieur de l’arbre, sans père, point de départ de la hiérarchie.
• Feuille (Noeud externe) : Nœud sans fils, généralement terminal dans la structure, représentant une donnée ou un symbole terminal.
• Noeud interne : Nœud ayant au moins un fils, représentant une opération ou une relation dans l’arbre.
• Parcours d’arbre : Méthode de visite des nœuds selon un ordre précis, notamment en largeur (niveau par niveau) ou en profondeur (préfixe, infixe, postfixe).
• Arbre binaire : Arbre où chaque nœud possède au plus deux fils, souvent appelés fils gauche et droit.

📝 Points essentiels

• La hauteur d’un arbre est la longueur du plus long chemin de la racine à une feuille. La profondeur d’un nœud est la distance entre ce nœud et la racine.
• Un arbre binaires équilibrés possède des sous-arbres dont la hauteur diffère de 1 maximum, ce qui optimise la recherche.
• La représentation par tuples permet d’imbriquer des structures d’arbres binaires de manière simple, avec un nœud sous la forme (valeur, sous-arbre gauche, sous-arbre droit).
• Les parcours en profondeur :
  • Préfixe (préordre) : Visite la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
  • Infixe (ordre) : Visite le sous-arbre gauche, la racine, puis le sous-arbre droit.
  • Postfixe (postordre) : Visite le sous-arbre gauche, le sous-arbre droit, puis la racine.
• Les arbres syntaxiques représentent la structure grammaticale ou syntaxique d’un programme ou d’une expression, facilitant l’analyse et la compilation.

💡 À retenir

Les arbres syntaxiques sont des représentations hiérarchiques essentielles pour analyser la structure d’un code ou d’une expression, permettant une compréhension claire des relations entre ses composants. Leur parcours et leur manipulation sont fondamentaux en informatique pour l’interprétation et la compilation.

📖 12. Parcours largeur

🔑 Notions clés & Définitions

• Parcours en largeur (ou parcours en niveau) : Méthode de traversée d’un arbre où l’on visite tous les nœuds d’un niveau avant de passer au niveau suivant, en allant de la racine vers les feuilles, de gauche à droite à chaque niveau.

• File (ou queue) : Structure de données utilisée pour réaliser le parcours en largeur, permettant de stocker les nœuds à explorer dans l’ordre d’arrivée.

• Niveau d’un nœud : La distance en nombre d’arêtes entre ce nœud et la racine, la racine ayant un niveau 0.

• Algorithme de parcours en largeur : Processus consistant à insérer la racine dans une file, puis à explorer chaque nœud en défilant la file, en ajoutant ses fils à la fin de la file.

• Complexité : Le parcours en largeur a une complexité en temps de O(n), où n est le nombre de nœuds de l’arbre, car chaque nœud est visité une seule fois.

📝 Points essentiels

• Le parcours en largeur permet d’explorer un arbre de manière systématique, étage par étage, ce qui est utile pour la recherche du plus court chemin dans un graphe ou pour la recherche d’un nœud spécifique.

• La structure de données clé est la file : on y insère (enfiler) les nœuds à explorer et on en retire (défiler) pour traiter.

• Lors du traitement d’un nœud, ses fils sont ajoutés à la file dans l’ordre de gauche à droite, garantissant une exploration de niveau.

• La méthode est souvent utilisée dans les algorithmes de recherche de chemin, de détection de cycles, ou pour générer une représentation en niveaux d’un arbre.

💡 À retenir

Le parcours en largeur explore un arbre niveau par niveau à l’aide d’une file, garantissant une visite exhaustive et ordonnée de tous les nœuds, ce qui le rend idéal pour la recherche du plus court chemin ou la génération de niveaux.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre arbre et graphe : un arbre est un graphe acyclique connecté, mais tous les graphes ne sont pas des arbres.
2. Mauvaise compréhension de la racine : la racine n’a pas de parent, mais certains oublient que la racine peut être n’importe quel nœud dans un sous-arbre.
3. Confusion entre nœud interne et feuille : une feuille n’a pas de fils, un nœud interne en a au moins un.
4. Faux-amis : « degré » d’un nœud (nombre de fils) vs « degré » d’un sommet dans un graphe.
5. Parcours en profondeur : confondre préfixe, infixe et postfixe, ou ne pas respecter l’ordre.
6. Mauvaise représentation en tuple : oublier que chaque tuple doit contenir la valeur et ses sous-arbres.
7. Confusion entre arbre binaire et arbre binaire de recherche : ABR impose une règle de tri, pas juste deux fils.

✅ Checklist Examen

• Définir un arbre et ses composants (racine, feuille, nœud interne).
• Expliquer la différence entre arbre et graphe.
• Décrire la notion de hauteur et de profondeur dans un arbre.
• Identifier un arbre binaire et ses caractéristiques.
• Décrire les trois parcours en profondeur (préfixe, infixe, postfixe).
• Expliquer la représentation d’un arbre binaire en tuple.
• Définir un arbre binaire de recherche et sa propriété de tri.
• Décrire le fonctionnement d’un tas binaire et ses applications.
• Expliquer la différence entre parcours en largeur et en profondeur.
• Illustrer la représentation d’un arbre en POO.
• Décrire la construction d’un arbre équilibré.
• Vérifier la maîtrise du vocabulaire spécifique : racine, feuille, nœud interne, degré, hauteur, profondeur.
• Connaître la complexité des parcours en fonction de la taille de l’arbre.