TP5 - Arbres binaires de recherche

Durée : 1h30

Inès de Courchelle, Elisabeth Ranisavljevic

Objectifs :

  • Connaître les arbres binaires
  • Utiliser des algos spécifiques
  • Comprendre les mécaniques de parcours d’un arbre binaire

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

  • Compile sans warning
  • Obtient les résultats attendus
  • Avant de coder, il faut écrire un algo avec un papier et un stylo !

    logo

Exercice 1 : La préparation

  1. Créer les fichiers suivants :
  • ABR.h
  • ABR.c
  • main.c
  1. Créer le squelette du programme

ABR.h

#ifndef ABR_H
#define ABR_H

/* Le prototype/signature de toutes mes fonctions/procédures */

#endif

ABR.c

#include <stdio.h>
#include <stdlib.h>
#include "ABR.h"

/* corps des différentes fonctions/procédures */

main.c

#include <stdio.h>
#include <stdlib.h>
#include "ABR.h"

int main(){
    printf("C'est l'arbre !");
    return 0;
}



Exercice 2 : Les basiques

  1. Déclarer une structure d’un noeud puis d’un arbre binaire. (c’est la même structure que le TP précédent !)
  2. Coder la fonction pour créer un arbre binaire de recherche (c’est la même structure que le TP précédent !)
/* Auteur :  */
/* Date :  */
/* Résumé : créer un arbre binaire */
/* Entrée(s) : la racine que l'on veut incérer ainsi que son fils gauche et droit */
/* Sortie(s) : l'arbre créé  */
arbre creerArbreBinaire (int val, arbre filsG, arbre filsD);
  1. Coder la fonction d’affichage de parcours infixe (c’est la même structure que le TP précédent !)
/* Auteur :  */
/* Date :  */
/* Résumé : Met l'affichage en forme  d'un arbre via le parcours infixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void parcoursInfixe(arbre a);

/* Auteur :  */
/* Date :  */
/* Résumé : affiche un arbre via le parcours infixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void afficherInfixe(arbre a);
  1. Coder l’ensemble des fonctionnalités suivantes :

/* Auteur : */
/* Date :   */
/* Résumé : Insertion dans un arbre binaire de recherche */
/* Entrée(s) : la valeur et l'arbre dans lequel on souhaite  insérer la valeur*/
/* Sortie(s) : le nouvel arbre */
arbre insertionArbre(int val, arbre a);


/* Auteur : */
/* Date :   */
/* Résumé : Recherche un élement dans un arbre binaire de recherche */
/* Entrée(s) : la valeur et l'arbre dans lequel on souhaite rechercher la valeur*/
/* Sortie(s) : l'arbre dont la racine est la valeur recherchée */
arbre rechercheArbre(int val, arbre a);


/* Auteur : */
/* Date :  */
/* Résumé : Suppresion d'un élement dans un arbre binaire de recherche */
/* Entrée(s) : la valeur et l'arbre dans lequel on souhaite supprimer la valeur*/
/* Sortie(s) : l'arbre avec la valeur en moins */
arbre supprArbre(int val, arbre a);

/* Auteur : */
/* Date :  */
/* Résumé : Récupére l'élement le plus petit dans un arbre binaire de recherche */
/* Entrée(s) : l'arbre dans lequel on souhaite rechecher la valeur la plus petite*/
/* Sortie(s) : la valeur la plus petite*/
int minArbre(arbre a);

/* Auteur : */
/* Date :  */
/* Résumé : Récupére l'élement le plus grand dans un arbre binaire de recherche */
/* Entrée(s) : l'arbre dans lequel on souhaite rechecher la valeur la plus grande */
/* Sortie(s) : la valeur la plus grande*/
int maxArbre(arbre a);


/* Auteur : */
/* Date :   */
/* Résumé : supprime l'élement le plus grand dans un arbre binaire de recherche */
/* Entrée(s) : l'arbre dans lequel on souhaite supprimer la valeur la plus grande */
/* Sortie(s) : l'arbre avec la valeur en moins */
arbre supprMax(arbre a);


/* Auteur : */
/* Date :  */
/* Résumé : Réalise l'intersection de 2 arbres passés en paramètres et renvoie le résultat dans un 3ieme arbre  */
/* Entrée(s) :  3 arbres*/
/* Sortie(s) :  1 arbre*/
arbre intersection(arbre a1, arbre a2, arbre a3);





/* Auteur : */
/* Date :  */
/* Résumé : Créer un arbre binaire de recherche aléatoire. On lui passe le nombre de noeuds en paramètres */
/* Entrée(s) : entier, arbre */
/* Sortie(s) : arbre */
arbre aleatoireArbre(int nbNoeuds, arbre a);


/* Auteur : */
/* Date :  */
/* Résumé : prédicat permettant de savoir si un arbre est binaire ou non */
/* Entrée(s) :  arbre */
/* Sortie(s) : entier */
int estBinaire(arbre a);