-
recursion
Hi,
I have a simple tree and I just want to print the parent id and the child ids using recursion. I have somthing like this.
2
/ \
3 4
/ \ / \
5 6 7 8
/\ /\ /\ /\
9 10 11 12 13 14 15 16
I want to traverse it like this
2 3 5 9 10 6 11 12 4 7 13 14 8 15 16.
I wrote simple recursion. the full program si provided at http://pastebin.ca/1354550. Just to illustrate the recrusion (If u happen to look at code dont messed up with the fill method, I am using this to simply my problem using in my project)
Code:
int order_display(long fid, long tid)
{
fot = FOST.find(fid);
if(fot != FOST.end())
{
int r = 0;
for(FOT.t = FOT.tids.begin();
FOT.t != FOT.tids.end();
FOT.t++)
{
fot1 = FOST1.find(*FOT.t);
if(fot1 != FOST1.end())
{
cout<<"tid "<<*FOT.t<<", creates family "<<FOT1<<endl;
//recursion
order_display(FOT1, *FOT.t);
}
else
{
cout<<"tid == "<<*FOT.t<<endl;
}
}
//return 1;
}
}
Can you please identify what is the problem. Coz I go till 2 3 5 8 9. But it does not go to the other family on the next to the lowest level. Any help will be appreciated.
i.
-
I didn't look at your pastebin code, but looking at your tree:
(1) this is a bog standard pre-order traversal
(2) since this is a binary tree, each node should have two children, so you should be making two recursive calls
(3) unless you have a forest of binary trees, why would you want to use a for loop for this?
-
Those last two questions / points are explained by the fact that a tail-recursive call can be translated into iteration (i.e. a loop) instead. When there are two recursive calls, then obviously only at most one of those can be tail-recursive.
Thus you would have one loop and one recursive call. Hence my own in-order tree processing function:
Code:
template <class TNode>
void InorderProcess(TNode *head, void ProcessItem(TNode *item)) {
while (head != NULL) {
InorderProcess(head->left, ProcessItem);
ProcessItem(head);
head = head->right;
}
}
The advantage is that a tree with a huge number of items that has degraded to a list following the right pointers doesn't blow the stack. Of course a list following the left pointers still does. It's also probably faster, assuming the compiler doesn't perform the same optimisation on its own, since it uses less stack space.
The OP's code is difficlut to understand because it contains non-descriptive names like fid, tid, tids, fot, FOT, fot1, FOST, FOST1, and an unused variable r.
mirfanud, before anyone else helps you, how about you help yourself by using proper variable names.
-
I guess ++ could mean "follow the right child", since technically it can mean anything, although to be honest that hadn't occurred to me. But if OP says all he gets is 2 3 5 9, that suggests to me that the left calls are being made and the right calls aren't.
-
Looking deeper into this, it appears that the way the author has chosen to represent a tree is to store the parent/children relationship in a map. The parent is the .first, and the .second is a list of the children. Finding each nodes children is a simple matter of using .find(). Although the diargam shows a binary tree, the author has not specified that it is merely a binary tree, and the code supports it being an n-ary tree. It's kind of ironic when you consider that a std::map is basically a tree in itself anyway.
Anyway, this is what actually explains the single recursive call in this case.
Next time it would help to provide this description up front.
I do think that this implementation is particularly nasty though. If it is meant to represent a binary tree then there are far better ways of representing it. The iterator 't' should not be a member of the struct. It should instead be a local variable.
Apart from needlessly calling .find() both before AND after each recursive call, the code itself looks at a glance like it would work.