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) 

雖然這種形式表示的是相當低效而且會產生巨大的數額更大的平衡樹數據。