Aller au contenu

[Java]Arbre n-aire


Premium

Messages recommandés

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)

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

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

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

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

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

Lien vers le commentaire
Partager sur d’autres sites

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

×
×
  • Créer...