Parcours n-Tree du nœud racine à tous les enfants

Question

J'ai une liste avec des tables d'une base de données où chaque ligne contient un champ parent se référant à une autre ligne. Comme cette

A

titre, parent
A, null
B, C, A
D, C
E, B
F, null

Ici A et F sont des nœuds racines, B et C sont enfants de A, D est enfant de C et E est enfant de B à son tour.

Quelle est la meilleure façon de produire une structure arborescente à partir de cette liste? L'une des façons consiste à parcourir de nouveau la liste en recherchant la racine (le titre sans parents) puis, pour chaque racine, bouclez à nouveau la liste et attachez les nœuds racines. Ensuite, pour ces nœuds, bouclez à nouveau la liste complète pour attacher les enfants qui leur sont propres.

Exemple:

private Node getNode(SomeData d) { 
    List<SomeData> tmp = getChildren(d); 
    if (tmp == null OR empty) return new Node(d); 

    Node n = new Node(d); 
    for (SomeData m : tmp) { 
     n.addChild(getNode(m)); // recurse 
    } 
    return n; 
} 

private List<SomeData> getChildren(SomeData parent) { 
    List<SomeData> tmp = new ArrayList<SomeData>(); 
    for (SomeData candidateChild : myBigFlatDataList.values()) { 
     if (parent.equals(candidateChild)) { 
      tmp.add(candidateChild); 
     } 
    } 
    return tmp; 
} 

Y at-il une meilleure façon de le faire?

Answer 1

C'est un très bon moyen, mais il est plus naïf que nécessaire.

Un autre itinéraire prend juste un temps linéaire. Y a-t-il quelque chose à propos d'une SomeData qui l'identifie de manière unique? Je suppose que oui; cela pourrait être SomeData implémentant lui-même equals() et hashCode() correctement.

Disons qu'il existe une méthode int SomeData.getID(). Ensuite, nous pouvons garder les nœuds que nous avons déjà vu dans un HashMap.

Map<Integer, Node> visitedNodes = new HashMap... 

Puis nous venons de lire en avant à travers les lignes:

for (SomeData data : ...) { 
    SomeData parent = data.getParent(); 
    Node<SomeData> parentNode = getOrCreateNode(parent); 
    Node<SomeData> childNode = getOrCreateNode(data); 
    parentNode.addChild(childNode); 
} 

private Node<SomeData> getOrCreateNode(SomeData data) { 
    Node<SomeData> node = visitedNodes.get(data.getID()); 
    if (node == null) { 
     node = new Node<SomeData>(data); 
     visitedNodes.put(data.getID(), node); 
    } 
    return node; 
} 

Answer 2

Étant donné que vous obtenez les données d'un DB, vous pouvez trier les lignes en fonction de l'attribut parent. Ensuite, vous n'aurez pas besoin de parcourir toute la liste à chaque fois que vous recherchez les enfants d'un nœud. Lorsque la liste est triée, vous pouvez arrêter l'itération sur la liste lorsque vous avez trouvé tous les enfants que vous recherchiez. Par exemple, lorsque vous avez la racine « A » et de commencer à chercher ses enfants dans cette liste:

B, A 
C, A 
E, B <- when you reach "B" you can assume that there are no 
D, C  other nodes which are children of "A" and stop the iteration 

Answer 3

Relire le fichier entier (ou pire interrogation de la base) pour chaque nœud est assez cher. Je préférerais que vous construisiez l'arbre en lisant la liste. Voici mes 2 cents

1. Soit des nœuds un ensemble de nœuds (initialement un jeu vide).
2. Laisser RootNodes être un ensemble de tous les nœuds racines (initialement un ensemble vide).
3. Pour chaque paire de noeuds (N1, N2):
   
   1. Pour chaque N dans (N1, N2) si N pas dans les nœuds, créer N et insérer dans les nœuds.
   2. Si N2 == null, insérez également N2 dans RootNodes (vous pouvez également le supprimer des nœuds)
   3. Mark N2.child = N1.

Si vous suivez ce, à la fin de l'itération sur la liste, vous devriez avoir:

RootNodes = {A,F} 
Nodes = {B,C,D,E} 

A.child = B 
A.child = C 
C.child = D 
B.child = E 

Hope this helps.

Answer 4

Vous pouvez construire votre arbre en une fois.Vous pouvez faire un premier passage sur la table pour construire tous les nœuds (construire une hashtable du nom au nœud), puis faire un autre passage où vous pouvez ajouter des relations parent-enfant entre deux nœuds (ajouter un parent à enfant et ajouter un enfant liste des enfants dans le parent).

Answer 5

List<User> list = new ArrayList<User>(); 
User blankNode; 
class User{ 
    String userid;  
    User child;  
    public User() { 
     //blankNode 
    } 
    public User(String userid) { 
     this.userid = userid; 
    } 
    @Override 
    public int hashCode(){ 
     return userid.hashCode(); 
    } 
} 
public void addUser(User parent,String userid){ 
    if(null == userid)return; 
    User child = new User(userid); 
    parent.child = child; 
    list.add(child);   
} 
public void removeUser(User child){ 
    if(null == child)return;   
    list.remove(child); 
} 
/* move the rank to up - assume 
* secParent - assign to new child 
*/ 
public void boubbleUp(User secParent, User oldParent, User child){ 
    if(null == child || null == secParent)return; 
    secParent.child = child; 
    oldParent.child = null; 
} 
public List<User> getTopUser(int num){ 
    if(num <1)return null; 
    Map<Integer, List<User>> map = new HashMap<Integer, List<User>>(); 
    for(User usr : list){ 
     int count =0; 
     User temp = usr.child; 
     while(null != temp){ 
      count++;temp=temp.child; 
     }   
     if(map.get(count)== null){ 
      List<User> sameNoOfChildren = new ArrayList<User>() ; 
      sameNoOfChildren.add(usr); 
      map.put(count, sameNoOfChildren); 
     }else{ 
      map.get(count).add(usr);     
     } 
    } 
    Integer[] arr = (Integer[]) map.keySet().toArray(); 
    Arrays.sort(arr); 
    List<User> result = new ArrayList<User>(); 
    for(int i = arr.length-1; i <=arr.length-num; i--){ 
     result.addAll(map.get(i)); 
    }  
    return result;  
}