TD 3 : constructeurs et arbres binaires

La mauvaise initialisation des données est une des principales sources d'erreurs dans beaucoup de langages de programmation (tel que le C). C'est pour cela que la POO introduit la notion de constructeur. Considérez le programme suivant :

#include <iostream>
#include <string>
 
struct Animal
{
    float poids;
    Animal()
    {
        std::cout << "Animal::Animal()n";
    }
 
    Animal(int _poids) : poids(_poids)
    {
        std::cout << "Animal::Animal(int)n";
    }
};
 
struct Pied
{
    int pointure;
    Pied(int _pointure) : pointure(_pointure)
    {
        std::cout << "Pied::Pied()n";
    }
};
 
struct Humain : public Animal
{
    std::string nom;
    Pied piedGauche;
    Pied piedDroit;
    Humain() : piedGauche(40), piedDroit(40)
    {
        cout << "Humain::Humain()n";
    }
};
 
int
main()
{
    Humain humain;
}

La syntaxe

Animal::Animal(int _poids)
: poids(_poids)
{}

sert à initialiser les membres et les parents d'une classe.

• Qu'affiche ce programme ?
• Si on supprime le constructeur Animal::Animal(), que se passe-t'il ? Pourquoi ?
• Pourrait-on remplacer la déclaration Pied piedGauche, piedDroit; par Pied pieds[2]; ? Pourquoi ?

Un arbre binaire est une structure efficace pour la recherche de données, puisque celle-ci peut se faire en temps logarithmique. Un arbre sera ici constitué de nœuds, contenant chacun une donnée (ici un std::string) et deux fils. L'arbre de cet exercice sera trié : la valeur d'un nœud est supérieure à celle de son fils gauche, et inférieure à celle de son fils droit. Implémentez une classe Noeud et une classe Arbre de manière à ce que le programme suivant fonctionne :

int
main()
{
    Arbre arbre;
    arbre.insererValeur("titi");
    arbre.insererValeur("toto");
    arbre.insererValeur("bonjour");
    arbre.insererValeur("aurevoir");
    arbre.insererValeur("ca va?");
    arbre.insererValeur("zozo");
    Noeud *n1=arbre.trouver("toto");
    Noeud *n2=arbre.trouver("aurevoir");
    arbre.afficher();
}

Les algorithmes de recherche et d'insertion seront implémentés par des fonctions récursives.

La STL propose des conteneurs associatifs, permettant d'associer une clé de type quelconque à une valeur de type également quelconque. Il s'agit d'une généralisation des tableaux, où la clé est forcément entière. Ce type de conteneur est implémenté comme un arbre binaire. Voici un exemple d'utilisation de la classe std::map :

#include <iostream>
#include <map>
#include <string>
 
int main()
{
    std::map<std::string, float> poids;
    poids["souris"] = 10;
    poids["elephant"] = 1000000;
    std::cout << "L'elephant est "
              << (poids["elephant"]>poids["souris"]?"plus ":"moins ")
              << "lourd que la sourisn";
}