BONJOUR
NOUS SOMMES HEUREUX DE VOUS PRÉSENTER NOTRE
TRAVAIL
UNIVERSITE DE BERTOUA UNIVERSITY OF BERTOUA
************* ************
ECOLE NORMALE SUPERIEURE DE HIGHER TEACHER TRAINING
BERTOUA COLLEGE BERTOUA
************** **************
BOITE POSTALE 652 BERTOUA [Link] 652 BERTOUA
************** *************
DEPARTEMENT D’INFORMATIQUE DEPARTMENT OF COMPUTER
************** SCIENCES
FILIERE : TIC-FONDA **************
OPTION: ICT-FONDA
THEME : LES ARBRES BINAIRES DE RECHERCHE
Sous la supervision : Année académique : 2022/2023
M. EMINI ME ZENANGA AMSTRONG
Rédigé et présenté par :
HASSAN BARKINDO
KEYA ZANGA ELYSEE
GASISSO GILBERT
MANOUERE MAIMOUNA
KOUMGANG MOÏSE DANIEL
NONO JEAN MARC
ZOGO NGA ABDON
INTRODUCTION
Le langage « C » est un langage impératif, normalisé, sa syntaxe très souple permet l’écriture des programmes
corrects du point de vue du langage. Nous aborderons ce langage au travers d’exemples de programmes
commentés sur les ARBRES BINAIRES DE RECHERCRES (ABR) plus précisément sur l’insertion d’un nœud, la
suppression d’un nœud et la recherche d’un élément dans un ABR. Un arbre binaire de recherche fait partie des
arbres les plus simples et nous allons l’illustrer. Ses éléments (ou nœuds) ne contiendront qu'une valeur de type
entier. C'est cette valeur qui nous servira à ordonner les éléments. Nous l'appellerons donc la clé (key).
Tout comme les listes chaînées, les arbres sont basés sur une structure du langage C. La différence sera qu'elle
contiendra deux pointeurs pour lier les éléments, un pointeur pour accéder à la branche de gauche et l'autre pour
accéder à la branche de droite. Nous avons maintenant suffisamment d'éléments pour constituer la structure d'un
nœud :
I- INSERTION DANS UN ARBRE BINAIRE DE RECHERCHE
1. Description
La deuxième étape est de trier les éléments à leur insertion dans l'arbre. Le tri sera effectué sur la
valeur de la clé (key). Le premier élément est inséré à la racine de l'arbre, l'élément suivant est inséré à
gauche si la valeur de sa clé est inférieure à celle de la racine et à droite si la valeur de sa clé est supérieure
à celle de la racine (on aurait pu faire l'inverse). Pour les éléments qui suivent, c'est le même principe
jusqu'à trouver un emplacement libre au bout d'une branche.
Par exemple, si on avait inséré des éléments ayant comme clé : 10, 20, 4, 8, 5, 15, 3 dans cet ordre, on
aurait un arbre équivalent au schéma suivant :
La première chose que l'on peut faire, c'est donc d'insérer des éléments. Pour cela, nous allons créer la
fonction addNode. Son rôle est de créer l'élément à l'aide de la fonction malloc, d'initialiser ses champs : la
clé avec la valeur désirée (passé en paramètre à la fonction), d'initialiser les deux pointeurs à NULL (ils
seront positionnés au bout d'une branche et n'ont donc pas d'enfants) et de les insérer dans l'arbre en
tenant compte des critères de tri. Donc si l'élément n'est pas le premier, on boucle (boucle do…while) afin
d'avancer de nœud en nœud jusqu'à atteindre un emplacement libre (pointeur à NULL) et à chaque nœud
on part à droite, si la clé est supérieure à celle du nœud courant, ou à gauche si elle est inférieure ou égale
à celle du nœud courant.
Le cas du premier élément (racine de l'arbre) impose d'affecter l'adresse de cet élément au pointeur sur
l'arbre que l'on a passé en paramètre à la fonction. Il s'impose donc que ce paramètre soit un pointeur de
pointeur, afin de passer l'adresse du pointeur sur l'arbre à la fonction. Fonction que l'on appellera donc de
la façon suivante :
2. Programme
II. SUPPRESSION DANS UN ARBRE BINAIRE DE RECHERCHE
1. Description
Nous avons alloué de la mémoire avec malloc, il faut donc la libérer. Là aussi, il faut parcourir
l'arbre complet, nous utiliserons donc le même principe que pour les fonctions d'affichage.
2. Programme
III. RECHERCHE DANS UN ARBRE BINAIRE DE RECHERCHE
1. Description
Nous avons dit que notre arbre est un arbre de recherche. C'est donc la deuxième fonction que nous allons
créer. Elle devra nous indiquer si un élément avec une clé de valeur x est présent dans l'arbre. Le principe est
identique à la fonction d'insertion. On suit le cheminement en partant à droite ou à gauche selon la valeur de la
clé. À chaque nœud on vérifie si on est en présence de l'élément recherché, si oui on retourne la valeur 1.
Quand on arrive au bout de la branche si on ne l'a pas trouvé on retourne 0. On est certain qu'il ne se trouve
pas dans une autre branche, il n'y a donc pas besoin de tester.
2. Programme
IV. PROGRAMME GENERAL IMPLEMENTANT L’INSERTION, LA
RECHERCHE, ET LA SUPPRESSION DANS UN ARBRE BINAIRE DE
RECHERCHE
Résultat après compilation
CONCLUSION
En somme un arbre binaire de recherche est bien adapté pour la
recherche d'élément, l'insertion et la recherche ne nécessitant pas de parcourir
l'arbre en entier. Il peut aussi faire du tri, vous l'avez vu avec les fonctions
d'affichage. Il est même assez performant si les valeurs des clés des éléments
insérés sont aléatoires. Par contre, il devient très mauvais dans le cas
d'insertion d'éléments déjà triés ou partiellement triés. Dans ce cas au lieu de
faire plusieurs branches il pourrait en faire une seule, très grande dans le pire
des cas (ce qui reviendrait à unelistechaînée).
MERCI POUR VOTRE ATTENTION
