TD 6 - Arbres binaires de recherche

On souhaite construire un type de données "arbre binaire de recherche" pour stocker des entiers.

Rappel : A chaque noeud est associé un entier. Etant donné un noeud r, on note val(r) la valeur stockée. On a la propriété suivante : tout noeud r' du sous-arbre gauche (resp. droit) de r vérifie : val(r') <= val(r) (resp. val(r') > val(r)).

Un arbre binaire de recherche est muni des opérations :

• Ajouter(int v) : pour ajouter un noeud avec une valeur v.
• Contient(int v) : retourne VRAI si il existe un noeud contenant la valeur v.
• Est_vide() : retourne VRAI si l'arbre binaire de recherche est vide ou non.
• Parcours() : qui parcours l'arbre binaire de recherche de manière à ce que les valeurs des noeuds soient affichées dans l'ordre croissant.

1. Implémenter une classe ABR à partir du canevas suivant

  class Noeud {
  private :
    int _val;
    Noeud * _fg;
    Noeud * _fd;

  public :
    Noeud(int v,Noeud * g =0,Noeud * d =0);
    int Val();
    Noeud * FG();
    Noeud * FD();
    void Ajouter(int x);
    void Affiche_tri();
    Noeud* Recherche(int x);
    int Contient(int x);
  };


class ABR {
  private :
   Noeud * _racine;

  public :
   ABR();

  // fct classiques: 
  void Ajouter(int x);
  bool Contient(int x);
  bool Est_vide();

  // fct en plus:
  ABR FilsG();
  ABR FilsD();
  int Val();
  void Affiche_tri();
  ABR  Recherche(int x);
};
  

La classe ABR correspond à un objet de type ABR, i.e. muni des opérations Ajouter, Contient et Est_vide. La partie "données" se limite à un pointeur sur la racine de l'arbre correspondant à l'ABR. En particulier, si l'ABR est vide, le pointeur sur la racine vaut 0.

La classe Noeud correspond aux noeuds de l'ABR. On définit, sur cette classe, les différentes fonctions de manipulation nécessaires pour la définition des opérations des ABR.

2. Intégrer la classe Noeud dans la classe ASBR.

3. Ajouter une focntion Supprimer(v)