TD 4 - Arbres binaires de recherche

• la première correspond aux éléments strictement inférieurs à une valeur donnée x ;
• la deuxième partie contient les éléments strictement supérieurs à cette valeur.

• si l'un des deux arbres est vide, on termine en renvoyant l'autre ;
• sinon
• on décompose l'ensemble B (autour de la valeur a) : on obtient ainsi deux arbres B1 et B2.
• récursivement on crée deux sous-arbres G:=(A_g union B1) et D:= (A_d union B2) ;
  
• on renvoie comme résultat l'arbre R, ayant comme valeur racine a, et dont le sous-arbre gauche et droit sont respectivement G et D.

Dans cet exercice, on cherche à écrire un algorithme qui teste si deux arbres binaires de recherche représentent le même ensemble. On pourrait convertir les deux arbres en listes triées d'entiers et comparer ces dernières, mais ces conversions nécessitent de parcourir entièrement les deux arbres, ce qu'il est dommage de faire si par exemple les deux arbres diffèrent dès leurs plus petits éléments.

L'idée est de procéder paresseusement : au lieu d'aplatir entièrement un arbre en une liste d'entiers, nous allons le convertir en une liste dont chaque maillon contient un entier et un arbre. Cette liste a la même longueur que la branche la plus à gauche de l'arbre de départ et chaque maillon correspond à un noeud de cette branche : l'entier du maillon est la valeur sur le noeud, et l'arbre dans le maillon est le fils droit du noeud.

Le premier des deux arbres ci-contre sera donc converti en une liste dont la tête contient l'entier 1 et l'arbre null, dont le deuxième maillon contient l'entier 4 et l'arbre réduit à la feuille 5, et le troisième maillon contient l'entier 7 et l'arbre de racine 16 (inchangé).

• la méthode  Enum build(TreeNode t, Enum acc) qui  construit la liste représentant (comme décrit ci-dessus) l'arbre t, en la concaténant à la liste acc qui vient derrière. On écrira une méthode récursive, acc jouant le rôle d'un accumulateur.

Il ne vous reste donc qu'à compléter la méthode

• boolean equals(Enum x, Enum y) qui teste si deux listes contiennent exactement les mêmes éléments. On procédera ainsi, récursivement :
• si les deux listes sont vides, alors la comparaison est positive ;
• si l'une des deux listes vient à s'épuiser, alors la comparaison est négative ;
• sinon, on vérifie si le premier maillon de x et le premier maillon de y contiennent le même entier ; si ce n'est pas le cas, la comparaison est négative ; si en revanche c'est le cas, il faut continuer la vérification avec, et pour x et pour y, les entiers se trouvant dans l'arbre du premier maillon et les entiers se trouvant dans les maillons suivant. A vous de trouver comment (mais il sera utile de se servir du constructeur Enum build(TreeNode t, Enum acc)).

public class Enum {
  final int root;
  final TreeNode right;
  final Enum next;
    
  public Enum(int root, TreeNode right, Enum next) {
    this.root = root;
    this.right = right;
    this.next = next;
  }
    
  static Enum build(TreeNode t, Enum acc) {
    throw new Error("A completer: exo 2");
  }
    
  static boolean equals(Enum x, Enum y) {
    throw new Error("A completer: exo 2");
  }

}