Test de C++ n° 5 et Arbres : (6 mai 2000 – durée : 2h)

© D. Mathieu    mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique
Créé le 06/05/2000 - Dernière mise à jour : 06/05/2000

Tout document autorisé

Sommaire

Question de cours 1
Question de cours 2
Question de cours 3
Question de cours 4
Question de cours 5
Affichage d'arbre binaire
Fonction ForEach() de la classe CTree utilisant un functor générique
Fonctions membres min() et max() de la classe CTree

Question de cours 1

    (1,5 points) - L'arbre ci-dessous (figure 1) est-il :
 
  • un arbre binaire ? (Oui, Non, Je ne sais pas)
  • un arbre de recherche ? (Oui, Non, Je ne sais pas)
  • un maximier ? (Oui, Non, Je ne sais pas)
    figure 1

Corrigé

Sommaire

Question de cours 2

    (1 point) - Mettre sous forme graphique l'arbre parfait stocké sous la forme du vecteur suivant (figure 2) :
14
8
19
3
11
16
24
1
7
10

figure 2

Corrigé

Sommaire

Question de cours 3

    (1 point) - Mettre sous forme graphique l'arbre stocké sous la forme du vecteur suivant (figure 3) :
14
8
19
3
  
11
24
  
7
      
10
  
16

figure 3

Corrigé

Sommaire

Question de cours 4

    (3 points) - Soit le maximier stocké sous la forme du vecteur suivant (figure 4) :
30
10
7
4
8
2
      

figure 4

    Que devient ce vecteur après chacun des ajouts successifs des valeurs 11, 6, 40, introduites dans cet ordre (donner le vecteur après chaque ajout).

Corrigé

Sommaire

Question de cours 5

    (3,5 points) - Soit le maximier stocké sous la forme du vecteur suivant (figure 5) :
30
10
7
4
8
2

figure 5

    Que devient ce vecteur après chacune des suppressions successives de 3 valeurs (donner le vecteur après chaque suppression) ? Quelles sont ces trois valeurs ?

Corrigé

Sommaire

Affichage d'arbre binaire

    (2 points) - Que donnent les affichage de l'arbre suivant (figure 6) parcouru en largeur, et en profondeur dans l'ordre préfixé, infixé, postfixé.

figure 6

Corrigé

Sommaire

Fonction ForEach() de la classe CTree utilisant un functor générique

    (6 points) - L'objectif de cet exercice est de doter la classe CTree écrite au TP 11 de la fonction ForEach(), utilisant un functor générique, qui permet d'appliquer un traitement particulier à chaque nœud d'un arbre (ici arbre de recherche).
Il faut tout d'abord rappeler qu'un arbre de recherche se parcourt toujours (en principe) dans l'ordre croissant des éléments, c'est-à-dire dans l'ordre infixé. Il faut aussi remarquer que le couple de fonctions CTree::Dump() et CNoeudT::Editer() est un cas particulier de la fonction ForEach(), dans laquelle le traitement consisterait en une édition. Il s'ensuit que la fonction ForEach() demandée est une généralisation de ces deux fonctions. La classe CTree doit donc disposer d'une fonction non récursive ForEach() qui appelle elle-même une fonction récursive de la classe CNoeudT, qu'on peut aussi appeler CNoeudT::ForEach() à partir de la racine.

    Indiquer les ajouts à faire dans le fichiers CTree.h (annexe). Ajouter les corps correspondants dans le fichier CTree.hxx.

Corrigé

Sommaire

Fonctions membres min() et max() de la classe CTree

    (2 points + 2 points de bonus si solution élégante) - Ajouter à la classe CTree les fonctions membres min() et max() qui renvoient les valeurs minimale et maximale de l'arbre. On supposera que l'arbre est non vide.

Corrigé

Sommaire

 Annexe

/**
 *
 * @File : CTree.h
 *
 **/
#if !defined __CTREE_H__
#define      __CTREE_H__

#include <vector>

#include "CLinkDouble.h"
#include "CDumpable.h"

namespace nsSdD
{
    template <class T>
    class CTree : virtual public CDumpable
    {
        class CNoeudT : public CLinkDouble, public T
        {
          public :
            CNoeudT (const T & Info = T (),
                     CNoeudT * const Gauche = 0, CNoeudT * const Droit = 0);

            CNoeudT * GetGauche (void) const;
            CNoeudT * GetDroit  (void) const;

            void SetGauche  (CNoeudT * const Ptr);
            void SetDroit   (CNoeudT * const Ptr);

            CNoeudT * Insert (const T & Info);
            void Editer (ostream & os) const;

        }; // CNoeudT

        CNoeudT <T> * m_Racine;

      public :
        CTree  (void);
        ~CTree (void);

        void Insert (const T & Info);

      protected :
        virtual ostream & Dump (ostream & os) const;
        void DetruireNoeud (CNoeudT * const Ptr);

    }; // CTree

} // nsSdD

#include "CTree.hxx"

#endif // __CTREE_H__

Sommaire

© D. Mathieu    mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique