M3103 – TP4 Exercice 1

Reprenez la classe CNode de l’exercice précédent, renommez les données membres m_Prec et m_Next en respectivement m_LC (left child) et m_RC (right child).
Mettez à jour les accesseurs et modifieurs correspondants.

En vous inspirant de la classe CList, créez la classe CRDTree (arbre aléatoire – Random Tree), elle aussi générique.

Les modifications sont les suivantes :

  1. le constructeur contient un paramètre (la donnée), crée un smart pointer contenant cette donnée et initialise la racine à cette adresse (ie, on n’a plus de tête fictive);
  2. la fonction show () parcours toutes les branches de l’arbre;
  3. la fonction add (), qui ne contient qu’un paramètre (la valeur à insérer dans l’arbre), doit avoir le comportement suivant :
    1. s’il n’y a pas de fils gauche, alors on insère dans ce dernier;
    2. s’il n’y a pas de fils droit, alors on insère dans ce dernier;
    3. sinon on explore aléatoirement (rand () % 2) le sous arbre de gauche, ou de droite.

M3103 – TP4 Exercice 2

Modifier l’exercice précédent de façon à obtenir un arbre binaire de recherche.

Seule la fonction add () doit être modifiée.

Ecrire ensuite le prédicat find() qui renvoie vrai si le paramètre passé en argument est présent dans l’arbre, faux sinon.

M3103 – TP4 Exercice 3

Modifier l’exercice précédent de façon à ce que l’arbre ait une structure de maximier : contrairement à l’arbre binaire de recherche, le maximier est un arbre dans lequel la valeur de la racine (ici un entier) est supérieure celle de n’importe laquelle de ses sous arbres.

M3103 – TP4 Exercice 4

  1. Faites en sorte de pouvoir afficher votre arbre sans utiliser de fonction d’aide dite “locale”.
  2. Afficher la vue arborescente de l’arbre : chaque fils est décalé d’une indentation par rapport à son père.