nœuds Parse dans une structure arborescente Java vecteur de chaînes

Question

J'ai une structure de données qui ressemble à ceci

private String name; 
private ArrayList<Node> children; 
private String parent=""; 

public Node(String name) { 
setName(name); 
children = new ArrayList<Node>(); 
} 

Ailleurs dans mon programme, j'ai un nœud appelé « racine » qui contient une structure de données d'arbre entier .

Conceptuellement, il ressemble à ceci

         root 
            / \ 
            /  \ 
            node1  node2 
           /   \ 
           /   \ 
           node2   node3 
           /
          /
          node3 

Comme vous pouvez le voir nœuds peuvent avoir le même nom. C'est prévu. Je veux créer une chaîne pour chaque noeud qui contient son propre nom, plus son lignage et les stocker dans un vecteur.

donc noeud 3 sur le côté gauche serait "root|node1|node2|node3" la node3 sur les rhs serait "root|node2|node3" node1 serait "root|node1" etc.

J'ai un moyen de parcourir la structure de noeud pour imprimer chaque noeud, mais je Je trouve difficile de définir tous les parents, car je n'arrive pas à trouver un moyen de le faire. Toute aide serait fantastique car tout ce que j'ai essayé jusqu'ici a échoué. Une note importante est que l'arbre n'est pas nécessairement un arbre binaire, je l'utilise juste pour un exemple.

Voici le code que j'utilise pour imprimer chaque nœud de l'arbre. Espérons que ce sera facile à modifier.

public void print() { 
     LinkedList<Node> open = new LinkedList<Node>(); 
     LinkedList<Node> closed = new LinkedList<Node>(); 

     open.add(this); 

     while(!open.isEmpty()) { 
      Node currentNode = open.removeFirst(); 
      System.out.println(currentNode.getName()); 

      ArrayList<Node> children = currentNode.getChildren(); 
      closed.add(currentNode); 

      for(int i = 0; i < children.size(); i++) { 
       Node current = children.get(i); 
       open.addLast(current); 
      } 
     } 
    } 

Merci les gars.

Answer 1

Il semble qu'il serait plus facile d'ajouter le parent lors de la construction de l'arbre mais si vous avez construit l'arbre et que vous voulez ajouter un parent à chaque nœud, vous pouvez utiliser la récursivité. Je vais essayer quelque chose comme

addParent(root, ""); 

public void addParent(Node node, String parent) { 
    node.setParent(parent); 

    // if this node has children iterate through them 
    // and call addParent with current node name. 
    for(Node childNode : node.getChildren()) { 
     addParent(childNode, node.getName()); 
    } 
} 

NOTE: Je n'ai pas pu tester ce code avant de poster.

Answer 2

Je suppose que vous avez déjà créé ces noeuds et qu'ils ont été créés avec des enfants mais sans le parent? On dirait que il y a quelques options:

1. Lors de la création des enfants, définissez le parent (je pense que vous n'avez pas vraiment le contrôle sur cela parce que vous posez cette question) si ...
2. lieu d'un vecteur peut-être utiliser un type de carte où vous pouvez définir la clé comme la lignée. Ensuite, lorsque vous itérez sur les noeuds, faites une modification de chaîne pour supprimer le nom du noeud actuel et vous êtes laissé avec la lignée parent. Relativement à # 2, n'utilisez pas de Map (et gardez le Vector) et faites toujours la manipulation de la chaîne, mais vous devrez alors itérer chaque nœud du Vector pour chercher le parent par son lignage.

Hope this helps et je l'espère, je suppose correctement -Dave