从平面列表创建Java层次结构树集

Question

我有Objects T的列表,它有一个parent的属性,其中top对象的parent属性为null.我想将所有对象放入TreeSet(或TreeMap)中.顶级对象将是没有父级的所有根对象(父级为null),并且他们的子级将在其下.

像这样的东西

              o
           /  |   \
          Ra  Rb   Rc          -- Level Root Objects
         / |   \    | \
        Ca1 Ca2 Cb1 Cc1 Cc2    -- Level of First Children
     /   \
   Ca11   Ca12..............   -- Level of Second Children

所以我可以得到Ra并找到它的孩子(Ca1,Ca2,Ca11,Ca12 ....)

更新:抱歉,可能是不清楚,节点指向父节点,如果父节点为空,则它们是根节点.问题是父母需要了解自己的孩子.但这种关系是相反的.

class Node
{
  private Node parent;
  private String name;
} 

Answer 1

我想您可能不清楚TreeSetJava中的功能.A TreeSet只是Set接口的一种实现,它在内部使用树.同样地TreeMap.它不是一个通用树结构,允许您从父母到孩子.它使用树的事实严格地说是内部实现的细节.

我知道你有一堆对象,每个对象都有一个"父"对象的引用.那些"父"链接形成一棵树,但你想从父母到孩子,而不是相反的方向(这很容易).

在这种情况下,我可能会遍历对象列表并构建一个Map从父对象到子对象List.就像是:

Map<Node,List<Node>> tree  = new HashMap<Node,ArrayList<Node>>();
List<Node>           roots = new ArrayList<Node>();
for(Node n : nodes) {
  if(n.parent == null)
    roots.add(n);
  else {
    if(!tree.containsKey(n.parent))
      tree.put(n.parent, new ArrayList<Node>());
    tree.get(n.parent).add(n);
  }
}

Answer 2

这是我想出的解决方案

SortedSet<Node> nodeSet = new TreeSet<Node>(new Comparator<Node>() {
    public int compare(Node node1, Node node2) {

        if (node1.getParent() == null) {
            if (node2.getParent() == null) {
                return  node1.getId().compareTo(node2.getId());
            }
            return -1;
        }

        if (node2.getParent() == null) return 1;

        int parentCompare = node1.getParent().getId()
                .compareTo(node2.getParent().getId());

        if (parentCompare == 0)
            return node1.getId().compareTo(node2.getId());

        return parentCompare;
    }
});

nodeSet.addAll(allData); // allData is the Node list


Map<Node, List<Node>> map = new HashMap<Node, List<Node>>();

for(Node node : nodeSet)
{
    if(map.get(node)==null)
    {
        map.put(node, new ArrayList<Node>());
    }
    map.get(node).add(node);
    Node parentNode = node.getParent();
    while(parentNode!=null)
    {
        map.get(parentNode).add(node);
        parentNode = parentNode.getParent();
    }
}

// At this point I can get an element from map and see all children in values.