R3.02 - dev. efficace

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
	*/
    }
}

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");
	}
    }
}

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

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