La création d'un java hierarchial treeset à partir d'une liste à plat

J'ai la liste des Objets T, il possède une propriété de parent où les objets de la propriété parent est null. J'ai envie de mettre tous les objets dans un TreeSet (ou TreeMap). Haut niveau les objets seront tous les objets racine qui n'a pas de parent (père, mère, est nulle) et ils ont leurs enfants de moins de.

Quelque chose comme cela

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

Si je peux obtenir de l'Ar et de trouver ses enfants (Ca1, Ca2, Ca11, Ca12....)

Mise à jour:
Désolé peut-être qu'il n'était pas clair, les nœuds point pour les parents et si le parent est null, ils sont des nœuds racine. Le problème est que les parents doivent savoir à ses enfants. Mais la relation est dans la direction opposée.

class Node
{
  private Node parent;
  private String name;
}
Yust le faire ou de poser une question... (Il n'est pas question chez vous "question")
quelle est votre structure de données?

OriginalL'auteur aug70co | 2012-02-27

  1. 11

    Je pense que vous pouvez être confus au sujet de ce qu'est un TreeSet n'en Java. Un TreeSet est simplement une mise en œuvre de la Set interface, qui utilise un arbre à l'interne. De même pour TreeMap. Il n'est pas d'un usage général, la structure en arborescence qui vous permet de traverser des parents aux enfants. Le fait qu'il utilise des arbres est strictement un détail de l'implémentation interne.

    Je comprends que vous avez un tas d'objets, dont chacun a une référence à un "parent" de l'objet. Ces "parent" liens forme d'un arbre, mais vous voulez traverser des parents aux enfants, et non pas la direction opposée (ce qui serait facile).

    Dans ce cas, je serais probablement marcher au-dessus de la liste des objets et de construire un Map du parent de l'objet à List des enfants. Quelque chose comme:

    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);
  }
}
    avez-vous oublié d'associer les racines avec l'arborescence?
    Pas de. Chaque racine est un arbre de son propre. Vous pouvez parcourir tous les nœuds de départ de la roots.
    ce qui se passe quand le premier indice de la boucle était l'enfant?
    Je ne comprends pas ce que tu veux dire. Pouvez-vous donner un exemple qui le rend plus clair?

    OriginalL'auteur Alex D

  2. 1

    Voici la solution je viens avec

    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.
    Si tout ce que vous voulez, c'est de voir les enfants d'un nœud, alors vous n'avez pas besoin d'ajouter du nœud dans un ensemble trié avant de les ajouter. Quel est le but de trier les nœuds?
    Vrai, mais cet ensemble contribue à la préservation de l'ordre
    Si vous souhaitez préserver l'ordre des nœuds enfants, alors vous pouvez faire votre Map être de type Map<Node, Set<Node>> et vous épargner un scan complet de votre nodeList.

    OriginalL'auteur aug70co