Extrait du support de cours sur arbre binaire de recherche (ABR)
Definition ABR
-Un arbre binaire de recherche (ABR) est un arbre binaire construit sur des elements qui possèdent une cle dentification et tel que pour tout nàud sa cle est :
- superieure a toutes celles de ses descendants de gauche et
- inferieure a toutes celles de ses descendants de droite.
Consequence
- Les proprie te s e nonce es sur les arbres binaires de recherche permettent de de duire que la liste infixe (GRD) d’un tel arbre correspond a la liste ordonne e par cle croissante
- Tous les arbres de recherche contenant les memes e le ments donnent le meme parcours infixe
Imple mentation
- On va utiliser la fonction element Comparer qui retourne 0, < 0 ou > 0
- La de finition dàun ABR est identique acelle d’un AB
- Avec les ABR on peut inse rer et supprimer des elements contrairement au AB classiques ce qui explique que le TDA ARBINR contient les
- deux primitives inserer et supprimer
Primitives du TDA ABR
/*****************************************************************
* Fichier : ARBRPRIM.H
* Contenu : De claration des primitives du TDA ARBINR
/****************************************************************/
#ifndef _ARBRPRIM_H
#define _ARBRPRIM_H
#include <stdio.h>
#include <stdlib.h>
#include « ARBRSDD.H »
ARBINR arbinRCreer(void);
void arbinRDetruire(ARBINR);
int arbinRVide(ARBINR);
int arbinRSature(ARBINR);
int arbinRTaille(ARBINR);
int inserer(ARBINR, ELEMENT);
int supprimer(ARBINR, ELEMENT);
int appartient(ARBINR, ELEMENT);
void arbinRAfficher(ARBINR , int );
#endif
Imple mentation:Appartient
int appartient(ARBINR a, ELEMENT e) {
int test=0;
NOEUD p;
if (!arbinRVide(a))
{
p=a->refRacine;
while ((p !=NULL) && (! test))
{
if ((elementComparer(e,p->info))<0)
p=p->fg;
else
}
}
return test;
}
{
if ((elementComparer(e,p->info))>0)
p=p->fd;
else
test=1;
}
Insertion dans un ARB version ite rative
int inserer(ARBINRa, ELEMENT e){
int succee=1;
NOEUD n, p, q;
if (arbinRSature(a))
{ // 1
printf (« \nArbre sature « );
succee=0;}
else {
if (appartient(a,e))
{
}
else
{ // 2
printf (« \nElement existant »);
succee=0;
n=noeudCreer (e, NULL, NULL);
if (arbinRVide(a))
a->refRacine=n;
……
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Support de cours sur arbre binaire de recherche (ABR) (888 KO) (Cours PDF)
