[Java]Arbre n-aire

Arbre n-aire [Java] - Java - Programmation

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 :
  1. import java.util.*;
  2. public abstract class Node {
  3.     private final int data;
  4.    
  5.     public Node(int data) {
  6. this.data = data;
  7.     }
  8.    
  9.     public int getData(){
  10. return data;
  11.     }
  12.    
  13.     public int size(){
  14. return 1;
  15.     }
  16.    
  17.     public boolean contains (int i){
  18. return data == i;
  19.     }
  20. }


 
 
Cette classe utilise les noeuds sans fils

Code :
  1. import java.util.*;
  2. public class Leaf extends Node{
  3.    
  4.     public Leaf(int data){
  5. super(data);
  6.     }
  7.    
  8.     public int size(){
  9. return super.size();
  10.     }
  11.    
  12.     public boolean contains(int i){
  13. return super.contains(i);
  14.     }
  15.    
  16.     @Override public String toString(){
  17. StringBuilder sb = new StringBuilder();
  18. sb.append(getData()).append(" " );
  19. return sb.toString();
  20.     }
  21.    
  22.     @Override public boolean equals(Object o){
  23. if(!(o instanceof Leaf))
  24.     return false;
  25. Leaf l = (Leaf)o;
  26. return getData() == l.getData();
  27.     }
  28. }


 
Noeud ayant un ou plusieurs fils

Code :
  1. import java.util.*;
  2. public class InternalNode extends Node{
  3.     private final List<Node> children;
  4.    
  5.     public InternalNode(int data, List<Node> children){
  6. super(data);
  7. this.children = children;
  8.     }
  9.    
  10.     public List<Node> getChildren(){
  11. return children;
  12.     }
  13.    
  14.     @Override public int size(){
  15. int size = 1;
  16. for(Node n : children){
  17.    
  18.     size += n.size();
  19. }
  20. return size;
  21.     }
  22.    
  23.     @Override public boolean contains(int i){
  24. if(getData() == i)
  25.     return true;
  26. boolean ret = false;
  27. int j = 0;
  28. while(!ret && j < children.size()){
  29.     ret = children.get(j++).contains(i);
  30. }
  31. return ret;
  32.     }
  33.    
  34.     @Override public String toString(){
  35. StringBuilder sb = new StringBuilder();
  36. sb.append(getData()).append(" " ).append(children.toString());
  37. return sb.toString();
  38.     }
  39.    
  40.     @Override public boolean equals(Object o){
  41. boolean ret = false;
  42. if(!(o instanceof InternalNode))
  43.     return ret;
  44. InternalNode n = (InternalNode)o;
  45. return (getData() == n.getData() && children.equals(n.children));
  46.     }
  47. }


 
 

Code :
  1. import java.util.*;
  2. public class Tree {
  3.     private final Node root;
  4.    
  5.     public Tree(Node root){
  6. this.root = root;
  7.     }
  8.     public String toString() {
  9. return root.toString();
  10.     }
  11.    
  12.     public int size() {
  13. return root.size();
  14.     }
  15.    
  16.     public boolean contains(int i) {
  17. return root.contains(i);
  18.     } 
  19.    
  20.     public boolean equals(Object o) {
  21. return root.equals(o);
  22.     } 
  23. }


 
 

Code :
  1. import java.util.*;
  2. public class Main{
  3.     public static void main(String [] args){
  4. List<Node> listThree = new ArrayList<Node>();
  5. listThree.add(new Leaf(5));
  6. listThree.add(new Leaf(6));
  7. List<Node> listOne = new LinkedList<Node>();
  8. listOne.add(new Leaf(2));
  9. listOne.add(new InternalNode(3, listThree));
  10. listOne.add(new Leaf(4));
  11. Node one = new InternalNode(1, listOne);
  12. Tree tree = new Tree(one);
  13. List<Node> listThree2 = new ArrayList<Node>();
  14. listThree2.add(new Leaf(9));
  15. listThree2.add(new Leaf(6));
  16. List<Node> listOne2 = new LinkedList<Node>();
  17. listOne2.add(new Leaf(2));
  18. listOne2.add(new InternalNode(3, listThree2));
  19. listOne2.add(new Leaf(4));
  20. Node one2 = new InternalNode(1, listOne2);
  21. Tree tree2 = new Tree(one2);
  22. System.out.println(one.size());
  23. System.out.println(one.contains(6));
  24. System.out.println(one);
  25. System.out.println(one.equals(one2));
  26.     }
  27. }

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

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed