Les Arbres :
Preparé par : Sous l'encadrement de :
Latifa Aarab M.Hisham Elmoubtahij
Yasmine Elhandia
Douae Benhilal
Le plan :
01 02 03
Introduction Arbres binaires Algorithmes de
Parcours
04 05
Arbres de Quiz
recherche
introduction
1. Un arbre est une structure de données utilisée pour
organiser des éléments de manière hiérarchique. Il est
composé de nœuds connectés entre eux sans former de
cycles.
01
Les arbres binaires :
02
Arbres binaires
Un arbre binaire est un type d’arbre où
chaque nœud a aux plus deux
enfants : un fils gauche et un fils
droit.
Algorithmes de
Parcours :
03
Definition algorihmes de parcours:
Les algorithmes de parcours d'arbres sont des méthodes
systématiques pour visiter chaque nœud d'une structure d'arbre.
Ces algorithmes sont fondamentaux en informatique et sont
utilisés pour explorer, rechercher, ou manipuler des données
stockées dans des arbres.
Il existe principalement deux types de parcours d'arbres : le
parcours en profondeur (Depth-First Search, DFS) et le
parcours en largeur (Breadth-First Search, BFS).
C’est quoi le BFS(breadth first search)?
Le parcours en largeur (BFS) est un parcours qui explore
tous les nœuds niveau par niveau, en partant de la racine et
en visitant chaque niveau de l'arbre de gauche à droite avant
de passer au niveau suivant.
Code couleur
couleur bleu : Sommet non noté
couleur noir : Sommet découvert
couleur rouge : Sommet terminé
Exemple d’un arbre binaire suivant le BFS:
● Parcours BFS :
A→B→F→C→D→G→H→E→I→J
Parcours en profondeur (Depth-First Search,
DFS)
C’est quoi le DFS(depth first search)?
Le DFS (Depth First Search), ou recherche en profondeur, est un
algorithme de parcours utilisé pour explorer un graphe ou un arbre. Il
explore une branche aussi profondément que possible avant de
revenir en arrière (backtracking).
Exemple d’un arbre binaire suivant le
DFS:
Parcours in-order
Parcours en profondeur infixe (In-order) = GND :
Dans ce type de parcours, on visite d'abord le sous-arbre
gauche , puis le nœud courant, et enfin le sous-arbre droit.
Pour un arbre binaire, le parcours se fait selon l'ordre
suivant :
Gauche → Nœud → Droit (GND).
Parcours en profondeur infixe (In-order) :
427581396
Exemple du parcous en ordre
Le parcours post-order :
Parcours en profondeur préfixe (Post-order) = GDN :
Dans ce type de parcours, on visite le nœud avant de visiter
ses enfants. Pour un arbre binaire, le parcours se fait selon
l'ordre suivant : sous-arbre gauche → sous-arbre droit. →
racine
Parcours en profondeur préfixe (Post-order) :
124578369
Exemple post ordre
Le parcours pre-ordre :
Parcours en profondeur postfixe (pre-order)= NGD :
Dans ce type de parcours, on visite les enfants d'un nœud
avant de visiter le nœud lui-même. Pour un arbre binaire, le
parcours se fait selon l'ordre suivant : racine →
sous-arbre gauche → sous-arbre droit → racine.
Parcours en profondeur prefixe (pré-order) :
478529631
Exemple parcours pre-order
Arbres de recherche :
04
Définition
Une arbre binaire de recherche est une structure de donnée
dynamique avec une organisation hiérarchique qui respecte les
règles suivantes :
• Tous les nœuds du sous-arbre gauche ont une valeur
inférieure à celle du nœud parent.
• Tous les nœuds du sous-arbre droit ont une valeur
supérieure à celle du nœud parent.
• Chaque nœud peut avoir jusqu'à deux nœuds fils
Recherche d’une valeur dans un arbre binaire k=10
Implémentation d'un arbre de recherche binaire
Exemple d'utilisation d'un arbre de recherche
Exemple
Pré-ordre In-ordre Post-ordre
Explication de l'exemple
• Affichage in-ordre : Cela produit une sortie triée des valeurs, ce
qui est utile pour vérifier l'ordre des éléments dans un arbre de
recherche.
• Affichage pré-ordre : Cela montre l'ordre dans lequel les nœuds
sont visités, ce qui peut être utile pour des opérations comme la
sauvegarde de l'arbre.
• Affichage post-ordre : Cela montre l'ordre de traitement des
nœuds, utile pour des opérations comme la suppression de
l'arbre.
Q1. Quelle est la principale caractéristique d'un arbre binaire ?
a) Chaque nœud a au plus trois enfants
b) Chaque nœud a au plus deux enfants
c) Chaque nœud a exactement deux enfants
d) Chaque nœud n'a qu'un seul enfant
Q2. Dans un arbre binaire de recherche (BST), où se trouvent
les valeurs inférieures à celle du nœud courant ?
a) Dans le sous-arbre droit
b) Dans le sous-arbre gauche
c) Dans les feuilles uniquement
d) Réparties de manière aléatoire
Q3. Quel type de parcours parcourt l'arbre niveau par niveau ?
a) Parcours en largeur (BFS)
b) Parcours en profondeur (DFS)
c) Parcours in-ordred) Parcours post-ordre
Q4. Quelle méthode de parcours retourne les éléments dans
l'ordre croissant pour un arbre de recherche ?
a) Post-ordre
b) In-ordred) BFS
c) Pré-ordre
Q5. Quelle est la définition correcte de la racine dans un arbre ?
a) Un nœud sans enfants
b) Un nœud qui a exactement deux enfants
c) Le nœud supérieur de l'arbre, sans parent
d) Le nœud avec la plus grande valeur
Q6. Dans un arbre binaire de recherche, que se passe-t-il si vous
tentez d'insérer une valeur qui existe déjà ?
a) La valeur est ajoutée dans le sous-arbre gauche
b) La valeur est ajoutée dans le sous-arbre droit
c) La valeur est ignorée ou refusée
d) L'arbre est réorganisé automatiquement
Q7. Quel parcours est particulièrement utile pour supprimer
tous les nœuds d'un arbre de bas en haut ?
a) Pré-ordre
b) In-ordre
c) Post-ordre
d) BFS
Q8. Si vous insérez les valeurs suivantes dans un BST : 50, 30,
70, 20, 40, 60, 80, quel sera le parcours in-ordre ?
a) 50 30 20 40 70 60 80
b) 20 30 40 50 60 70 80
c) 80 70 60 50 40 30 20
d) 30 20 40 50 60 70 80
Q9. Quelle structure de données est généralement utilisée pour
implémenter le parcours en largeur (BFS) ?
a) Une pile
b) Une file
c) Un tableau
d) Une liste chaînée
Q10. Quelle est la hauteur d'un arbre contenant seulement la
racine ?
a) 0
b) 1
c) 2
d) Infinie
Merci pour votre
attention
