Создание иерархического набора java из плоского списка

Question

У меня есть список объектов T, у него есть свойство parent, где родительское свойство верхних объектов равно nullЯ хочу поместить все объекты в TreeSet (или TreeMap).Объектами верхнего уровня будут все корневые объекты, у которых нет родителя (parent равен 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 ....)

Обновление: извините, может быть, это не ясно, узлы указывают на родителей, и если parent равен null, они являются корневыми узлами.Проблема в том, что родители должны знать своих детей.Но отношения в противоположном направлении.

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

Answer 1

Я думаю, что вам может быть неясно, что TreeSet делает в Java. 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.