no :of nodes
sophia
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);
}
Walter Roberson
sophia <sophia...@gmail.com> 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
Eric Sosman
"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.
fred.l.kl...@boeing.com
It would also be nice if the function reported the maximum depth
(the largest value of lev).
--
Fred Kleinschmidt
Chris Thomasson
news:7521541f-9a67-4239...@h1g2000prh.googlegroups.com...
Its no good. Use dynamic allocation if the level count of the tree is not
known in advance. Also, recursion is not safe. Passing some tress to this
function will blow the stack. There are ways to traverse a tree without
using recursion. Here is a simple example:
Instead of threading the tree, you can include an auxiliary node that a
traversal function uses as an node to link into a local queue. Check the
'destroy_tree()' function...
Chris Thomasson
news:vLGdndQrSbqk2L_V...@comcast.com...
> "sophia" <sophia...@gmail.com> wrote in message
> news:7521541f-9a67-4239...@h1g2000prh.googlegroups.com...
>> 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);
>> }
>
> Its no good. Use dynamic allocation if the level count of the tree is not
> known in advance. Also, recursion is not safe. Passing some tress to this
> function will blow the stack. There are ways to traverse a tree without
> using recursion. Here is a simple example:
>
> http://pastebin.com/m7ffa217c
ARGH!!!!
Forget that code!
Look at this one instead!
Sorry about the first one. I made forgot to call free!!!!!!!
;^(...
Richard Harter
If I read the code correctly, it makes a separate malloc call for
each new node. While legal, that makes for inefficient code. It
is better to allocate space for a block of nodes and link them
into a free list. There are other alternatives, but the essence
is that one malloc per node is expensive and should be avoided in
production code.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
Thad Smith
> 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);
>> }
>
> 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
Chris Thomasson
news:482268d8....@news.sbtc.net...
> On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
> <cri...@comcast.net> wrote:
>
>>"Chris Thomasson" <cri...@comcast.net> wrote in message
>>news:vLGdndQrSbqk2L_V...@comcast.com...
>>>
>>> Its no good. Use dynamic allocation if the level count of the tree is
>>> not
>>> known in advance. Also, recursion is not safe. Passing some tress to
>>> this
>>> function will blow the stack. There are ways to traverse a tree without
>>> using recursion. Here is a simple example:
>>
>>http://pastebin.com/m3e5a9fd8
[...]
>>> Instead of threading the tree, you can include an auxiliary node that a
>>> traversal function uses as an node to link into a local queue. Check the
>>> 'destroy_tree()' function...
>
>
> If I read the code correctly, it makes a separate malloc call for
> each new node. While legal, that makes for inefficient code. It
> is better to allocate space for a block of nodes and link them
> into a free list. There are other alternatives, but the essence
> is that one malloc per node is expensive and should be avoided in
> production code.
You can hook it up to the following crude region allocator I did:
http://groups.google.com/group/comp.lang.c/browse_frm/thread/f8f65273b09b4229
Now, the tree program can look something like:
The region allocator simply increments a counter and bumps a pointer along
the buffer until the end is reached, then another region is allocated.
Deallocations consist of decrementing the counter and resetting the
allocator state when zero is reached. It can dynamically expand and shrink.
It can also amortize calls to free into a single "reset" call. The example
code shows this...
Any thoughts?
Keith Thompson
> 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) <ks...@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Spiros Bousbouras
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.
Eric Sosman
> Thad Smith <Thad...@acm.org> 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.
That's why I only claimed "some" defense against degeneracy.
Even in the tree you describe one might get lucky: if when
faced with a two-way branch the function always recursed to the
right and looped to the left, there'd be no trouble. Of course,
then a tree that leaned the other direction would be bad. So
would a zig-zag arrangement where the "trunk" went left and right
alternately while the "twigs" branched right and left.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Chris Thomasson
news:IdSdne1qWJRzbr_V...@comcast.com...
I personally find that using recursion to traverse trees can be somewhat
dangerous because certain trees can potentially blow the stack. To get
around recursion, I tend to use an auxiliary node, and use that as a link
into a traversal queue. Something like:
<pseudo-code>
_______________________________________________________________
struct tnode {
struct tnode* left;
struct tnode* right;
struct tnode* next;
};
/* Tree Iteration Support */
struct tnode_iterq {
struct tnode* head;
struct tnode* tail;
};
void tnode_iterq_push(
tnode_iterq* const _this,
tnode* const node
) {
if (node) {
node->next = NULL;
if (! _this->head) {
_this->head = node;
} else {
_this->tail->next = node;
}
_this->tail = node;
}
}
tnode* tnode_iterq_pop(
tnode_iterq* const _this
) {
tnode* const node = _this->head;
if (node) {
if (! (_this->head = node->next)) {
_this->tail = NULL;
}
}
return node;
}
/* Tree Iterator */
void* tnode_iterate(
tnode* const _this,
void (*fp_iterate) (tnode*, void*),
void* const state
) {
unsigned count = 0;
tnode* node = _this;
tnode_iterq iterq = { NULL };
do {
tnode_iterq_push(&iterq, node->left);
tnode_iterq_push(&iterq, node->right);
fp_iterate(node, state);
++count;
} while (! (node = tnode_iterq_pop(&iterq)));
return state;
}
_______________________________________________________________
Now there is no chance of blowing the stack because all recursion is
eluded...
Richard Harter
<cri...@comcast.net> wrote:
If you like. There is one no-no in your code - you start some of
your variables with an underscore. Don't do this; you're invading
the system implementation namespace.
There is an oddity in allocator_release - you call assert(0)
followed by a call to abort. The assert(0) calls abort.
What you have is commonly called a pool allocator; it's a good
thing to have available. Your implementation looks plausible,
though I would be happier if it had some inline documentation.
Advantages of pool allocators: Allocation can be significantly
faster than with malloc; deallocation only requires freeing the
entire pool rather than freeing each item.
That said, when all items in the pool are the same kind of thing,
e.g., tree nodes, it can pay to have a free list. Pushing items
onto the free list and popping them off is equally cheap, and you
(potentially) use less storage.
A caveat here is that execution costs in modern machines depends
upon cache hits and misses. In a tree it may pay to arrange the
code so that nodes that are near each other in the tree are near
each other in local storage as much as possible.
Walter Roberson
Spiros Bousbouras <spi...@gmail.com> 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
Chris Thomasson
>>The region allocator simply increments a counter and bumps a pointer along
>>the buffer until the end is reached, then another region is allocated.
>>Deallocations consist of decrementing the counter and resetting the
>>allocator state when zero is reached. It can dynamically expand and
>>shrink.
>>It can also amortize calls to free into a single "reset" call. The example
>>code shows this...
>>
>>
>>Any thoughts?
>>
>
> If you like. There is one no-no in your code - you start some of
> your variables with an underscore. Don't do this; you're invading
> the system implementation namespace.
This issue has been raised:
http://groups.google.com/group/comp.lang.c/browse_frm/thread/de5f62667b250ca3
There happens to nothing wrong with the way I am using it. E.g.:
static void
foo_something(
struct foo* const _this
) {
[...];
}
> There is an oddity in allocator_release - you call assert(0)
> followed by a call to abort. The assert(0) calls abort.
I want abort to still be called when NDEBUG is defined.
> What you have is commonly called a pool allocator; it's a good
> thing to have available. Your implementation looks plausible,
> though I would be happier if it had some inline documentation.
>
> Advantages of pool allocators: Allocation can be significantly
> faster than with malloc; deallocation only requires freeing the
> entire pool rather than freeing each item.
>
> That said, when all items in the pool are the same kind of thing,
> e.g., tree nodes, it can pay to have a free list. Pushing items
> onto the free list and popping them off is equally cheap, and you
> (potentially) use less storage.
>
> A caveat here is that execution costs in modern machines depends
> upon cache hits and misses. In a tree it may pay to arrange the
> code so that nodes that are near each other in the tree are near
> each other in local storage as much as possible.
Agreed.
Spiros Bousbouras
> In article <8ad43552-b186-4aa9-8688-34e203ff9...@e39g2000hsf.googlegroups.com>,
> Spiros Bousbouras <spi...@gmail.com> 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.
Thad Smith
> Thad Smith <Thad...@acm.org> 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.)
>
>
> A
> / \
> B C
> / \
> D E
> / \
> F G
> / \
> H I
> .
> .
> .
>
Oops, thanks for correcting my mistake.
--
Thad