On Wed, 7 May 2008 17:22:50 -0700, "Chris Thomasson"
<cristom@[EMAIL PROTECTED]
> wrote:
>"Chris Thomasson" <cristom@[EMAIL PROTECTED]
> wrote in message
>news:vLGdndQrSbqk2L_VnZ2dnUVZ_rjinZ2d@[EMAIL PROTECTED]
>> "sophia" <sophia.agnes@[EMAIL PROTECTED]
> wrote in message
>>
news:7521541f-9a67-4239-93d5-1452d442314c@[EMAIL PROTECTED]
>>> 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!
>
>http://pastebin.com/m3e5a9fd8
>
>
>Sorry about the first one. I made forgot to call free!!!!!!!
>
>;^(...
>
>
>
>> 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.
Richard Harter, cri@[EMAIL PROTECTED]
http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
|
