[Java]Arbre n-aire

Marsh Posté le 22-03-2006 à 07:27:38

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)

Code :

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

Cette classe utilise les noeuds sans fils

Code :

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

Noeud ayant un ou plusieurs fils

Code :

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

Code :

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

Code :

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

Reply

Marsh Posté le 22-03-2006 à 07:27:38

Reply

Marsh Posté le 22-03-2006 à 13:00:58

Faut faire l'exo à ta place ?

---------------
Commons Configuration - http://jakarta.apache.org/commons/configuration

Reply

[Java]Arbre n-aire

Sujets relatifs:

Leave a Replay