Re: binary tree traversal...

[Eric Bambach <eric@cisu.net>]

On Wednesday 26 January 2005 05:01 pm, J. wrote:
> Wednesday, January 26
>
> Hello,
>
> I am trying to traverse a binary tree, returning each node that is
> encounterd so that I can preform operations on that node. However it keeps
> looping over the same first node, it refuses to travel any further down
> the tree ... What did I overlooked ? I know the tree is loaded with data
> since a simple recursive preorder treeprint confirms that.
>
> An example:
>
>  while((root = treerecurse(root)) != NULL)
>   printf("%4d %s\n", root->count, root->word);
>
> And the treerecurse function would look something like:
>
> struct tnode *treerecurse(struct tnode *p) {
>  if(p != NULL) {
>   treerecurse(p->left);
>   return p;
>   treerecurse(p->right);
>  }
> }
>
> I guess there is something wrong in my reasoning about this...

Yea, that definatly wont work. I think you're messing up because a recursive 
function can only pass back the top node, or a node that meets a certain 
condition back up the calling stack, without static data, you cant call a 
recursive function and keep going where it left off so you can only return 
one node.

Why dont you just pass a function pointer into the recursive function so it 
looks like this:(pseudocode, my function pointer syntax is bad)

-------------(pseudo)code--------

treerecurse(root);

//Now you dont need a loop. A single line will now make your function 
//perform on all the nodes.

//And the treerecurse function would look something like:

struct tnode *treerecurse(struct tnode *p,function *dofoo) {
 if(p != NULL) {
  dofoo(p->data);
  treerecurse(p->left);
  return p;
  treerecurse(p->right);
 }
}
---------------end (pseudo)code---------------

If its C++, then its even easier, make tnode a class and define a function 
dofoo and inside the recursion call tnode.dofoo();
> Thnkx..
>
> J.
>
> -
> To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

-- 
----------------------------------------
--EB

> All is fine except that I can reliably "oops" it simply by trying to read
> from /proc/apm (e.g. cat /proc/apm).
> oops output and ksymoops-2.3.4 output is attached.
> Is there anything else I can contribute?

The latitude and longtitude of the bios writers current position, and
a ballistic missile.

                --Alan Cox LKML-December 08,2000 

----------------------------------------
-
To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html