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.
--
Eric.Sosman@[EMAIL PROTECTED]
|
