Exercice n°1

• Créez le fichier Node.java à partir du code ci-dessous, et complétez aux endroits indiqués.

import java.util.*;
 
class Node {
 
    public List<Node> children;
    public int value;
 
    public Node(int value) {
	this.value = value;
	children = new ArrayList<Node>();
    }
 
    /* addChild(int value) :
       créer un nouveau noeud contenant value
       et l'ajoute comme fils au noeud courant
       renvoie le nouveau noeud
     */
    public Node addChild(int value) {
 
	// à compléter
    }
 
    /* addChild(Node n) :
       ajoute n comme fils au noeud courant
     */
    public void addChild(Node n) {
 
	// à compléter
    }
 
    /* getChild(int index) :
       si index <0 ou >= taille list, renvoie null
       sinon renvoie le fils en index
 
     */
    public Node getChild(int index) {
 
	// à compléter       
    }
}

Exercice n°2

• Créez le fichier Tree.java à partir du code ci-dessous et complétez les méthodes en suivant les indications.

import java.util.*;
 
class Tree {
 
    public Node root;
    public int nbNodes; // pas nécessaire mais utile
 
    public Tree() {
	root = null;
	nbNodes = 0;
    }
 
    public Node addNode(int value, Node parent) {
	/*
 
	  - si parent est null :
	     - créer un nouveau noeud contenant value
	     - si root existe déja : ajouter root comme fils du nouveau noeud
	     - root devient le nouveau noeud
	     - incrémenter le nombre de noeud
	     - renvoyer le nouveau noeud
	  - sinon si l'arbre contient parent
	     - ajouter un noeud fils à parent, contenant value
	     - incrémenter le nombre de noeud
	     - renvoyer le nouveau noeud
	  - sinon renvoyer null
	*/
    }
 
    public Node contains(Node toSearch, Node parent) {
 
	// NB : la recherche doit se faire en profondeur d'abord
    }
 
    public Node searchValueByLevel(int value, Node parent) {
 
	// NB : la recherche doit se faire en largeur d'abord */
 
    }
 
    public Node searchValueByDepth(int value, Node parent) {
 
	// NB : la recherche doit se faire en profondeur d'abord */
 
    }
 
    public Node searchValue(int value, int type) {
        Node n = null;
        if (type == 1) n = searchValueByDepth(value, root);
        else if (type == 2) n = searchValueByLevel(value, root);
        return n;
    }
 
    public void print() {
	if (root != null) {
	    printNode(root,0);
	}
    }
 
    public void printNode(Node n,int level) {
	/*
	  - afficher 2*level espace puis la valeur contenue dans n
	  - pour chaque noeud fils de n :
	     - afficher le contenu du noeud, en incrémentant le niveau
	*/
    }
}

Pour tester les deux classes ainsi créées, utilisez le code suivant :

class TestTree {
 
    public static void main(String[] args) {
 
	Tree tree = new Tree();
 
	Node root = tree.addNode(20,null); // création racine
	root = tree.addNode(10,null); // test remplacement racine
	Node n1 = tree.addNode(21,root);
	n1.addChild(30);
	Node n2 = n1.addChild(31);
	Node n3 = n1.addChild(32);
	n2.addChild(40);
	n2 = n2.addChild(41);
	n3.addChild(45);
	n3.addChild(46);
	Node n4 = n3.addChild(47);
	n4.addChild(50);
	n4 = n4.addChild(51);
 
	tree.print();
 
	Node s = tree.contains(n3,root);
	if (s != n3) {
	    System.out.println("echec recherche du noeud contenant 32");
	}
	s = tree.contains(n2,root);
	if (s != n2) {
	    System.out.println("echec recherche du noeud contenant 41");
	}
	s = tree.contains(n4,root);
	if (s != n4) {
	    System.out.println("echec recherche du noeud contenant 51");
	}
 
	s = tree.searchValue(45,1); // recherche en profondeur
	if (s.value != 45) {
	    System.out.println("echec recherche valeur 45");
	}
	s = tree.searchValue(50,2); // recherche en largeur
	if (s.value != 50) {
	    System.out.println("echec recherche valeur 50");
	}
	s = tree.searchValue(60,1); // recherche en profondeur
	if (s != null) { // si on trouve qq chose = pas normal
	    System.out.println("echec recherche valeur 60");
	}
    }
}

Normalement, l'exécution produit l'affichage suivant :

affichage de l'arbre en profondeur
10
  20
  21
    30
    31
      40
      41
    32
      45
      46
      47
        50
        51

Exercice n°3

• Inspirez vous de la méthode searchValueByLevel() pour créer une méthode printLevel() permettant de parcourir l'arbre en largeur.
• Normalement, l'appel à tree.printLevel() dans TestTree doit donner le résultat suivant :

10
  20
  21
    30
    31
    32
      40
      41
      45
      46
      47
        50
        51