TP4 - Généralités sur les arbres

Durée : 1h30

Inès de Courchelle, Elisabeth Ranisavljevic

Objectifs :

Connaître les propriétés d’un arbre
Assimiler le vocabulaire sur les arbres
Étudier les parcours d’un arbre
Appréhender les arbres binaires

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 !

Exercice 1 : La préparation

Créer les fichiers suivants :

arbre.h
arbre.c
main.c

Créer le squelette du programme

arbre.h

#ifndef ARBRE_H
#define ARBRE_H

/* RAPPEL */
typedef struct noeud {
  int val;
  struct noeud* filsG;
  struct noeud* filsD;
}noeud;

typedef noeud* arbre;

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

#endif

arbre.c

#include "arbre.h"
/* corps des différentes fonctions/procédures */

main.c

#include <stdio.h>
#include "arbre.h"

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

Exercice 2 : Les basiques

Déclarer une structure d’un noeud puis d’un arbre
Coder la fonction pour créer un arbre binaire :

/* 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);

Astuce : Comment créer les arbres binaires suivant ?

Arbre 1

Nous allons le créer dans la fonction main
Nous allons faire appel à la fonction creerArbreBinaire

#include <stdio.h>
#include "arbre.h"

int main(){
  arbre monArbre = NULL;
  monArbre creerArbreBinaire(42,NULL,NULL);
  return 0;
}

Arbre 2

Nous allons le créer dans la fonction main
Nous allons faire appel à la fonction creerArbreBinaire

#include <stdio.h>
#include "arbre.h"

int main(){
  arbre monArbre = NULL;
  monArbre creerArbreBinaire(42,creerArbreBinaire(24,NULL,NULL),NULL);
  return 0;
}

Arbre 3

Nous allons le créer dans la fonction main
Nous allons faire appel à la fonction creerArbreBinaire

#include <stdio.h>
#include "arbre.h"

int main(){
    arbre monArbre = NULL;
    monArbre creerArbreBinaire(42,
                                 creerArbreBinaire(24,NULL,NULL),
                                 creerArbreBinaire(53,
                                              creerArbreBinaire(21,NULL,NULL),
                                              creerArbreBinaire(55,NULL,NULL)
                                              )
                             );
  return 0;
}

Coder les fonctions suivantes :

/* Auteur :  */
/* Date :  */
/* Résumé : donne la taille d'un arbre */
/* Entrée(s) : arbre */
/* Sortie(s) : cpt */
int taille(arbre a);

/* Auteur :  */
/* Date :  */
/* Résumé : indique si un noeud est une feuille */
/* Entrée(s) : arbre  */
/* Sortie(s) : vrai ou faux */
int estFeuille(arbre a);

/* Auteur :  */
/* Date :  */
/* Résumé : donne la hauteur d'un arbre */
/* Entrée(s) : arbre  */
/* Sortie(s) : entier */
int hauteur(arbre a);


/* Auteur :  */
/* Date :  */
/* Résumé : donne le nombre de feuille d'un arbre */
/* Entrée(s) : arbre, cpt */
/* Sortie(s) : cpt */
int nbFeuilles(arbre a);

Exercice 3 : Les affichages

Coder les procédures d’affichage suivantes :

/* 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);


/* Auteur :  */
/* Date :  */
/* Résumé : affiche un arbre via le parcours Postfixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void afficherPostfixe(arbre a);

/* Auteur :  */
/* Date :  */
/* Résumé : Met l'affichage en forme  d'un arbre via le parcours Postfixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void parcoursPostfixe(arbre a);


/* Auteur :  */
/* Date :  */
/* Résumé : Met l'affichage en forme  d'un arbre via le parcours prefixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void parcoursPrefixe(arbre a);


/* Auteur :  */
/* Date :  */
/* Résumé : affiche un arbre via le parcours Prefixe */
/* Entrée(s) : l'arbre que l'on souhaite afficher */
/* Sortie(s) : none */
void afficherPrefixe(arbre a);