Recursion in Java: Question for those who understand recursion well.

Recursion in Java: Question for those who understand recursion well.

Post by success_n » Sun, 28 Aug 2005 08:10:20


I have a tree represented as a linked list of simple objects
(nodeId/parentId pairs) where the root node is the 1st element in the
list. The other nodes are in somewhat random order. The parentId refers
to the parent node.

I want to convert it into a list where the values are in pre-order.
I.e., I want to get this list as follows: ABCDEFGHIJ (see graph below).
I.e., get the 1st node, put in in the list. If it has children, go
through them one by one, get their child nodes, then put the parent in
the list, then the leftmost first, and go from there. I.e., so that
it's ordered in my linked list like this by (letters represent nodeId):


A
/ \
B J
/ | \
C H I
|
D
/|\
E F G

I created the following recursive method but it does not work
correctly. For example, it places the nodes A then B and then J into
the list first, rather than getting to J after adding all the child
nodes. "isOnTheList" checkes whether the item is already in the list.
"getImmediateChildren" returns the list of immediate child nodes
ordered by nodeId

Note: the empty list is passed to the method and is populated with the
result:

public static void orderTree(List list, List treeList) {
if(treeList == null || treeList.size() == 0)
return;

Node child = null; List children = null;

for(int i = 0; i < treeList.size(); i++) {
node = (Node) treeList.get(i);
// get list of children for this node
children = getImmediateChildren(node, treeList);

// if the node is not yet on the list, add it
if(! isOnTheList(node, list) )
list.add(cat);

// if it has children, recurse to add all other nodes
if(children.size() > 0) {
orderTree(list, children);
}
}
}

Any idea what the problem is?

Thanks.
 
 
 

Recursion in Java: Question for those who understand recursion well.

Post by CBFalcone » Sun, 28 Aug 2005 16:34:37


... snip code ...

No he isn't. What he has shown is not a binary tree. Even if it
was, he would want an inorder traversal. He neglected to show the
declarations for the actual tree.

For help, the OP should post a complete compilable minimized
program.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

 
 
 

Recursion in Java: Question for those who understand recursion well.

Post by Rob Thorp » Mon, 29 Aug 2005 19:51:21


Is this cast really necessary?


As CBFalconer said, show the smallest compilable program you can. From
reading the above I can't see any obvious mistakes, so long as each
node contains a list and all the functions work as they should. The
tree should flatten.

Try going though it in a de *** , or printing out the nodes as they're
processed.
 
 
 

Recursion in Java: Question for those who understand recursion well.

Post by googmeiste » Mon, 29 Aug 2005 23:52:07


Given the example tree, the OP does want a preorder
traveral (with the usual convention that you visit the
children from left to right), but not necessarily of a
binary tree.