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