Sign in to follow this  
Enerjak

LITTLE help returning nodes recursively....

Recommended Posts

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

[CODE]
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;
}
[/CODE]

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:

[CODE]
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());
}
[/CODE]

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

Share this post


Link to post
Share on other sites
Maybe you should try to comment and explain your code a little, because frankly, I have no idea what you are even trying to do there.

You have two places where you say a=b, b=a which seems pointless as the second line would be like saying b=b.

Your function is taking a parameter id and completely ignores it, so what is the point in calling it three times with a different parameter that doesn't do anything?

You have a recursive call and completely ignore the return value. On top of that, you call it on the same node itself.

Your recursion has no apparent condition to ever abort. How does it ever return instead of just going on until you run out of memory?

Share this post


Link to post
Share on other sites
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:

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

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

Share this post


Link to post
Share on other sites
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.

[code]
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;
}

}
[/code]

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.

[code]
public class Node {

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

}
[/code]

If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a [i]collection[/i] 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.

[code]
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 );
}
}

}
[/code]

The above solution adds the current child behind the children of the current child, and hence does a [url="http://en.wikipedia.org/wiki/Depth-first_search"]deep-first[/url] traversal.


/* all code above is untested */ Edited by haegarr

Share this post


Link to post
Share on other sites
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:

[code]
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));
}
}[/code]

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this