TP4 AFGT - Partie Algo - Types Abstraits de Données
TAD Arbre Binaire de Recherche (ABR)
Un Arbre Binaire de Recherche (ABR), est un arbre binaire tel que :
— chaque noeud possède au-plus 2 fils,
— chaque noeud possède une valeur,
— les valeurs des noeuds du sous-arbre gauche sont inférieures ou égales à celle du noeud
père,
— les valeurs des noeuds du sous-arbre droit sont strictement supérieures à celle du
noeud père.
On définit une implantation du TAD ABR de la manière suivante :
Type ABR = ref Noeud ;
Type Noeud = { Info val ;
ABR g, d ;
}
Le code C de cette implantation (avec ses primitives de base) est disponible en annexe et sur
Moodle, dans les fichiers TAD ABR.h, TAD ABR.c et TAD ABR.a pour la compilation.
Pour ce TP, on supposera que le type Info est le type entier.
Le TP est divisé en 3 parties. Il est nécessaire de réaliser la partie 1 avant d’aborder les
parties 2 et 3. Les parties 2 et 3 sont indépendantes. La partie 3 est en bonus.
1ère Partie :
1.1 Écrire une fonction récursive d’ajout d’une valeur aux feuilles dans un arbre binaire de
recherche (en utilisant la fonction creer feuilleABR) : ABR ajout f(Info v, ABR A).
1.2 Écrire une procédure d’affichage (en ligne) des valeurs des noeuds d’un ABR en ordre
préfixe : affiche prefixe(ABR A).
1.3 Écrire une procédure d’affichage (en ligne) des valeurs des noeuds d’un ABR en ordre
infixe : affiche infixe(ABR A).
1.4 Écrire une procédure d’affichage (en ligne) des valeurs des noeuds d’un ABR en ordre
postfixe : affiche postfixe(ABR A).
1.5 Écrire un programme (main) permettant de remplir un ABR en demandant à l’utilisateur
le nombre n de valeurs qu’il souhaite ajouter à l’arbre, et en ajoutant successivement aux
feuilles les n valeurs saisies par l’utilisateur.
1
Tester ce programme avec 3 nœuds à ajouter (de valeurs 10, 20 et 30) en entrant succes-
sivement les valeurs des trois nœuds dans les 6 différents ordres possibles et en affichant à
chaque fois l’ABR obtenu selon les 3 procédures d’affichage.
2ème Partie :
2.1 Écrire une fonction (récursive ou itérative au choix) qui renvoie la plus petite valeur d’un
arbre binaire de recherche :
Info min (ABR A)
PRE : A est supposé non vide.
2.2 Écrire une fonction qui renvoie la plus grande valeur d’un arbre binaire de recherche :
Info max (ABR A)
PRE : A est supposé non vide.
2.3 Un arbre binaire de recherche A est dit de domaine plus petit qu’un autre arbre binaire
de recherche B si et seulement si le plus petit élément de A est supérieur ou égal au plus petit
élément de B et si le plus grand élément de A est inférieur ou égal au plus grand élément de
B.
Écrire une fonction qui teste si un arbre binaire de recherche A est de domaine plus petit
qu’un arbre binaire de recherche B :
booléen dom inclus (ABR A, ABR B)
PRE : A et B sont supposés non vides.
2.4 Écrire une fonction qui calcule et retourne la hauteur d’un arbre binaire de recherche :
entier hauteur (ABR A)
2.5 Écrire un programme (main) permettant de tester les différentes fonctions de cette 2ème
partie (fonctions min, max, dom inclus et hauteur).
3ème Partie (Bonus) :
3.1 Parmi les 3 fonctions d’affichage de la 1ère partie, laquelle vous paraı̂t la plus intéressante,
et pourquoi ?
3.2 En déduire une procédure de tri d’un tableau, basée sur l’utilisation d’ABR.
tri (tableau T, entier nb)
// On pourra définir une fonction intermédiaire si besoin
PRE : T est un tableau de nb entiers non trié, nb ≤ 50
POST : le tableau T a été trié en ordre croissant.
3.3 Écrire un programme (main) permettant de tester cette procédure de tri avec un tableau
de 10 éléments.
2
Annexe : Implantation du TAD ABR
———– Fichier TAD ABR.h
typedef int Info;
typedef struct noeud {
Info val;
struct noeud *g, *d;
} Noeud;
typedef Noeud *ABR;
// creation d’un ABR (retourne un accès à une feuille-racine initialisée)
ABR creer_feuilleABR(Info v);
// teste si un ABR est vide
int est_videABR(ABR abr);
// teste si un ABR est une feuille
int est_feuilleABR(ABR abr);
// rend la valeur de la racine d’un ABR
Info valracABR(ABR abr);
// retourne le fils gauche d’un ABR
ABR gaucheABR(ABR abr);
// retourne le fils droit d’un ABR
ABR droitABR(ABR abr);
// libère la mémoire allouée à un ABR
void detruireABR(ABR abr);
———– Fichier TAD ABR.c
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "TAD_ABR.h"
ABR creer_feuilleABR(Info v)
{
ABR abr = (ABR)malloc(sizeof(Noeud));
abr->val = v;
3
abr->g = NULL;
abr->d = NULL;
return abr;
}
int est_videABR(ABR abr)
{ return (abr == NULL); }
int est_feuilleABR(ABR abr)
{
assert(!(abr==NULL)); /* l’arbre ne doit pas e
^tre vide */
return (est_videABR(abr->g) && est_videABR(abr->d));
}
Info valracABR(ABR abr)
{
assert(!(abr==NULL)); /* l’arbre ne doit pas e
^tre vide */
return (abr->val);
}
ABR gaucheABR(ABR abr)
{
assert(!(abr==NULL)); /* l’arbre ne doit pas e
^tre vide */
return abr->g;
}
ABR droitABR(ABR abr)
{
assert(!(abr==NULL)); /* l’arbre ne doit pas e
^tre vide */
return abr->d;
}
void detruireABR(ABR abr)
{
if (abr!=NULL) {
detruireABR(abr->g);
detruireABR(abr->d);
free(abr);
}
}
