binary tree traversal...

binary tree traversal...

[J.]

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

Thnkx..

J.

Re: binary tree traversal...

[Eric Bambach]

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

Re: binary tree traversal...

[Joel Pareja]

[-- Attachment #1: Type: text/plain, Size: 1943 bytes --]

Hi,

It did traverse your binary tree. However, your call to printf is only
performed with the first(?) node.

I think this is how to accomplish what you want.

---- snippet+  ---

{
  ....
  treerecurse(root);   // you don't need a loop here
  ....

}

struct tnode *treerecurse(struct tnode *p) {
 if(p != NULL) {
  treerecurse(p->left);

  printf("%4d %s\n", p->count, p->word);  // perform what   
                                          //  you desire for
                                          //  each entry
  treerecurse(p->right);
 }
}

---- snippet- ----


Hope this helps,
Joel 

On Thu, 2005-01-27 at 07:01, 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...
> 
> 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
-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." 
					    - Brian W. Kernighan

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: binary tree traversal...

[J.]

On Wed, 26 Jan 2005, Eric Bambach wrote:

> On Wednesday 26 January 2005 05:01 pm, J. wrote:
> > Wednesday, January 26

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

Aha, of course momement here ! ;-)
 
> Why dont you just pass a function pointer into the recursive function so it 
> looks like this:(pseudocode, my function pointer syntax is bad)

Thnkx...

I slept a night over it and decided that it was way more effecient for my
program to keep an shadow array of pointers to each node in the tree.
That way it's easy sorting, iter etc.. And it works without a large mem
increase.

Thnkx again.. for the answer.

J.

Re: binary tree traversal...

[Glynn Clements]

J. wrote:

> 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;

This causes the function to return, so ...

>   treerecurse(p->right);

... this will never be executed.

-- 
Glynn Clements <glynn@gclements.plus.com>