Travaux Pratiques : Construction et Parcours
d’Arbres Binaires en C
AeroSup
February 20, 2025
1 Objectifs Pédagogiques
Ce TP a pour but de vous familiariser avec :
• La structure et la manipulation des arbres binaires de recherche
(BST).
• L’insertion des éléments dans un arbre binaire.
• L’affichage des éléments selon différents parcours.
• L’utilisation des files pour le parcours niveau par niveau (BFS).
2 Introduction aux Arbres Binaires de Recherche
(BST)
Un BST est un type d’arbre binaire qui suit ces règles :
• Chaque nœud contient une valeur.
• Tout élément plus petit que la racine est placé à gauche.
• Tout élément plus grand ou égal à la racine est placé à droite.
Exemple : Construction du BST à partir de {5, 3, 8, 1, 4, 7, 10}
5
/ \
3 8
/\ /\
1 4 7 10
1
3 Activité 1 : Implémentation d’un Arbre Bi-
naire en C
3.1 Définition de la structure d’un nœud
En langage C, un nœud d’arbre est une structure contenant :
• Un entier (valeur du nœud).
• Deux pointeurs (vers le sous-arbre gauche et le sous-arbre droit).
À faire : Écrire une structure Node représentant un nœud d’arbre.
1 // D f i n i t i o n de la structure d ’ un n u d d ’ arbre binaire
2 typedef struct Node {
3 int data ;
4 struct Node * left ;
5 struct Node * right ;
6 } Node ;
3.2 Création d’un nouveau nœud
À faire : Compléter la fonction pour créer un nœud.
1 // Fonction pour c r e r un nouveau n u d
2 Node * createNode ( int value ) {
3 Node * newNode = ( Node *) malloc ( sizeof ( Node ) ) ;
4 newNode - > data = value ;
5 newNode - > left = NULL ;
6 newNode - > right = NULL ;
7 return newNode ;
8 }
3.3 Insertion d’un élément dans un BST
À faire : Implémenter l’insertion dans un BST.
1 // Fonction pour i n s r e r un lment dans un BST
2 Node * insert ( Node * root , int value ) {
3 if ( root == NULL )
4 return createNode ( value ) ;
5
6 if ( value < root - > data )
7 root - > left = insert ( root - > left , value ) ;
8 else
9 root - > right = insert ( root - > right , value ) ;
2
10
11 return root ;
12 }
4 Activité 2 : Affichage des Parcours d’un
Arbre
4.1 Parcours Inorder (Gauche - Racine - Droite)
Le parcours Inorder permet d’afficher les valeurs triées dans un BST.
À faire : Implémenter le parcours Inorder.
1 // Fonction pour afficher le parcours Inorder
2 void inorder ( Node * root ) {
3 if ( root == NULL )
4 return ;
5
6 inorder ( root - > left ) ;
7 printf ( " % d " , root - > data ) ;
8 inorder ( root - > right ) ;
9 }
4.2 Parcours Level Order (BFS - Parcours par niveau)
À faire : Implémenter le parcours Level Order.
1 // Fonction pour afficher le parcours Level Order ( BFS )
2 void levelOrder ( Node * root ) {
3 if ( root == NULL )
4 return ;
5
6 Queue * front = NULL , * rear = NULL ;
7 enqueue (& front , & rear , root ) ;
8
9 while ( front != NULL ) {
10 Node * temp = dequeue (& front , & rear ) ;
11 printf ( " % d " , temp - > data ) ;
12
13 if ( temp - > left )
14 enqueue (& front , & rear , temp - > left ) ;
15 if ( temp - > right )
16 enqueue (& front , & rear , temp - > right ) ;
17 }
18 }
3
5 Activité 3 : Expérimentation et Tests
À faire : Insérer ces nombres dans un BST et afficher Inorder et Level
Order.
1 int main () {
2 Node * root = NULL ;
3 int values [] = {1 ,5 ,2 ,6 ,7 ,8 ,20 ,22 ,13 ,4 ,11 ,50};
4 int n = sizeof ( values ) / sizeof ( values [0]) ;
5
6 for ( int i = 0; i < n ; i ++)
7 root = insert ( root , values [ i ]) ;
8
9 printf ( " Parcours Inorder : " ) ;
10 inorder ( root ) ;
11 printf ( " \ n " ) ;
12
13 printf ( " Parcours Level Order : " ) ;
14 levelOrder ( root ) ;
15 printf ( " \ n " ) ;
16
17 return 0;
18 }
6 Conclusion
Ce TP vous a permis de :
• Comprendre la structure et l’utilité des BST.
• Implémenter les fonctions d’insertion et de parcours.
• Tester le fonctionnement sur plusieurs ensembles de nombres.
Exercice Bonus : Ajouter une fonction pour supprimer un nœud
dans le BST.