Jump to content

  • Log In with Google      Sign In   
  • Create Account

LITTLE help returning nodes recursively....


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 27 April 2012 - 09:08 PM

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?

Sponsor:

#2 Trienco   Crossbones+   -  Reputation: 2171

Like
0Likes
Like

Posted 27 April 2012 - 10:14 PM

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?
f@dzhttp://festini.device-zero.de

#3 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 27 April 2012 - 11:10 PM

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

#4 haegarr   Crossbones+   -  Reputation: 4310

Like
0Likes
Like

Posted 28 April 2012 - 02:54 AM

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 */

Edited by haegarr, 29 April 2012 - 03:08 AM.


#5 Enerjak   Members   -  Reputation: 233

Like
0Likes
Like

Posted 28 April 2012 - 05:27 AM

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

#6 Dragonsoulj   Crossbones+   -  Reputation: 2111

Like
0Likes
Like

Posted 28 April 2012 - 09:46 AM

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).




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS