java - 将具有多个值的地图转换为树？

Question

给定一组随机分布的键，每个键映射到一组值，如何将其转换为多棵树？

示例数据集

• 注意₂ => {NC ₂ ND ₂ }
  
• ND ₁ => {NG ₁ NH ₁ }
  
• NA ₁ => {NB ₁ }
• 注意₁ => {NC ₁ ND ₁ NE ₁ }
  
• NA ₂ => {NB ₂ }
  
• NC ₁ => {NF ₁ }
  
• 东北₁ => {NI ₁新泽西₁ NK ₁ }
  

NA _{1的结果树}

NA 1 
`-- NB 1 
    |-- NC 1 
    | `-- NF 1 
    |-- ND 1 
    | |-- NG 1 
    | `-- NH 1 
    `-- NE 1 
        |-- NI 1 
        |-- NJ 1 
        `-- NK 1

NA _{2的结果树}

NA 2 
`-- NB 2 
    |-- NC 2 
    `-- ND 2

Answer 1

我不知道有任何库方法可以进行这种转换。这就是我的做法。这很简单，IMO。

public class Tree {
    public Tree(String key) {
        // ...
    }
    public void addChild(Tree child) {
        // ...
    }
}

public Set<Tree> transform(Map<String, List<String>> input) {
    // Potential tree roots.  We start with all LHS keys as potential roots,
    // and eliminate them when we see their keys on the RHS.
    Set<String> roots = new HashSet<String>(input.keySet());

    // This map associates keys with the tree nodes that we create for them
    Map<String, Tree> map = new HashMap<String, Tree>();

    for (Map.Entry<String, List<String>> entry : input.entrySet()) {
        String key = entry.getKey();
        List<String> childKeys = entry.getValue();
        Tree tree = map.get(key);
        if (tree == null) {
            tree = new Tree(key);
            map.put(key, tree);
        }
        for (String childKey : childKeys) {
            roots.remove(childKey);
            Tree child = map.get(childKey);
            if (child == null) {
                child = new Tree(childKey);
                map.put(childKey, child);
            }
            tree.addChild(child);
        }
    }
    Set<Tree> res = new HashSet<Tree>(roots.size());
    for (String key : roots) {
        res.add(map.get(key));
    }
    return res;
}

编辑：请注意，如果输入表示一组 DAG（有向无环图），则此算法将“起作用”。但是，我刚刚意识到生成的一组树将为输入数据中的任何公共子树共享 TreeNode 实例。

请注意，我还没有调试过这段代码:-)

Answer 2

当您谈论将它们转换为一组树时，您是在谈论在内存中表示它们的方法吗？

或者也许是我们将遍历您的一组键和值并将它们放入内存表示中的算法？

还是您在谈论图形表示？