Licence 3 info/M IAGE
PRG1 - année 2022/2023
PRG1 – TD12 – Correction
4.4. Représentation des arbres binaires
On s’intéresse aux représentations chaînées par références selon 2 techniques : chaînage père et pile de
pères.
4.4.1. Chaînage père
Chaque élément d’arbre possède 4 champs : value, father, left, right.
1 public class BinaryTree<T>
2 {
3 private class Element
4 {
5 public T value;
6 Element father, left, right;
7 public Element()
8 {
9 value = null;
10 father = null;
11 left = null;
12 right = null;
13 }
14 public Element(Element father)
15 {
16 value = null;
17 this.father = father;
18 left = null;
PRG1 année 2022/2023
Licence 3 info/M IAGE PRG1 – TD12 – Correction
19 right = null;
20 }
21 }
22 public class TreeIterator implements Iterator<T>
23 {
24 private Element currentNode;
25 private TreeIterator() { ... }
26 ...
27 }
28 private Element root;
29 ...
30 }
PRG1 2 année 2022/2023
Licence 3 info/M IAGE PRG1 – TD12 – Correction
Exo 4.5.
PRG1 3 année 2022/2023
Licence 3 info/M IAGE PRG1 – TD12 – Correction
Exo 4.6.
Énoncé :
Écrire les constructeurs BinaryTree et TreeIterator, et les méthodes goLeft, goUp, addValue.
Solution :
1 public BinaryTree()
2 {
3 root = new Element();
4 }
5
6 private TreeIterator()
7 {
8 currentNode = root;
9 }
10
11 public void goLeft()
12 {
13 assert !this.isEmpty() : "le butoir n’a pas de fils";
14 currentNode = currentNode.left;
15 }
16
17 public void goUp()
18 {
19 assert currentNode != root : "la racine n’a pas de père";
20 currentNode = currentNode.father;
21 }
22
23 public void addValue(T v)
24 {
25 assert this.isEmpty() : "Ajouter : on n’est pas sur un butoir";
26 currentNode.value = v;
27 currentNode.left = new Element(currentNode);
28 currentNode.right = new Element(currentNode);
29 }
Expliquer que la classe interne TreeIterator n’est pas statique et donc chaque instance est attachée à un
objet BinaryTree d’où la possibilité d’accès à l’attribut root (de façon plus verbeuse BinaryTree.this.root).
4.4.2. Pile de pères
En 4.1, le lien father permet d’atteindre les ancêtres de currentNode. Pour économiser de la place,
on supprime le champ father de chaque élément et on ajoute, à la classe TreeIterator, un attribut pile
correspondant à une pile d’éléments mémorisant les références des ancêtres de currentNode.
Faire un exemple au tableau.
Les méthodes de la classe Stack sont
PRG1 4 année 2022/2023
Licence 3 info/M IAGE PRG1 – TD12 – Correction
void push(Element e) // empiler
Element pop() // dépiler
Element peek() // sommet
boolean isEmpty()
void clear()
1 public class BinaryTree<T>
2 {
3 private class Element
4 {
5 public T value;
6 public Element left, right;
7 public Element()
8 {
9 value = null;
10 left = null;
11 right = null;
12 }
13 }
14 public class TreeIterator implements Iterator<T>
15 {
16 private Element currentNode;
17 private Stack<Element> stack;
18 private TreeIterator() { ... }
19 ...
20 }
21 private Element root;
22 ...
23 }
Exo 4.7.
Énoncé :
Écrire les méthodes goLeft, goUp, goRoot et remove (si pas le temps pour remove, ce n’est pas très
grave, ils le feront en TP de toutes facons).
Solution :
1 public void goLeft()
2 {
3 assert !this.isEmpty() : "le butoir n’a pas de fils";
4 stack.push(currentNode);
5 currentNode = currentNode.left;
6 }
7
8 public void goUp()
PRG1 5 année 2022/2023
Licence 3 info/M IAGE PRG1 – TD12 – Correction
9 {
10 assert !stack.isEmpty() : "la racine n’a pas de père";
11 currentNode = stack.pop();
12 }
13
14 public void goRoot()
15 {
16 stack.clear();
17 currentNode = root;
18 }
19
20 public void remove()
21 {
22 assert this.nodeType() != NodeType.DOUBLE :
23 "remove : retrait d’un nœud double non permis";
24 Element newCurrentNode = null;
25 switch (nodeType())
26 {
27 case SENTINEL : return; // rien à enlever
28 case DOUBLE : break; // cas impossible
29 case SIMPLE_LEFT : newCurrentNode = currentNode.left;
30 break;
31 case SIMPLE_RIGHT : newCurrentNode = currentNode.right;
32 break;
33 case LEAF : newCurrentNode = new Element();
34 break;
35 }
36 currentNode.value = newCurrentNode.value;
37 currentNode.left = newCurrentNode.left;
38 currentNode.right = newCurrentNode.right;
39 }
PRG1 6 année 2022/2023
