Etablissement Inter – Etats d’Enseignement Supérieur
CENTRE D’EXCELLENCE TECHNOLOGIQUE PAUL BIYA
BP : 13719 Yaoundé (Cameroun) Tel. (+237) 242 72 99 57/ (+237) 242 72 99 58
Site web : www.iaicameroun.com E-mail :
[email protected] THEME : LES ARBRES EN C
Membres du groupe :
❖ NGO MANDENG IRENE
❖ NGANDO JASON
❖ NDJOUPE JEHOH
❖ NYANSE
❖ KAMBENG
❖ ABENA
❖ NSALLE
❖ NGUEWA
❖ MOUNCHILLI
❖ JOGO
❖ TCHANGOU
❖ TCHANKOU
❖ FOUEJIO
Sous l’encadrement de : Année académique
2024/2025
M. AVINA MANY ALBERT
1
Table des matières
INTRODUCTION ...................................................................................................................................... 3
I. DEFINITION ..................................................................................................................................... 3
1. LES CARACTERISTIQUES DES ARBRES EN C .................................................................................... 3
II. LES TYPES D’ARBRES EN C ............................................................................................................... 4
III. Opération sur les arbres en C ................................................................................................... 11
IV. IMPLEMENTATION D’ARBRE BINAIRE EN LANGAGE C ................................................................... 14
a) CODE DU PROGRAMME D’UN ARBRE BINAIRE ............................................................................. 14
V. EXEMPLE D’APPLICATION .............................................................................................................. 17
2
INTRODUCTION
Les arbres sont des structures de données fondamentales en informatique permettant de
représenter des hiérarchies et des relations entre des éléments. En langage C, la manipulation
des arbres nécessite une bonne compréhension de leur structure et des opérations associées.
I. DEFINITION
Un arbre est une structure de données composée de nœud ou chaque nœud contient une
valeur et des références vers ses enfants. Les arbres peuvent être utilisées pour représenter
divers types de données et sont essentiels dans de nombreux algorithmes.
1. LES CARACTERISTIQUES DES ARBRES EN C
• Nœud : un élément de l’arbre qui contient une valeur et des pointeurs vers ses enfants.
3
• Racine : le nœud supérieur de l’arbre
• Feuille : un nœud sans enfant
• Hauteur : la longueur du chemin le plus long depuis la racine jusqu’à une feuille
II. LES TYPES D’ARBRES EN C
1. Les arbres binaires en C
Un arbre binaire est un type d’arbre ou chaque nœud a ou plus deux enfants
a) Version itérative
L’implémentation itérative utilise des structures de contrôle comme des boucles pour
parcourir des arbres.
Exemples :
• Parcours en largeur (BFS) : Utilise une file pour explorer les nœuds niveau par niveau.
Implémentation :
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
// Définition de la structure Node
typedef struct Node {
int value; // Valeur du nœud
struct Node* left; // Pointeur vers le fils gauche
struct Node* right; // Pointeur vers le fils droit
} Node;
4
// Fonction BFS
void bfs(Node* root) {
if (root == NULL) return;
Node* queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
Node* current = queue[front++];
printf("%d ", current->value);
// Vérification pour éviter le dépassement de la file
if (current->left) {
if (rear < MAX_QUEUE_SIZE) {
queue[rear++] = current->left;
} else {
printf("Erreur : File pleine, impossible d'ajouter le fils gauche.\n");
}
}
if (current->right) {
if (rear < MAX_QUEUE_SIZE) {
queue[rear++] = current->right;
} else {
printf("Erreur : File pleine, impossible d'ajouter le fils droit.\n");
}
}
}
}
// Fonction pour créer un nouveau nœud
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
5
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
// Création d'un arbre binaire
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// Appel de la fonction BFS
printf("Parcours BFS de l'arbre : ");
bfs(root);
printf("\n");
// Libération de la mémoire (ajoutez une fonction si nécessaire)
return 0;
}
b) Version récursive
L’implémentation récursive utile des appels de fonction pour parcourir l’arbre
Exemples :
• Parcours prefixe
Implémentation :
6
#include <stdio.h>
#include <stdlib.h>
// Définition de la structure Node
typedef struct Node {
int value; // Valeur du nœud
struct Node* left; // Pointeur vers le fils gauche
struct Node* right; // Pointeur vers le fils droit
} Node;
// Fonction de parcours préfixe (preorder)
void preorder(Node* node) {
if (node != NULL) {
printf("%d ", node->value);
preorder(node->left);
preorder(node->right);
}
}
// Fonction pour créer un nouveau nœud
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
// Création d'un arbre binaire
7
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// Appel de la fonction preorder
printf("Parcours préfixe de l'arbre : ");
preorder(root);
printf("\n");
// Libération de la mémoire (ajoutez une fonction si nécessaire)
return 0;
}
• Parcours infixe
Implémentation :
#include <stdio.h>
#include <stdlib.h>
// Définition de la structure Node
typedef struct Node {
Int value; // Valeur du nœud
struct Node* left; // Pointeur vers le fils gauche
struct Node* right; // Pointeur vers le fils droit
} Node;
8
// Fonction de parcours infixe (inorder)
void inorder(Node* node) {
if (node != NULL) {
inorder(node->left);
printf("%d ", node->value);
inorder(node->right);
}
}
// Fonction pour créer un nouveau nœud
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
// Création d'un arbre binaire
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// Appel de la fonction inorder
9
printf("Parcours infixe de l'arbre : ");
inorder(root);
printf("\n");
// Libération de la mémoire (ajoutez une fonction si nécessaire)
return 0;
}
2. Les arbres binaires de recherche
a) Définition
Un arbre binaire de recherche est un arbre binaire ou pour chaque nœud :
• Les valeurs du sous-arbre gauche sont inférieurs à celle du nœud.
• Les valeurs du sous-arbre droit sont inférieures.
3. Caractéristiques des arbres binaires
➢ Taille (nombre total de nœuds)
➢ Hauteur (longueur du chemin le plus long de la racine à une feuille)
➢ Profondeur d’un nœud
➢ Feuille (nœud sans enfant)
10
III. Opération sur les arbres en C
1. INSERTION
a) Pseudo code
Node* inserer(Node* noeud, int valeur) {
if (noeud == NULL) {
Node* nouveauNoeud = (Node*)malloc(sizeof(Node));
nouveauNoeud->valeur = valeur;
nouveauNoeud->gauche = NULL;
nouveauNoeud->droite = NULL;
return nouveauNoeud;
if (valeur < noeud->valeur) {
noeud->gauche = inserer(noeud->gauche, valeur);
} else {
noeud->droite = inserer(noeud->droite, valeur);
return noeud;
2. SUPPRESSION
11
a) Pseudo code
Node* supprimer(Node* noeud, int valeur) {
if (noeud == NULL) {
return noeud;
if (valeur < noeud->valeur) {
noeud->gauche = supprimer(noeud->gauche, valeur);
} else if (valeur > noeud->valeur) {
noeud->droite = supprimer(noeud->droite, valeur);
} else {
if (noeud->gauche == NULL) {
return noeud->droite;
} else if (noeud->droite == NULL) {
return noeud->gauche;
Node* temp = noeudValeurMinimale(noeud->droite);
noeud->valeur = temp->valeur;
noeud->droite = supprimer(noeud->droite, temp->valeur);
return noeud;
3. RECHERCHE
12
a) Pseudo code
Node* rechercher(Node* noeud, int valeur) {
if (noeud == NULL || noeud->valeur == valeur) {
return noeud;
if (valeur < noeud->valeur) {
return rechercher(noeud->gauche, valeur);
return rechercher(noeud->droite, valeur);
4. PARCOURS D’UN ARBRE BINAIRE
a) Pseudo code
void parcoursInfixe(Node* noeud) {
if (noeud != NULL) {
parcoursInfixe(noeud->gauche);
printf("%d\n", noeud->valeur);
parcoursInfixe(noeud->droite);
13
IV. IMPLEMENTATION D’ARBRE BINAIRE EN LANGAGE C
a) CODE DU PROGRAMME D’UN ARBRE BINAIRE
#include <stdio.h>
#include <stdlib.h>
// Définition de la structure Node
typedef struct Node {
int valeur; // Valeur du nœud
struct Node* gauche; // Pointeur vers le fils gauche
struct Node* droite; // Pointeur vers le fils droit
} Node;
// Fonction pour créer un nouveau nœud
Node* creerNoeud(int valeur) {
Node* nouveauNoeud = (Node*)malloc(sizeof(Node));
nouveauNoeud->valeur = valeur;
nouveauNoeud->gauche = NULL;
nouveauNoeud->droite = NULL;
return nouveauNoeud;
14
// Fonction pour insérer un nœud dans l'arbre
Node* inserer(Node* noeud, int valeur) {
if (noeud == NULL) {
return creerNoeud(valeur);
if (valeur < noeud->valeur) {
noeud->gauche = inserer(noeud->gauche, valeur);
} else {
noeud->droite = inserer(noeud->droite, valeur);
return noeud;
// Fonction pour chercher une valeur dans l'arbre
Node* chercher(Node* noeud, int valeur) {
if (noeud == NULL || noeud->valeur == valeur) {
return noeud;
if (valeur < noeud->valeur) {
return chercher(noeud->gauche, valeur);
return chercher(noeud->droite, valeur);
15
// Fonction pour effectuer un parcours infixe
void parcoursInfixe(Node* noeud) {
if (noeud != NULL) {
parcoursInfixe(noeud->gauche);
printf("%d\n", noeud->valeur);
parcoursInfixe(noeud->droite);
// Fonction principale
int main() {
Node* racine = NULL;
// Insertion de valeurs dans l'arbre
racine = inserer(racine, 50);
inserer(racine, 30);
inserer(racine, 70);
inserer(racine, 20);
inserer(racine, 40);
inserer(racine, 60);
inserer(racine, 80);
// Affichage des valeurs de l'arbre en ordre
16
printf("Parcours infixe de l'arbre :\n");
parcoursInfixe(racine);
// Recherche d'une valeur
int valeur = 40;
Node* resultat = chercher(racine, valeur);
if (resultat != NULL) {
printf("Valeur %d trouvée dans l'arbre.\n", valeur);
} else {
printf("Valeur %d non trouvée dans l'arbre.\n", valeur);
// Libération de la mémoire (à implémenter si nécessaire)
return 0;
V. EXEMPLE D’APPLICATION
#include <stdio.h>
#include <stdlib.h>
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droit;
17
} Noeud;
Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
Noeud* nouveau = malloc(sizeof(Noeud));
nouveau->valeur = valeur;
nouveau->gauche = nouveau->droit = NULL;
return nouveau;
if (valeur < racine->valeur)
racine->gauche = inserert(racine->gauche, valeur);
else
racine->droit = inserert(racine->droit, valeur);
return racine;
void parcoursPreordre(Noeud* racine) {
if (racine == NULL) return;
printf("%d ", racine->valeur); // Visiter la racine
parcoursPreordre(racine->gauche); // Visiter le sous-arbre gauche
parcoursPreordre(racine->droit); // Visiter le sous-arbre droit
void parcoursEnOrdre(Noeud* racine) {
if (racine == NULL) return;
parcoursEnOrdre(racine->gauche); // Visiter le sous-arbre gauche
printf("%d ", racine->valeur); // Visiter la racine
parcoursEnOrdre(racine->droit); // Visiter le sous-arbre droit
void parcoursPostordre(Noeud* racine) {
if (racine == NULL) return;
parcoursPostordre(racine->gauche); // Visiter le sous-arbre gauche
parcoursPostordre(racine->droit); // Visiter le sous-arbre droit
18
printf("%d ", racine->valeur); // Visiter la racine
#include <stdbool.h>
typedef struct Pile {
Noeud** elements;
int sommet;
int capacite;
} Pile;
Pile* creerPile(int capacite) {
Pile* pile = malloc(sizeof(Pile));
pile->elements = malloc(capacite * sizeof(Noeud*));
pile->sommet = -1;
pile->capacite = capacite;
return pile;
bool estVide(Pile* pile) {
return pile->sommet == -1;
void empiler(Pile* pile, Noeud* noeud) {
pile->elements[++(pile->sommet)] = noeud;
Noeud* depiler(Pile* pile) {
return pile->elements[(pile->sommet)--];
void parcoursPreordreIteratif(Noeud* racine) {
19
if (racine == NULL) return;
Pile* pile = creerPile (100); // Capacité� de la pile
Empiler (pile, racine);
while (!estVide(pile)) {
Noeud* courant = depiler(pile);
printf("%d ", courant->valeur);
if (courant->droit != NULL) empiler(pile, courant->droit);
if (courant->gauche != NULL) empiler(pile, courant->gauche);
free(pile->elements);
free(pile);
int main() {
Noeud* racine = NULL;
// Insertion des valeurs dans l'arbre
racine = inserer(racine, 5);
inserer(racine, 3);
inserer(racine, 7);
inserer(racine, 2);
inserer(racine, 4);
printf("Parcours pr�fixe recursif : ");
parcoursPreordre(racine);
printf("\n");
20
printf("Parcours en ordre recursif : ");
parcoursEnOrdre(racine);
printf("\n");
printf("Parcours postfixe recursif : ");
parcoursPostordre(racine);
printf("\n");
printf("Parcours prefixe iteratif : ");
parcoursPreordreIteratif(racine);
printf("\n");
return 0;
21
CONCLUSION
Les arbres sont des structures puissantes et polyvalente, essentielles pour gérer des données
complexes. Le langage C permet une implémentation fine et efficace, tout en nécessitant une bonne
maîtrise des pointeurs. Savoir travailler sur les arbres améliore la compréhension algorithmique et
prépare à des concepts plus avancés comme les arbres AVL, rouge-noir ou, ou les arbres B
22
