Dobre praktyki programistyczne

Generowanie struktury drzewa z tablic

24.02.2011

Załóżmy, że mamy tablice zawierające elementy w hierarchicznej kolejności. Na takim zbiorze łatwiej operować, jeśli ma strukturę drzewa.

Innymi słowy, chcemy przekształcić macierz, np.:

[a, f, d, s]
[a, f, w]
[b, r]
[a, p]
[b, n, l]


na drzewo:

Root
 b
  r
  n
   l
 a
  f
   w
   d
    s
  p


Tablice, które mają wspólny taki sam element na danej pozycji, są w tym miejscu „spinane” i tworzy się wspólna gałąź.

Poniżej umieszczam kod, który to dokonuje, wraz z przykładem. Kod korzysta z typów generycznych, dzięki czemu można go łatwo wykorzystać do operowania na różnych typach danych. W przykładzie jest to klasa String.

  1. package treegenerator;
  2.  
  3. import java.util.Arrays;
  4. import java.util.HashSet;
  5. import java.util.List;
  6. import java.util.Set;
  7.  
  8. /**
  9.  * Generates tree structure from arrays.
  10.  *
  11.  * @author Łukasz Sutkowski
  12.  * @param Class of tree leafs
  13.  */
  14. public class TreeGenerator {
  15. public TreeGenerator(E root, E[][] array){
  16. List list = Arrays.asList(array);//makes list
  17. Set set = new HashSet(list);//then set
  18. Node tree = new Node(root, set, 0);//makes whole tree
  19.  
  20. System.out.println(tree.toString());//displays tree
  21. }
  22.  
  23. public static void main(String[] args) {
  24. String[][] array = new String[][] { { "a", "f", "d", "s" }, { "a", "f", "w" }, { "b", "r" }, { "a", "p" }, { "b", "n", "l" } };
  25. for(String[] s : array){
  26. System.out.println(Arrays.toString(s));
  27. }
  28. new TreeGenerator("Root", array);
  29. }
  30. }

Node.java   
  1. package treegenerator;
  2.  
  3. import java.util.HashMap;
  4. import java.util.HashSet;
  5. import java.util.Map;
  6. import java.util.Set;
  7.  
  8. /**
  9.  * Subset of tree. It can be whole tree, a branch or a leaf.
  10.  *
  11.  * @author Łukasz Sutkowski
  12.  * @param Class of tree leafs
  13.  */
  14. public class Node {
  15. private final E nodeName;
  16. private final Node[] children;
  17. private final int depth;
  18.  
  19. /**
  20.   * Constructs a Node and its children.
  21.   *
  22.   * @param name Node name
  23.   * @param array Set of arrays
  24.   * @param depth Index of arrays
  25.   */
  26. public Node(E name, Set array, int depth) {
  27. nodeName = name;
  28. this.depth = depth;
  29. Map map = new HashMap();
  30.  
  31. for (E[] line : array) { //iterates over arrays
  32. if (line.length > depth) { //checks if an element exists at this depth
  33. E common = line[depth]; //gets an element
  34. Set branch = map.get(common); //gets a branch for the element
  35. if (branch == null) { //if first such an element
  36. branch = new HashSet(); //creates branch
  37. map.put(common, branch); //adds for the element
  38. }
  39. branch.add(line); //adds the line for proper branch
  40. }
  41. }
  42. children = new Node[map.size()];
  43. int i = 0;
  44. depth++;//gets deeper
  45. for (Map.Entry entry : map.entrySet()) {//iterates over map
  46. children[i] = new Node(entry.getKey(), entry.getValue(), depth);//makes child
  47. i++;
  48. }
  49. }
  50.  
  51. /**
  52.   * Returns a string representation of this node and its children
  53.   *
  54.   * @return string representation
  55.   */
  56. public String toString(){
  57. StringBuilder sb = new StringBuilder();
  58. sb.append('\n');
  59. for(int i=0; i

Leave a Response