Creating a hierarchical tree of Java trees from a flat list

Question

I have a list of T objects, it has a parent property, where the parent property of top objects is null. I want to put all the objects in a TreeSet (or TreeMap). Top-level objects will be all root objects that do not have a parent (the parent object is null), and they will have their children under them.

Something like that

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

So I can get Ra and find his children (Ca1, Ca2, Ca11, Ca12 ....)

Update: Sorry, it may have been unclear, the nodes point to the parents, and if the parent is null, they are the root nodes. The problem is that parents need to know their children. But relations are in the opposite direction.

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

Answer 1

Here is the solution I came up with

 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. 

Answer 2

I think you may not understand what TreeSet does in Java. A TreeSet is just an implementation of the Set interface, which uses the tree within itself. Similarly for TreeMap . This is not a general tree structure that allows you to move from parents to children. The fact that he uses trees is a strictly internal implementation.

I understand that you have a bunch of objects, each of which has a link to a "parent" object. These "parent" links form a tree, but you want to switch from parents to children, and not in the opposite direction (which would be easy).

In this case, I will probably go through the list of objects and build a Map from the parent object to the List for children. Sort of:

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