OK, i recently decided to practice some tree building techniques before taking on data structures in school (im doing java 2 in the fall so i have time) But i want to at least know the basics...Anyways, my problem is this:

I'm trying to get the number of nodes per node by ID. you know, here's what I have


public Node getChildren(int id)
{
Node retNode = new Node();
if(First != null)
{
retNode = First;
First = retNode;
}
else
{
retNode = last;
last = retNode;

}
getChildren(id);
return retNode;
}


now if i remove the recursive call to getChildren(id) it works but it returns the same node as many times as there are children in the node
so i have this:


Node root = new Node("Root");
Node child = root.addChildToBack("Eggman");
Node Child2 = root.addChildToBack("Sonic");
Node child3 = root.addChildToFront("Tails");
Node child4 = child.addChildToBack("Snively");
Node child5 = Child2.addChildToBack("Sally");

String message = "Root node has: " + root.getChildrenCount() + "\n" +
"Child Node has: " + child.getChildrenCount() + "\n" +
"Child Node 2 has: " + Child2.getChildrenCount() + "\n" +
"Child Node 3 has: " + child3.getChildrenCount() + "\n";

JOptionPane.showMessageDialog(null, message);

for(int x = 0; x < root.getChildrenCount(); x++)
{
Node c = root.getChildren(x);
JOptionPane.showMessageDialog(null, " " + c.getName());
}


now, as u can see it'll get tails 3 times since that's how many children the root has. any advice?

Well, as i said, I'm not really familiar with recursion that well, Basically I want to get all nodes based on the ID of the node like how many children it has. I want to do this recursivly but not sure how to do an abort clause for it, as i tried this:


public Node getChildren(int id)
{
counter = id;
if(counter > 0)
{
if(this != null)
{
return this;
}
else
{
return null;
}
}
return null;
}


I suppose i could just use a vector to add nodes and get them that way, but i want to get them based on how many there are so i can print everything about them.
like root.getChildre(0).getName(), blah blah. if you need anymore please let me know what else i can give

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.


public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 && index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.


public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.


public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
collector.add( currentChild );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.


/* all code above is untested */

thanks i'll keep looking, your advice helped me a lot and i may even do it that way but i'll keep looking.

From what I can tell, and it has been a while dealing with Java, but your for loop where you use getChildrenCount() should be in your getChildren statement. I'll give a shot at offering some pseudo-code mixed with the Java you have:


public Node getChildren(Node parentNode)
{
// You wanted to print the names
JOptionPane.showMessageDialog(null, " " + parentNode.getName());

// Then get the child nodes
// For each child node...
for(int x = 0; x < parentNode.getChildrenCount(); x++)
{
// Here's the recursion. This only gets called when getChildrenCount() is greater than 0, thus it does end at some point.
// This passes the child node at index "x" as the new parent node
getChildren(parentNode.getChildren(x));
}
}

Then replace your whole for loop in the main part of your program with a call to getChildren(root).