java - 如何从二维数组生成树

Question

我想从数组（如字符串）生成树，但我不知道该怎么做。

我输入数组：

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

我要让这样的树：

Root 
b 
    r 
    n 
    l 
a 
    f 
    w 
    d 
    s 
    p 

这是我到目前为止的代码：

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

Answer 1

你的代码是有点混乱，你应该最明确地不要在Node的构造函数中递归地创建整个结构。所以，我提供了一些伪

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) 

虽然这种形式表示的是相当低效而且会产生巨大的数额更大的平衡树数据。