Les arbres
Un arbre est un cas particulier de graphe.
Un graphe est composé de nœuds (sommets) reliés par des arêtes.
Un arbre est un graphe :
- connexe (tous les nœuds sont reliés entre eux),
- acyclique (pas de cycle),
- possédant exactement n − 1 arêtes pour n nœuds.
On peut voir un arbre comme un graphe organisé de manière hiérarchique.
Vocabulaire
Considérons un arbre ayant un nœud principal noté A.
- Noeud
- Arête
- Racine
- Fils
- Père
- Feuille
- Sous-arbre
Élément de base de l’arbre.
Lien entre deux nœuds.
Nœud de départ de l’arbre.
B et C sont reliés à A, A est donc la racine.
Noeud directement en dessous d’un autre nœud.
B et C sont fils de A.
Noeud directement au-dessus d’un autre nœud.
A est le père de B.
Nœud sans fils.
D, E et F sont des feuilles.
Un arbre formé à partir d’un nœud et de tous ses descendants.
L'arbre formé à partir de B :
est un sous-arbre de l’arbre A.
Dans un arbre :
- chaque nœud (sauf la racine) possède un unique père,
- un nœud peut avoir plusieurs fils.
Exemples d’arbres dans la vie courante
- Tournoi
- Arbre généalogique
- Arborescence de fichiers
Un tableau de tournoi (tennis, e-sport…) est organisé sous forme d’arbre.
Chaque personne est reliée à ses parents.
L’organisation des dossiers sur un ordinateur est un arbre :
- un dossier racine,
- des sous-dossiers,
- des fichiers (souvent des feuilles).
Arbre binaire
Un arbre binaire est un arbre particulier dans lequel :
- chaque nœud possède au maximum deux fils,
- appelés :
- fils gauche,
- fils droit.
Les fils gauche et droit sont eux-mêmes des sous-arbres.
⚠️ Un arbre binaire n’est pas forcément équilibré.
Taille d’un arbre
La taille d’un arbre est le nombre total de nœuds.
Exemple : Si l’arbre contient 10 nœuds → taille = 10.
Profondeur d’un nœud
La profondeur d’un nœud est le nombre de nœuds (ou d’arêtes selon la convention) du chemin entre la racine et ce nœud.
Exemple : Si le chemin est : A → F → G
Profondeur de G = 3 (en comptant les nœuds).
Hauteur d’un arbre
La hauteur d’un arbre est la profondeur maximale parmi tous les nœuds.
Autrement dit :
longueur du plus long chemin entre la racine et une feuille.
Parcours d’un arbre
Parcourir un arbre consiste à visiter tous les nœuds dans un certain ordre.
Les parcours utilisent très naturellement la récursivité.
- Parcours infixe
- Parcours préfixe
- Parcours suffixe
- Parcours en largeur (BFS)
Ordre : gauche → racine → droit
S'il existe un fils gauche, on le visite d'abord.
Ensuite, on visite la racine.
Enfin, s'il existe un fils droit, on le visite.
Ordre : racine → gauche → droit
On visite d'abord la racine.
Ensuite, s'il existe un fils gauche, on le visite.
Enfin, s'il existe un fils droit, on le visite.
Ordre : gauche → droit → racine
S'il existe un fils gauche, on le visite d'abord.
Ensuite, s'il existe un fils droit, on le visite.
Enfin, on visite la racine.
Le parcours en largeur visite les nœuds niveau par niveau.
On utilise une file (FIFO).
Mettre la racine dans la file.
Tant que la file n’est pas vide :
- Retirer un élément (nœud courant)
- L’afficher
- Ajouter ses fils dans la file