Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > no :of nodes

Reply
Thread Tools

no :of nodes

 
 
sophia
Guest
Posts: n/a
 
      05-07-2008
Dear all,

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?


int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}
 
Reply With Quote
 
 
 
 
Walter Roberson
Guest
Posts: n/a
 
      05-07-2008
In article <(E-Mail Removed)>,
sophia <(E-Mail Removed)> wrote:

>How good is this function which is used to find the no: of nodes
>in each level of the binary tree. ?


>int arrlev[100];


>void preorder(struct btree *n,int lev)
>{
> if(!(n))
> return;
>
> arrlev[lev]++;


When you restrict the number of levels in the counters (which
you do in your declaration of arrlev), then before you write
into arrlev[lev] you need to check that you are not overflowing
the end of the array.

> lev++;
>
> preorder(n->left,lev);
> preorder(n->right,lev);


You could avoid a bunch of do-nothing calls:

if (n->left) preorder(n->left,lev);
if (n->right) preorder(n->right,lev);

>}



--
"I want to be remembered as the guy who gave his all whenever
he was on the field." -- Walter Payton
 
Reply With Quote
 
 
 
 
fred.l.kleinschmidt@boeing.com
Guest
Posts: n/a
 
      05-07-2008
On May 7, 11:39*am, Eric Sosman <(E-Mail Removed)> wrote:
> sophia wrote:
> > Dear all,

>
> > How good is this function which is used to find *the no: of nodes
> > in each level of the binary tree. ?

>
> > int arrlev[100];

>
> > void preorder(struct btree *n,int lev)
> > {
> > * * * *if(!(n))
> > * * * *return;

>
> > * * * *arrlev[lev]++;
> > * * * *lev++;

>
> > * * * preorder(n->left,lev);
> > * * * preorder(n->right,lev);
> > }

>
> * * *"How good" is a slippery question, because there are many
> criteria of goodness, some of them in conflict. *So I'll offer
> observations, not judgements.
>
> * * *1) It will fail badly on a tree with more than a hundred
> levels. *Do such trees really exist? *Try this: write a program
> to build a binary search tree from an input stream of words,
> then feed it a list of ten thousand words -- in alphabetical
> order.
>
> * * *2) Even if arrlev[] is made larger, the function is likely
> to fail on very tall trees (or degenerate trees, as above).
> Remember, each function invocation needs to "remember" where
> it was called from so it can return there. *The amount of space
> set aside for this bookkeeping is often rather limited, and if
> the recursive calls go too deep they may exhaust it.
>
> * * *3) You might gain some speed by handling the left branch
> (say) in a loop while making recursive calls only for the right
> branches.
>
> * * *4) You might gain still more speed by using recursion only
> when you encounter a node where both the left and right branches
> are non-NULL. *This also offers some defense against degeneracy.
>
> * * *5) Adding `const' to the first argument might be nice.
>
> * * *6) Adding some commentary about what the function does and
> how to use it might be even nicer.
>
> * * *7) Passing a pointer to the totals array instead of using
> the global variable arrlev[] might be nice.
>
> - Show quoted text -


It would also be nice if the function reported the maximum depth
(the largest value of lev).
--
Fred Kleinschmidt
 
Reply With Quote
 
Thad Smith
Guest
Posts: n/a
 
      05-08-2008
Eric Sosman wrote:
> sophia wrote:
>> How good is this function which is used to find the no: of nodes
>> in each level of the binary tree. ?
>>
>> int arrlev[100];
>>
>> void preorder(struct btree *n,int lev)
>> {
>> if(!(n))
>> return;
>>
>> arrlev[lev]++;
>> lev++;
>>
>> preorder(n->left,lev);
>> preorder(n->right,lev);
>> }

>
> 1) It will fail badly on a tree with more than a hundred
> levels. Do such trees really exist? Try this: write a program
> to build a binary search tree from an input stream of words,
> then feed it a list of ten thousand words -- in alphabetical
> order.
>
> 2) Even if arrlev[] is made larger, the function is likely
> to fail on very tall trees (or degenerate trees, as above).

....
> 4) You might gain still more speed by using recursion only
> when you encounter a node where both the left and right branches
> are non-NULL. This also offers some defense against degeneracy.


I'd say that 4) offers excellent defense against (call level overflow)
degeneracy since the maximum recursion level is less than log2(N)+1.
That doesn't fix the array bounds problem, though.

--
Thad
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      05-08-2008
Thad Smith <(E-Mail Removed)> writes:
> Eric Sosman wrote:
>> sophia wrote:
>>> How good is this function which is used to find the no: of nodes
>>> in each level of the binary tree. ?


[snip]

>> 4) You might gain still more speed by using recursion only
>> when you encounter a node where both the left and right branches
>> are non-NULL. This also offers some defense against degeneracy.

>
> I'd say that 4) offers excellent defense against (call level overflow)
> degeneracy since the maximum recursion level is less than log2(N)+1.


Does it? It limits recursion if the tree is a linear vine, and can
reduce it substantially in some other cases, but what if each node on
the leftmost vine has a single node as its right child? Then the
depth of recursion could be on the order of 1/2 the number of nodes.
(I'm probably not describing it very well.)

To attempt to describe the shape more precisely:

The root A has children B and C. (C has no children.)
B has children D and E. (E has no children.)
D has children F and G. (G has no children.)
F has children H and I. (I has no children.)
And so on.

And here's a picture (use a monospaced font):

A
/ \
B C
/ \
D E
/ \
F G
/ \
H I
.
.
.


> That doesn't fix the array bounds problem, though.


Right.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Spiros Bousbouras
Guest
Posts: n/a
 
      05-08-2008
On 7 May, 19:16, sophia <(E-Mail Removed)> wrote:
> Dear all,
>
> How good is this function which is used to find the no: of nodes
> in each level of the binary tree. ?
>
> int arrlev[100];
>
> void preorder(struct btree *n,int lev)
> {
> if(!(n))
> return;
>
> arrlev[lev]++;
> lev++;
>
> preorder(n->left,lev);
> preorder(n->right,lev);
>
> }


Apart from the comments made by others I note also
that the way it is written it will only count the nodes
starting from lev0 and above where lev0 is the value
it is initially passed as a second argument. I assume
the intention is to call the function with a second
argument of 0 but it might be clearer to write it like
this:

int arrlev[100];

void preorder(struct btree *n) {
preorder_aux(n , 0) ;
}

void preorder_aux(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);

}

I don't think the name "preorder" is very appropriate
because one would use it in cases where one might have
doubts that the preorder is actually an order. But a tree
is actually an order. Best to call your function
count_level_nodes or something.
 
Reply With Quote
 
Walter Roberson
Guest
Posts: n/a
 
      05-08-2008
In article <(E-Mail Removed)>,
Spiros Bousbouras <(E-Mail Removed)> wrote:

>I don't think the name "preorder" is very appropriate
>because one would use it in cases where one might have
>doubts that the preorder is actually an order. But a tree
>is actually an order. Best to call your function
>count_level_nodes or something.


I don't understand your comment, Spiros.

"preorder" is the name of one of the major strategies for
visiting all nodes of a tree; it involves visiting the leaves
of a node in left-to-right order, always following all the way down
the left-most unvisited side before processing any of the nodes further
right. The code the original poster put up uses preorder traversal
of a binary tree.

I have not been able to come up with a meaning of "order" that
would fit with your comment "But a tree is actually an order."
A tree just *is*; it might perhaps -encode- a command
("command" or "instructions" is one meaning of "order"), but
that would depend upon the -interpretation- of the tree, not upon
the tree itself.
--
"You may comand nature to the extent only in which you are willing to
obey her." -- Walter Russell
 
Reply With Quote
 
Spiros Bousbouras
Guest
Posts: n/a
 
      05-08-2008
On 8 May, 15:53, (E-Mail Removed)-cnrc.gc.ca (Walter Roberson) wrote:
> In article <(E-Mail Removed)>,
> Spiros Bousbouras <(E-Mail Removed)> wrote:
>
> >I don't think the name "preorder" is very appropriate
> >because one would use it in cases where one might have
> >doubts that the preorder is actually an order. But a tree
> >is actually an order. Best to call your function
> >count_level_nodes or something.

>
> I don't understand your comment, Spiros.
>
> "preorder" is the name of one of the major strategies for
> visiting all nodes of a tree; it involves visiting the leaves
> of a node in left-to-right order, always following all the way down
> the left-most unvisited side before processing any of the nodes further
> right. The code the original poster put up uses preorder traversal
> of a binary tree.
>
> I have not been able to come up with a meaning of "order" that
> would fit with your comment "But a tree is actually an order."
> A tree just *is*; it might perhaps -encode- a command
> ("command" or "instructions" is one meaning of "order"), but
> that would depend upon the -interpretation- of the tree, not upon
> the tree itself.


Oh I see. I was only familiar with the mathematical meaning of
preorder (http://en.wikipedia.org/wiki/Preorder) I didn't know it
also has a meaning in computer science. In the mathematical
sense a tree is a (partial) order which also makes it a preorder.
 
Reply With Quote
 
Thad Smith
Guest
Posts: n/a
 
      05-17-2008
Keith Thompson wrote:
> Thad Smith <(E-Mail Removed)> writes:
>> Eric Sosman wrote:
>>> sophia wrote:
>>>> How good is this function which is used to find the no: of nodes
>>>> in each level of the binary tree. ?

>
> [snip]
>
>>> 4) You might gain still more speed by using recursion only
>>> when you encounter a node where both the left and right branches
>>> are non-NULL. This also offers some defense against degeneracy.

>> I'd say that 4) offers excellent defense against (call level overflow)
>> degeneracy since the maximum recursion level is less than log2(N)+1.

>
> Does it? It limits recursion if the tree is a linear vine, and can
> reduce it substantially in some other cases, but what if each node on
> the leftmost vine has a single node as its right child? Then the
> depth of recursion could be on the order of 1/2 the number of nodes.
> (I'm probably not describing it very well.)
>
> And here's a picture (use a monospaced font):
>
> A
> / \
> B C
> / \
> D E
> / \
> F G
> / \
> H I
> .
> .
> .
>


Oops, thanks for correcting my mistake.

--
Thad
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Text nodes and element nodes query asd Java 3 05-23-2005 10:01 AM
finding nodes that don't match other nodes mlybarger@gmail.com XML 2 01-27-2005 07:26 PM
Looking A Nodes From Within Nodes Johnny Ooi XML 10 11-14-2004 06:55 PM
selecting nodes between other nodes Timo Nentwig XML 1 06-17-2004 04:54 AM
Reality check: Is it sensible to link XML nodes to other XML nodes in the same file? gavnosis XML 0 08-02-2003 08:22 AM



Advertisments