TigraoGPB
Messages postés2Date d'inscriptionmercredi 7 décembre 2016StatutMembreDernière intervention17 décembre 2016
-
Modifié par KX le 17/12/2016 à 17:30
Bonjour,
j'implémente une classe ArbreGene() en suivant une interface Arbre.
Le but est de créer des Arbres sous Java.
Mon TP me demade ensuite d'implémenter la méthode toString() de sorte qu'elle fasse un parcours (et donc un affichage) en profondeur avec l'utilisation d'une pile.
Puis on doit faire une autre implémentation de toString() cette fois ci en effectuant un parcours en largeur de l'arbre avec l'utilsiation d'une file.
La méthode toString() que j'ai réussis à implémenter parcours l'arbre en profondeur mais avec l'utilisation de la pile de récursivité.
Pourriez-vous m'aider à implémenter les deux autres toString : en profondeur selon une pile et en largeur selon une file ?
Voici mon Interface :
public interface Arbre<Element>{
public Element getElement (); // Retourne la racine
public int getDegree (); // Retourne le degré du " nœud " courant
public Arbre<Element> getNode(int i); // Retourne le sous-arbre i
public boolean isEmpty (); // Retourne vrai si l'arbre est vide
public boolean isLeaf (); // Retourne vrai si le nœud est une feuille
public void setElement(Element e); // Positionne la valeur courante du nœud racine
public void addNode(Arbre<Element> a); // Ajoute un sous-arbre fils (utilisation du constructeur par clonage)
public void deleteNode(int i); // Supprime le ième nœud fils
public String toString(); // Affichage des Elements
public boolean equals(Arbre<Element> a); // Test d'égalité
public int getHeight(); // Retourne la hauteur de l'arbre
}
Et voici ma Classe :
import java.util.*;
public class ArbreGene<Element> implements Arbre<Element>{
private Element element;
private LinkedList<ArbreGene<Element>> fils;
/*
* Constructeur par défaut :
*
* pas d'élément donc element = null.
* on initialise fils grace new LinkedList<ArbreGene<Element>>() pour pouvoir ensuite,
* dans le main, lui ajouter des elmt.
*/
public ArbreGene(){
element=null;
fils=new LinkedList<ArbreGene<Element>>();
}//ArbreGene
/*
* Constructeur par paramètre :
*
* prend comme paramètre Element e
* Donc on initialise la racine de l'abre à e : element=e
*
* Comme plus haut, on initialise fils grace new LinkedList<ArbreGene<Element>>() pour pouvoir ensuite,
* dans le main, lui ajouter des elmt.
*/
public ArbreGene(Element e){
element=e;
fils=new LinkedList<ArbreGene<Element>>();
}//ArbreGene
/*
* Constructeur par Clonage :
*
* prend comme paramètre Arbre<Element> a
*
* on initialise la racine de l'arbre courant avec la racine de l'arbre a : element=a.getElement() (getElement() permet de récupérer l'elmt donc la racine)
*
* Comme plus haut, on initialise fils grace new LinkedList<ArbreGene<Element>>() pour pouvoir ensuite,
* dans le main, lui ajouter des elmt.
*
* et maintenant il ne reste plus qu'à remplir l'arbre courant par les éléments de a
* pour ça on fait une boucle de la dimension de a et on ajoute, pour chaque i, grace à addNode
* le sous arbre de a ayant pour racine l'element placé à l'indice i :
* addNode(new ArbreGene<Element>(a.getNode(i)))
*/
public ArbreGene(Arbre<Element> a){
element=a.getElement();
fils=new LinkedList<ArbreGene<Element>>();
for(int i=0; i<a.getDegree(); i++){
addNode(new ArbreGene<Element>(a.getNode(i)));
}
}//ArbreGene
/*
* getElement() :
*
* retourne simplement l'attribut element de l'arbre
* à savoir sa racine.
*/
public Element getElement(){
return element;
}
/*
* getDegree():
*
* retourne la dimension de l'arbre, i.e. le nombre maximum de sous-arbres de la racine
*
* fils étant une Liste, on peut utiliser ma fonction Java size() sur fils
* et avoir la taille de la liste fils donc de l'arbre.
*/
public int getDegree(){
return fils.size();
}
/*
* getNode(int i) :
*
* retourne le i-ème sous-arbre.
*/
public Arbre<Element> getNode(int i){
if((i<0) || (i>=getDegree())){
System.out.println("ERREUR !");
return null;
}
return fils.get(i);
}//getNode
/*
* isEmpty() :
*
* retourne si l'arbre est vide ou pas.
*
* il suffit de regarder s'il existe une racine donc si element == null
*/
public boolean isEmpty(){
return (element==null);
}//isEmpty
/*
* isLeaf() :
*
* retourne vrai si l'arbre est une feuille et faux sinon
*
* donc il suffit de regarder si le nombre de fils de l'arbre est vide où non :
* getDegree()==0
*/
public boolean isLeaf(){
return (getDegree()==0);
}//isLeaf
/*
* setElement(Element e) :
*
* change la racine de l'arbre par e, un element passé en paramètre.
*/
public void setElement(Element e){
element=e;
}//setElement
/*
* addNode(Arbre<Element> a) :
*
* ajoute un arbre à l'arbre courant.
*
* On utilise la fonction générique add de java pour ajouter un new ArbreGene<Element> à fils
*/
public void addNode(Arbre<Element> a){
fils.add(new ArbreGene<Element>(a));
}//addNode
/*
* deleteNode(int i) :
*
* supprime le i-ème fils de l'arbre.
*
* on utilise la fonction générique remove(int) de java applqué sur fils
*
* on vérifie au préalable que l'indice i passé en paramètre soit supérieur à 0 et inférieur à la dimension de l'arbre donc
* à getDegree() car sinon l'élément à supprimer n'existe pas.
*/
public void deleteNode(int i){
if(i>=0 || i<=getDegree()){
fils.remove(i);
}
}//deleteNode
/*
* equals(Arbre<Element> a) :
*
* pour une meilleure efficacité on vérifie en premier trois conditions différentes qui sont :
*
* - si les racines des deux sont différentes ou non : si oui, pas besoin de continuer, on retourne faux
* - si on arrive au deuxième if c'est que la première condition est vérifiée donc les deux racines sont égales;
* donc si on regarde maintenant si l'un des deux arbre est une feuille, on retourne le buleen de la condition
* isLeaf() && a.isLeaf()) car on sait par le if que l'un ou l'aurte ou les deux sont une feuille
* d'où : si les deux sont des feuilles alors :
* _ vrai et vrai = vrai
* _ vrai et faux = faux
* et on obtient le bon résultat
* - si ces deux première conditions sont vérifiées i.e. les racines sont égales et que les deux arbres ne sont pas des feuilles,
* alors :
* on regarde si leur dimension sont égales : car si non alors on s'arrête là et on retourne faux.
*
* Une fois les trois conditions réunis i.e. les racines sont égales et que les deux arbres ne sont pas des feuilles
* et qu'ils ont la même dimensions, alors :
*
* on boucle sur la dimension et on compare chaque fils de chaque sous arbre du courant est égal un des fils du sou-arbre de même hauteur de a,
* a étant l'earbre passé en paramètre
*
* pour ça on utilise la récursivité et on rappel equals dans le deuxième while qui lui nous permet de comparer un même racine d'un sous-arbre
* du courant à toutes les racines du sous-arbre de même hauteur de a
*
* et on change test par la condition booléenne f.equals(a.getNode(j)).
*
* f étant un sous-arbre de l'arbre courant.
*
*/
public boolean equals(Arbre<Element> a){
boolean test=true;
int i=0;
if(element != a.getElement()){return false;}
if(isLeaf() || a.isLeaf()){return (isLeaf() && a.isLeaf());}
if(getDegree() != a.getDegree()){return false;}
while(test && i<getDegree()){
ArbreGene<Element> f = new ArbreGene<Element>(getNode(i));
int j=0;
test=false;
while(!test && j<a.getDegree()){
test = f.equals(a.getNode(j));
j++;
}//while j
i++;
}//while i
return test;
}
/*
* getHeight() :
*
* retourne la hauteur de l'arbre
*
* la condition if nous permet de garder à chaque fois le chemin le plus long pour des neuds différents
*/
public int getHeight(){
int h=0,c=0;
for(int i=0; i<getDegree(); i++){
h = 1+getNode(i).getHeight();
if(h>c){
c = h;
}//if
}//for
return c;
}
/*
* toString() :
*
* parcours normal de l'arbre en profondeur
*/
public String toString(){
String ch="{";
if(!isEmpty()){
ch+=element;
}
if(!isLeaf()){
for(int i=0; i<getDegree(); i++){
ch+="," + getNode(i).toString();
}//for i
}//if
ch+="}";
return ch;
}//toString
public static void main(String[] args) {
//Constructeur par paramètre
ArbreGene<String> a1 = new ArbreGene<String>("Méline");
System.out.println("Arbre a1 : " + a1);
//Constructeur par défaut
ArbreGene<String> a2 = new ArbreGene<String>();
System.out.println("Arbre a2 : " + a2);
//Constructeur par clonage
ArbreGene<String> a3 = new ArbreGene<String>(a2);
//getElement()
System.out.println("Racine de a1 : " + a1.getElement());
//getDegree
System.out.println("degré de a1 : " + a1.getDegree());
//isEmpty
System.out.println("a1 est vide ? : " + a1.isEmpty());
System.out.println("a2 est vide ? : " + a2.isEmpty());
System.out.println();
//isLeaf
System.out.println("a1 est une feuille ? : " + a1.isLeaf());
System.out.println("a2 est une feuille ? : " + a2.isLeaf());
//setElement
a1.setElement("Marie");
System.out.println("Arbre a1 : " + a1);
a2.setElement("Méline");
a3.setElement("Maxime");
System.out.println("Arbre a3 : " + a3);
System.out.println();
//addNode
a2.addNode(a3);
a2.addNode(a3);
System.out.println("a2 : " +a2);
a1.addNode(a2);
System.out.println("Arbre a1 : " + a1);
//getNode
System.out.println("Sous-Arbre 2 de a1 : "+a1.getNode(0));
System.out.println();
//equals
System.out.println("Arbre a1 egale Arbre a2 ? : " + a1.equals(a2));
System.out.println("Arbre a2 egale Sous-Arbre 0 de a1 ? : " + a2.equals(a1.getNode(0)));
System.out.println();
//delete
a2.deleteNode(1);
System.out.println("Arbre a2 après delete(1) : " +a2);
System.out.println();
//getHeight
System.out.println("hauteur de l'Arbre a1 : " + a1.getHeight());
System.out.println("hauteur de l'Arbre a2 : " + a2.getHeight());
}//main
}