On May 7, 11:39=A0am, Eric Sosman <Eric.Sos...@[EMAIL PROTECTED]
> wrote:
> sophia wrote:
> > Dear all,
>
> > How good is this function which is used to find =A0the no: of nodes
> > in each level of the binary tree. ?
>
> > int arrlev[100];
>
> > void preorder(struct btree *n,int lev)
> > {
> > =A0 =A0 =A0 =A0if(!(n))
> > =A0 =A0 =A0 =A0return;
>
> > =A0 =A0 =A0 =A0arrlev[lev]++;
> > =A0 =A0 =A0 =A0lev++;
>
> > =A0 =A0 =A0 preorder(n->left,lev);
> > =A0 =A0 =A0 preorder(n->right,lev);
> > }
>
> =A0 =A0 =A0"How good" is a slippery question, because there are many
> criteria of goodness, some of them in conflict. =A0So I'll offer
> observations, not judgements.
>
> =A0 =A0 =A01) It will fail badly on a tree with more than a hundred
> levels. =A0Do such trees really exist? =A0Try 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.
>
> =A0 =A0 =A02) 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. =A0The amount of space
> set aside for this bookkeeping is often rather limited, and if
> the recursive calls go too deep they may exhaust it.
>
> =A0 =A0 =A03) You might gain some speed by handling the left branch
> (say) in a loop while making recursive calls only for the right
> branches.
>
> =A0 =A0 =A04) 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. =A0This also offers some defense against degeneracy.
>
> =A0 =A0 =A05) Adding `const' to the first argument might be nice.
>
> =A0 =A0 =A06) Adding some commentary about what the function does and
> how to use it might be even nicer.
>
> =A0 =A0 =A07) 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 re****ted the maximum depth
(the largest value of lev).
--
Fred Kleinschmidt
|
