java - How to generate Tree from two dimensional array

2.5k views Asked by At

I want to generate a tree from an array(such as String), but I don't know how to do it.

My input array:

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

I want to make a tree like this:

Root 
 b 
  r 
  n 
   l 
 a 
  f
   w 
   d
    s 
  p

This is my code so far:

public class TreeGenerator {
    public TreeGenerator(E root, E[][] array){
        List list = Arrays.asList(array);//makes list
        Set set = new HashSet(list);//then set
        Node tree = new Node(root, set, 0);//makes whole tree

        System.out.println(tree.toString());//displays tree
    }

    public static void main(String[] args) {
        String[][] array = new String[][] { { "a", "f", "d", "s" }, { "a", "f", "w" }, { "b", "r" }, { "a", "p" }, { "b", "n", "l" } };
        for(String[] s : array){
            System.out.println(Arrays.toString(s));
        }
        new TreeGenerator("Root", array);
    }
}






public class Node {
    private final E nodeName;
    private final Node[] children;
    private final int depth; 
    /**
     * Constructs a Node and its children.
     *
     * @param name Node name
     * @param array Set of arrays
     * @param depth Index of arrays
     */
    public Node(E name, Set array, int depth) {
        nodeName = name;
        this.depth = depth;
        Map map = new HashMap();

        for (E[] line : array) { //iterates over arrays
            if (line.length > depth) { //checks if an element exists at this depth
                E common = line[depth]; //gets an element
                Set branch = map.get(common); //gets a branch for the element
                if (branch == null) { //if first such an element
                    branch = new HashSet(); //creates branch
                    map.put(common, branch); //adds for the element
                }
                branch.add(line); //adds the line for proper branch
            }
        }
        children = new Node[map.size()];
        int i = 0;
        depth++;//gets deeper
        for (Map.Entry entry : map.entrySet()) {//iterates over map
            children[i] = new Node(entry.getKey(), entry.getValue(), depth);//makes child
            i++;
        }
    }
}
1

There are 1 answers

0
AudioBubble On

You're code is a bit chaotic and you should most definitly not create the entire structure recursively in the constructor of Node. So i've provided some pseudocode

define generateTree:
    input: string[][] struct
    output: tree

    node root

    //each string[] describes on path from the root to a leaf of the tree
    for string[] s in struct
        node tmp = root

        //complete a path
        for string n in s
            //check whether the next node is already part of the tree
            if hasChild(tmp , n)
                //continue with the next node in the path
                tmp = getChild(tmp , n)
            else
                //next node doesn't exist -> create it first
                node child = new node(n)
                add(tmp , child)
                tmp = child

    return tree(root)

Though this form of representation is rather inefficient and will produce gigantic amounts of data for bigger balanced trees.