Corrigé du TD 3 : constructeurs et arbres binaires

Ce programme affiche :

Animal::Animal()
Pied::Pied()
Pied::Pied()
Humain::Humain()

Lorsque la liste d'initialisation est vide, l'ordre de construction d'un objet est le suivant :

• appel du constructeur par défaut de chaque classe mère
• appel du constructeur par défaut de chaque donnée membre
• exécution du constructeur de l'objet

Lorsque la liste d'initialisation n'est pas vide, les constructeurs par défaut ne sont pas appelés et leur appel est remplacé par celui indiqué dans la liste d'initialisation. L'exécution du corps du constructeur se fait en dernier dans ce cas également.

Si on supprime le constructeur sans paramètre Animal::Animal(), le programme ne compile plus : le constructeur de la classe Humain comporte un appel implicite au constructeur par défaut de la classe Animal, qui n'existe plus.

Les deux pieds ne peuvent pas être regroupés dans un tableau : il faudrait pour cela que la classe Pied comporte un constructeur par défaut.

#ifndef Noeud_h
#define Noeud_h
 
#include <string>
 
struct Noeud
{
    std::string valeur;
    Noeud *gauche;
    Noeud *droite;
    Noeud(std::string _valeur);
};
 
#endif // Noeud_h

#include "Noeud.h"
 
#include <string>
 
Noeud::Noeud(std::string _valeur)
: valeur(_valeur), gauche(0), droite(0)
{
}

#ifndef Arbre_h
#define Arbre_h
 
#include <string>
#include "Noeud.h"
 
class Arbre
{
public :
    Arbre();
    ~Arbre();
 
    void insererValeur(std::string const & valeur);
    Noeud* trouver(std::string const & valeur) const;
    void afficher() const;
 
private :
    Noeud* tete;
 
    void detruire(Noeud* courant);
    Noeud* trouver(std::string const & valeur,Noeud* courant) const;
    void afficher(Noeud* courant) const;
};
 
#endif // Arbre_h

#include "Arbre.h"
 
#include <iostream>
#include <string>
 
#include "Noeud.h"
 
Arbre::Arbre()
: tete(0)
{
}
 
Arbre::~Arbre()
{
    if(tete!=0)
    {
        detruire(tete);
    }
}
 
void
Arbre::insererValeur(std::string const & valeur)
{
    if(!tete)
    {
        tete=new Noeud(valeur);
    }
    else
    {
        Noeud* lieu=trouver(valeur);
        if(lieu->valeur != valeur)
        {
            Noeud* nouveau=new Noeud(valeur);
            if(valeur < lieu->valeur)
            {
                lieu->gauche=nouveau;
            }
            if(valeur > lieu->valeur)
            {
                lieu->droite=nouveau;
            }
        }
        // sinon la valeur est déjà dans l'arbre, on ne fait rien
    }
}
 
Noeud*
Arbre::trouver(std::string const & valeur) const
{
    return trouver(valeur, tete);
}
 
Noeud*
Arbre::trouver(std::string const & valeur, Noeud* courant) const
{
    if(courant==0)
    {
        // non trouvé
        return 0;
    }
    if(valeur < courant->valeur && courant->gauche != 0)
    {
        return trouver(valeur, courant->gauche);
    }
    else if(valeur > courant->valeur && courant->droite != 0)
    {
        return trouver(valeur, courant->droite);
    }
    else
    {
        // valeur == courant->valeur
        return courant;
    }
}
 
void
Arbre::afficher() const
{
    return afficher(tete);
}
 
void
Arbre::afficher(Noeud *courant) const
{
    if(courant != 0)
    {
        if(courant->gauche != 0)
        {
            afficher(courant->gauche);
        }
        std::cout << courant->valeur << " ";
        if(courant->droite != 0)
        {
            afficher(courant->droite);
        }
    }
}
 
void
Arbre::detruire(Noeud* courant)
{
    if(courant->gauche != 0)
    {
        detruire(courant->gauche);
    }
    if(courant->droite != 0)
    {
        detruire(courant->droite);
    }
    delete courant;
}