[Java]Arbre n-aire

Man_Utd · 22 Mars 2006

Bonjour,

j'ai codé différentes méthodes pour des arbres n-aires.
Je mets les différents code pour que vous puissiez m'aider.
J'aurais d'aide besoin pour l'écriture d'une méthode traverse qui renvoie la liste des noeuds(List<Node>) en ordre préfixe

Merci d'avance

Cette classe permettra d'utiliser la classe Leaf(noeud n'ayant pas de fils) ou la classe InternalNode(noeud ayant un ou plusieurs fils)
[cpp]import java.util.*;

public abstract class Node {
private final int data;

public Node(int data) {
this.data = data;
}

public int getData(){
return data;
}

public int size(){
return 1;
}

public boolean contains (int i){
return data == i;
}
}
[/cpp]

Cette classe utilise les noeuds sans fils
[cpp]import java.util.*;

public class Leaf extends Node{

public Leaf(int data){
super(data);
}

public int size(){
return super.size();
}

public boolean contains(int i){
return super.contains(i);
}

@Override public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(getData()).append(" ");

return sb.toString();
}

@Override public boolean equals(Object o){
if(!(o instanceof Leaf))
return false;

Leaf l = (Leaf)o;
return getData() == l.getData();
}
}
[/cpp]

Noeud ayant un ou plusieurs fils
[cpp]import java.util.*;

public class InternalNode extends Node{
private final List<Node> children;

public InternalNode(int data, List<Node> children){
super(data);
this.children = children;
}

public List<Node> getChildren(){
return children;
}

@Override public int size(){
int size = 1;
for(Node n : children){

size += n.size();
}
return size;
}

@Override public boolean contains(int i){
if(getData() == i)
return true;

boolean ret = false;
int j = 0;

while(!ret && j < children.size()){
ret = children.get(j++).contains(i);
}
return ret;
}

@Override public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(getData()).append(" ").append(children.toString());

return sb.toString();
}

@Override public boolean equals(Object o){
boolean ret = false;

if(!(o instanceof InternalNode))
return ret;

InternalNode n = (InternalNode)o;
return (getData() == n.getData() && children.equals(n.children));
}
}
[/cpp]

[cpp]import java.util.*;

public class Tree {
private final Node root;

public Tree(Node root){
this.root = root;
}

public String toString() {
return root.toString();
}

public int size() {
return root.size();
}

public boolean contains(int i) {
return root.contains(i);
}

public boolean equals(Object o) {
return root.equals(o);
}
}
[/cpp]

[cpp]import java.util.*;

public class Main{
public static void main(String [] args){
List<Node> listThree = new ArrayList<Node>();
listThree.add(new Leaf(5));
listThree.add(new Leaf(6));
List<Node> listOne = new LinkedList<Node>();
listOne.add(new Leaf(2));
listOne.add(new InternalNode(3, listThree));
listOne.add(new Leaf(4));
Node one = new InternalNode(1, listOne);
Tree tree = new Tree(one);

List<Node> listThree2 = new ArrayList<Node>();
listThree2.add(new Leaf(9));
listThree2.add(new Leaf(6));
List<Node> listOne2 = new LinkedList<Node>();
listOne2.add(new Leaf(2));
listOne2.add(new InternalNode(3, listThree2));
listOne2.add(new Leaf(4));
Node one2 = new InternalNode(1, listOne2);
Tree tree2 = new Tree(one2);

System.out.println(one.size());
System.out.println(one.contains(6));
System.out.println(one);
System.out.println(one.equals(one2));
}
}
[/cpp]

Anubis_ · 22 Mars 2006

totofetmax :

C'est vraiment super facile, je suis étonné que tu sois parvenu à écrire toutes ces classes et que maintenant tu butes là dessus. Qu'est-ce qui te bloque précisément ?

Man_Utd · 22 Mars 2006

nexo59 :

Salut,
Voici ce que j'ai fait :
[cpp]public List<Node> traverse(){
return root.traverse();
}[/cpp]

Cela me renvoie bien la liste des noeuds en ordre préfixe mais je n'ai pas le sommet

Anubis_ · 22 Mars 2006

totofetmax :

Ta classe abstraite Node devrait donc contenir une méthode traverse, ce qui n'est pas le cas dans le code que tu as cité. Ensuite, cette méthode devra être spécialisée, selon le type de noeud (noeud avec ou sans enfants).
La spécialisation se fait de la manière suivante :

■pour un noeud de type feuille, traverse doit retourner une liste à un élément qui est cette feuille.
■pour un autre noeud, traverse doit retourner une liste contenant lui-même, puis les noeuds retournés par traverse appliquée à chacun de ses enfants, dans l'ordre.

Par ailleurs, quel est l'intérêt de la classe Tree, puisqu'un noeud est déjà un arbre en soi ? Ta classe Tree n'ajoute aucune fonctionnalité : elle répercute tous les appels de méthodes sur le noeud racine.

Bonne continuation

Man_Utd · 22 Mars 2006

nexo59 :

Je n'ai pas édité le programme que j'ai posté mais j'ai bien rajouter la méthode traverse dans mes différentes classes.
J'avais compris qu'il fallait que je renvoie une liste à un élement pour ma classe Leaf mais je ne sais pas comment m'y prendre pour que l'attribut data soit considéré comme un élément d'une liste de noeud ,de même pour la classe InternalNode

Anubis_ · 22 Mars 2006

totofetmax :

La méthode traverse de la classe Leaf renverra bien une liste contenant l'instance du noeud qui a appelé cette fonction. Je n'ai pas fait de java depuis 1 an, mais ça devrait ressembler à ça :

[cpp]
class Leaf [...]
{
[...]
public List<Node> traverse()
{
result = new List<node>();
result.add(this);
return result;
}
[...]
}
[/cpp]
Pour le traverse de la classe InternalNode :

[cpp]
class InternalNode [...]
{
[...]
public List<Node> traverse()
{
result = new List<node>();
// D'abord ajouter le noeud visité
result.add(this);
for (Node child: children)
{
// Ensuite ajouter les noeuds de chaque enfant
result.addAll(child.traverse());
}
return result;
}
[...]
}
[/cpp]
Je crois que ça fait l'affaire.

Anubis_ · 22 Mars 2006

Une autre petite remarque : dans la classe InternalNode, tu ne vérifies pas que la liste des noeuds enfants passée au constructeur n'est pas vide : si cette liste est vide, ton noeud InternalNode n'a pas d'enfants et est donc sémantiquement une feuille.

Soit tu dois faire un test dans le constructeur (et échouer su la liste est vide, mais ça ne me plait pas tellement...), soit tu peux ne faire aucune différence entre feuille et noeud interne, et te débarasser de ces 2 classes en implémentant l'ensemble des fonctionnalités nécessaires dans la classe Node directement.

Man_Utd · 22 Mars 2006

nexo59 :

Salut,
merci pour le code,il y a un problème car lorsque j'utilise le new List<Node> comme dans ton exemple,j'ai ce message pour Leaf(en utilisant l'appel à Node) et InternalNode ce qui est normal car Node est une classe abstraite:
[cpp]./Node.java:23: java.util.List is abstract; cannot be instantiated
List<Node> result = new List<Node>();
^

./InternalNode.java:55: java.util.List is abstract; cannot be instantiated
List<Node> result = new List<Node>();
^
[/cpp]

J'enlève les 2 new() et je n'ai plus que ceci comme erreur:
[cpp]./Node.java:24: cannot find symbol
symbol : method add(int)
location: interface java.util.List<Node>
result.add(this.getData());
^
./InternalNode.java:56: cannot find symbol
symbol : method add(int)
location: interface java.util.List<Node>
result.add(this.getData());
^
2 errors
[/cpp]

avec ceci comme code dans la classe Node
[cpp]public List<Node> traverse(){
List<Node> result;
result.add(this.getData());
return result;
}[/cpp]

et ceci dans la classe InternalNode
[cpp]public List<Node> traverse(){
List<Node> result;
result.add(this.getData());

for (Node child: children){
result.addAll(child.traverse());
}
return result;
}[/cpp]

Anubis_ · 22 Mars 2006

écoute le compilateur : il te dit que la classe List est abstraite. Et il a raison, elle l'est. C'est moi qui me suis un peu gouré dans le morceau de code, il faut utiliser une implémentation de liste, et pas l'interface. remplace
[cpp]List<Node> result = new List<node>();[/cpp]
par
[cpp]List<Node> result = new Vector<node>();[/cpp]

et si tu fais ça :
[cpp]result.add(this.getData());[/cpp]
à la place de ça
[cpp]result.add(this);[/cpp]
il faut changer le typage du conteneur de <Node> à <int>...

Moi je te donne les principes généraux, pas le code au mot près, il faut savoir interpréter et adapter un peu.

Anubis_ · 22 Mars 2006

Pour info, je viens d'écrire une courte implémentation d'arbre n-aire, qui n'utilise qu'une seule classe.
[cpp]import java.util.List;
import java.util.Vector;

public class Node<E> {

private final Vector<Node<E>> children;
private final E element;

public Node(E theElement) {
this.children = new Vector<Node<E>>();
this.element = theElement;
}
public Node(E theElement, List<Node<E>> theChildren)
{
this.children = (Vector<Node<E>>) theChildren;
this.element = theElement;
}

public Vector<E> getElementsPrefix()
{
Vector<E> result = new Vector<E>();
result.add(this.element);
for (Node<E> childNode : this.children)
{
result.addAll(childNode.getElementsPrefix());
}
return result;
}
public int count()
{
int sum = 1;
for (Node<E> childNode : this.children)
{
sum += childNode.count();
}
return sum;
}
}[/cpp]

pour la tester :

[cpp]
Vector<Node<Integer>> children1 = new Vector<Node<Integer>>();
children1.add(new Node<Integer>(1));
children1.add(new Node<Integer>(2));

Vector<Node<Integer>> children2 = new Vector<Node<Integer>>();
children2.add(new Node<Integer>(3, children1));
children2.add(new Node<Integer>(4));

Node<Integer> tree = new Node<Integer>(0, children2);

Vector<Integer> nodes = tree.getElementsPrefix();
System.out.println(nodes.toString());
[/cpp]

ce qui correspond à l'arbre
[fixed]
0
/ \
3 4
/ \
1 2
[/fixed]
Je ne sais pas ce que ça vaut, j'ai pas fait de java depuis un bail (je découvre les génériques en java), mais ça semble vouloir fonctionner. La liste des valeurs parcourue en ordre préfixe est [0, 3, 1, 2, 4]

Man_Utd · 22 Mars 2006

En faite ,il reste encore un soucis concernant l'affichage de la liste .
Avec la méthode toString() que j'ai écrit,j'obtiens:

Code:

1 [2 , 3 [5 , 6 ], 4 ]

alors qu'avec traverse,j'obtiens ceci:

Code:

[1 [2 , 3 [5 , 6 ], 4 ], 2 , 3 [5 , 6 ], 5 , 6 , 4 ]

je trouve cela bizzare car je ne vois pas ce qui pourrait amener cette affichage.Le programme affiche dans un premier temps l'arbre en ordre préfixe :
[cpp][1 [2 , 3 [5 , 6 ], 4 ],[/cpp]
puis 2 (seul car pas de fils):
[cpp]2[/cpp]
,puis 3 et ses fils :
[cpp] 3 [5 , 6 ] [/cpp]
puis 5,
puis 6
et enfin 4 .

Avec un arbre de cette forme:
[fixed]
1
/ | \
2 3 4
/ \
5 6
[/fixed]

Anubis_ · 22 Mars 2006

Le problème c'est que la méthode toString de tes noeuds renvoit le sous-arbre, et pas seulement la valeur du noeud.

[Java]Arbre n-aire

Man_Utd

Anubis_

Man_Utd

Anubis_

Man_Utd

Anubis_

Anubis_

Man_Utd

Anubis_

Anubis_

Man_Utd

Anubis_