PROFDINFO.COM

Votre enseignant d'informatique en ligne

Un dictionnaire dans un arbre

Voici une solution possible pour le laboratoire de l'arbre binaire. Elle contient la classe Arbre (qui elle-même contient la classe Noeud) et une classe Programme que j'ai utilisée pour tester vos travaux.

Quelques commentaires en passant:

 

L'itérateur récursif

Puisqu'entre le moment où vous avez débuté ce travail et le moment où je vous donne la solution nous avons vu les itérateurs, j'ai décidé d'en créer un pour l'arbre.

L'arbre est différent de la liste puisqu'il est beaucoup plus efficace de le parcourir récursivement. Peut-on faire un itérateur récursif? La réponse est évidemment oui, mais il faut simplement savoir comment.

GetEnumerator() ne peut pas être écrite directement de façon récursive puisqu'elle ne reçoit aucun paramètre. Par contre on pourrait très bien utiliser un foreach à l'intérieur de GetEnumerator(), ce qui reviendrait exactement à une forme récursive, en autant que notre foreach soit appliqué sur un sous-arbre et qu'on arrête de l'appeler un moment donné.

Le problème c'est que si notre arbre est bien un Arbre, les deux enfants de la racine, eux, sont des Noeuds et pas des Arbres (même si on peut les voir comme des sous-arbres). On ne peut donc pas faire un foreach si le Noeud lui-même n'a pas d'itérateur.

(On pourrait penser à créer un Arbre à partir de chaque Noeud puisqu'on a un constructeur qui le permet, mais premièrement c'est une solution bien peu efficace et très coûteuse en mémoire et en plus notre constructeur d'Arbre à partir d'un Noeud utilise l'itérateur de l'Arbre pour déterminer la valeur du nbÉléments... Donc solution non viable.)

Supposons alors qu'on a un itérateur dans notre Noeud, qui nous permet de considérer un Noeud comme une collection énumérable qui contient plein d'autres Noeuds. L'itérateur de notre Arbre est alors assez simple:

public IEnumerator GetEnumerator()
{
   if (_racine != null)
   {
      foreach (Noeud nn in _racine)
         yield return nn;
   }
}

Si la racine est nulle on ne fait rien puisqu'il n'y a rien à énumérer. Sinon, on considère le noeud racine comme une collection énumérable et donc on l'énumère avec un foreach. Chaque item retourné par le foreach du Noeud sera retourné par notre itérateur d'Arbre.

Notre arbre est donc énumérable si le Noeud racine qu'il contient est énumérable.

Du côté du Noeud maintenant, on fera:

public IEnumerator GetEnumerator()
{
   if (_gauche != null)
      foreach (Noeud nn in _gauche)
         yield return nn;
         
   yield return this;

   if (_droite != null)
      foreach (Noeud nn in _droite)
         yield return nn;
}

Comme un Noeud est énumérable et qu'un Noeud contient en fait deux autres Noeuds, on énumère simplement le contenu de notre noeud de gauche, puis on retourne le noeud courant, et finalement on énumère le contenu du noeud de droite.

C'est donc bien un énumérateur récursif puisqu'il utilise le foreach pour appeler l'itérateur de chaque sous-noeud.

Du coup, notre constructeur d'Arbre à partir d'un Noeud peut aisément compter le nombre de Noeuds qu'on lui passe et ajuster son attribut nbElements en conséquence.

Et tant qu'à avoir fait des Arbres et des Noeuds énumérables, pourquoi ne pas officialiser la chose en dérivant explicitement la classe Arbre et la classe Noeud de IEnumerable?

Le programme de correction

Le programme que j'ai utilisé pour corriger vos arbres demande à ce que la classe Noeud soit publique et qu'il y ait une façon d'accéder en lecture à la racine d'un Arbre. Si ce n'était pas le cas (puisque je ne l'avais pas demandé explicitement), j'ai modifié votre code en conséquence, ce qui n'avait aucun impact sur votre classe autrement.

Le correcteur suppose également que les propriétés Racine et AGauche du Noeud existent et fonctionnent (je modifiais mon code si vous ne les aviez pas, mais vous perdiez alors des points de respect des spécifications).

Le programme teste un à un chaque opération possible sur votre arbre, en attrapant les éventuelles exceptions pour ne pas planter (le StackOverflow ne peut pas être attrapé par contre, alors les arbres infinis faisaient planter le correcteur malgré tout).

La fonction AfficherArbre est une fonction récursive qui affiche le contenu de votre arbre de façon formatée sous forme d'arborescence. Ceci me permettait de voir de quoi avait l'air votre arbre après des insertions ou supressions.