Parse Nodes in a Java Tree Structure in Vector of Strings

I have a data structure that looks like t开发者_StackOverflow社区his

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

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

Elsewhere in my program, I have a Node called "root" that contains an entire tree data structure.

Conceptually it looks like this

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

As you can see nodes can have the same name. That's intended. I want to create a string for each node that contains its own name, plus it's lineage and store them in a Vector.

so node 3 on the left hand side would be "root|node1|node2|node3" the node3 on the rhs would be "root|node2|node3" node1 would be "root|node1"etc.

I have a way to iterate through the node structure to print each node, but I'm finding it difficult to set every parent, as in, I can't figure out a way to do it. Any help would be fantastic as everything I've tried so far has failed. One important note is that the tree may not necessarily be a Binary tree, I'm just using it for an example.

Here's the code I use for printing every node of the tree. Hopefully it will be easy to tweak.

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

Thanks guys.

---

I'm assuming that you already have these nodes created and they were created with children but without the parent? Seems like there are a few options:

1. When creating the children, set the parent (I would think you don't really have control over this because you are asking this question) so...
2. Instead of a Vector maybe use some type of Map where you can set the key as the lineage. Then when you iterate over the nodes do some string tweaking to remove the current node's name and you are left with the parent lineage.
3. Related to #2, don't use a Map (and keep the Vector) and still do the string manipulation but you would then have to iterate every node in the Vector to look for the parent by its lineage.

Hope this helps and hopefully I assumed correctly -Dave

---

it seems that it would be easier to add the parent as you are building the tree but if you have the tree built and want to add a parent to each node you can use recursion. I'd try something like

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: I was not able to test this code before posting.