java - 用字符串列表构造一棵树并计数

Question

我有一个 Map<List<String>,Integer>其中每个条目都是一个路径(List<String>)和一个计数

例如:

["a1", "a2", "a3"] => 4
["a1", "a2"] => 2
["b1", "b2", "b3"] => 3
["b1"] => 4
["b1", "b2"] => 3
["c1", "c2", "c3", "c4"] => 5

我想为每个节点输出一个计数的树

树:

- ROOT
-- a1 : 6
--- a2 : 6
---- a3 : 4
-- b1 : 7
--- b2 : 3
-- c1 : 5
--- c2 : 5
---- c3 : 5
----- c4 : 5

JSON 结构:

{
    "name": "",
    "count": "",
    "children": [
        {
            "name": "",
            "count": "",
            "children": []
        }
    ]
}

什么是最有效的数据结构，然后在这种情况下如何使用它(然后应该将树序列化为 JSON 树)？

Answer 1

我会使用节点创建树结构，然后使用 XStream 序列化该结构。下面举例，希望对你有帮助。

转换为节点结构

public static Node createNodes(Map<List<String>, Integer> map) {
    Map<String, Node> namemap = new HashMap<String, Node>();
    Node root = new Node();
    Node current;
    for (Entry<List<String>, Integer> path : map.entrySet()) {
        current = root;
        for (String nodename : path.getKey()) {
            Node p;
            if (!namemap.containsKey(nodename)){
                p = new Node(nodename, path.getValue());
                namemap.put(nodename, p);
            }else {
                p = namemap.get(nodename);
                p.addCost(path.getValue());
            }
            current.addChild(p);
            current = p;
        }

    }

    return root;
}

序列化

public static String toXML(Node n) {
    XStream xstream = new XStream(new JsonHierarchicalStreamDriver());
    xstream.alias("node", Node.class);
    return xstream.toXML(n);
}

节点对象

public class Node {

    private String name;
    private int count;
    private List<Node> children;

    public Node() {
        this(null, 0);
    }

    public Node(String name, int count) {
        this.name = name; 
        this.count = count;
        this.children = new ArrayList<Node>();
    }


    public void addChild(Node n) {
        for (Node nn : children) {
            if (nn.name.equals(n.name)) {
                return;
            }
        }
        this.children.add(n);
    }

    public void addCost(int i) {
        this.count += i;
    }
}

JSON 输出

{"node": {
  "count": 0,
  "children": [
    {
      "name": "c1",
      "count": 5,
      "children": [
        {
          "name": "c2",
          "count": 5,
          "children": [
            {
              "name": "c3",
              "count": 5,
              "children": [
                {
                  "name": "c4",
                  "count": 5,
                  "children": [
                  ]
                }
              ]
            }
          ]
        }
      ]
    },
    {
      "name": "b1",
      "count": 10,
      "children": [
        {
          "name": "b2",
          "count": 6,
          "children": [
            {
              "name": "b3",
              "count": 3,
              "children": [
              ]
            }
          ]
        }
      ]
    },
    {
      "name": "a1",
      "count": 6,
      "children": [
        {
          "name": "a2",
          "count": 6,
          "children": [
            {
              "name": "a3",
              "count": 4,
              "children": [
              ]
            }
          ]
        }
      ]
    }
  ]
}}