Durée : 3h Matière : PROG C II
Classe : TI 1.5 TP 8 Enseignant :
Date : Mai 2023 ARBRE BINAIRE DE RECHERCHE Adel DAHMANE
Objectif : implémenter les opérations essentielles d’un ARBRE BINAIRE DE RECHERCHE.
#include<stdio.h>
#include<stdlib.h>
struct noeud
{
int info;
noeud * gauche;
noeud * droit;
};
typedef noeud * arbre;
//Opérations sur un ABR : Arbre Binaire de Recherche
void init(arbre &a);
bool vide(arbre r);
arbre sad(arbre r); //sous-arbre gauche
arbre sag(arbre r); //sous-arbre droit
int racine(arbre r);
void inserer(arbre * r, int elem); //insérer elem dans l'ABR pointé par r
void transfert(arbre * r, int t[], int n); //du tableau t vers l'ABR pointé
par r.
void rgd(arbre r); //parcours préfixé
void grd(arbre r); //parcours infixé
void gdr(arbre r); //parcours postfixé
int max(int a, int b); //sera utilisée dans hauteur
int hauteur(arbre r);
bool degenere(arbre r); //arbre <=> liste simplement chaînée
int min(arbre r); //sera utilisée dans supprimer
arbre recherche(arbre r, int elem);
void supprimer(arbre * r, int elem); //supprimer elem de l'ABR pointé par r
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
void init(arbre * r)
{
*r = NULL;
}
Page 1 sur 4
bool vide(arbre r) { return (r == NULL); }
//Précond: Non vide(r)
int racine (arbre r) { return r->info; }
//Précond: Non vide(r)
arbre sag(arbre r) { return r->gauche; }
//Précond: Non vide(r)
arbre sad(arbre r) { return r->droit; }
//----------------------------------------------------------------
//----------------------------------------------------------------
void inserer(arbre * r, int elem) //insertion dans un ABR
{
//...
}
void transfert(arbre * r, int t[], int n)
{
//...
}
//----------------------------------------------------------------
//----------------------------------------------------------------
void rgd(arbre r) //parcours préfixé
{
//...
}
void grd(arbre r) //parcours infixé
{
//...
}
void gdr(arbre r) //parcours postfixé
{
//...
}
//----------------------------------------------------------------
//----------------------------------------------------------------
int max(int a, int b) { return (a>b)? a : b ; }
int hauteur(arbre r)
{
//...
}
Page 2 sur 4
bool degenere(arbre r) //r <=> liste simplement chaînée
{
//...
}
//----------------------------------------------------------------
//----------------------------------------------------------------
int min(arbre r)
{
//...
}
arbre recherche(arbre r, int elem)
{
//r est un ABR
//...
}
void supprimer(arbre * r, int elem)
{
//...
}
//----------------------------------------------------------------
//----------------------------------------------------------------
int main()
{
arbre r;
//initialisation de r
//...
//création de r à partir d'un tableau t de 9 entiers
int n = 9;
int t[]= {50, 20, 60, 90, 80, 10, 40, 70, 30};
//...
//affichage de r en utilisant les trois parcours
printf("Parcours Prefixe :\n");
//...
printf("Parcours Infixe :\n");
//...
printf("Parcours Postfixe :\n");
//...
printf("\nHauteur de l'arbre :\n");
//...
//insertion de l'élément 75
//...
Page 3 sur 4
printf("Parcours Infixe :\n");
//...
printf("\nHauteur de l'arbre : ");
//...
printf("\nArbre degenere (O/N) : ");
//...
arbre rd = sag(sad(r));
printf("\nSous-arbre degenere (O/N) : ");
//...
}
Page 4 sur 4
