Good programming practices

Generating tree from two-dimensional array

February 24th, 2011

Suppose we have an arrays, which contain hierarchically ordered elements. It should be easier to operate if it would be a tree.
In other words, we want to transform a matrix, for example:

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



to tree:

Root
 b
  r
  n
   l
 a
  f
   w
   d
    s
  p



An arrays, which have equal elements in the same index, become “stapled” and common branch is created.
Below is the algorithm and example code. Classes use generics, so you can use it easily for any kind of data. In this example it is just 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

You must be logged in to post a comment.