Prev: Looking for a development tool to list all the functions in asource file
Next: ParallelQueueh ...
From: rake on 11 Mar 2010 11:51
I have come accross with the code for finding Depth of tree, i am not
getting this, please anyone throw a light on this ....


http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg

please explain in code level rather than theoratical level.

int depth(treenode *p)
{
if(p==NULL)return(0);
if(p->left){h1=depth(p->left);}
if(p=>right){h2=depth(p->right);}
return(max(h1,h2)+1);
}

From: Andrew Poelstra on 11 Mar 2010 14:00
On 2010-03-11, rake <t.sathyanarayanan(a)gmail.com> wrote:
> I have come accross with the code for finding Depth of tree, i am not
> getting this, please anyone throw a light on this ....
>
>
> http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg
>
> please explain in code level rather than theoratical level.
>
> int depth(treenode *p)
> {
> if(p==NULL)return(0);
> if(p->left){h1=depth(p->left);}
> if(p=>right){h2=depth(p->right);}
> return(max(h1,h2)+1);
> }
>

First, let's clean this up and add definitions for h1 and h2:
(BTW, I renamed h-one to h-el. My apologies.)

int depth(treenode *p)
{
int hl = 0;
int hr = 0;

if(p == NULL)
return 0;
if(p->left)
hl = depth(p->left);
if(p->right)
h2 = depth(p->right);

return 1 + max(h1, h2);
}

The way a tree works is that each node is a tree in itself - so
to calculate its depth at any given node, you take 1 (for the
node itself) and add the depth of whatever one of its subtrees
is taller.

So given the tree:

A
/ \
B D
|
C

and told to find depth(A), you code does this:

1. See if A has a left tree.
i. It does, B. Find depth(B).
ii. Does B have a left tree?
a. It does, C. Find depth(C).
b. Does C have a left tree? No, hl = 0.
c. Does C have a right tree? No, hr = 0.
d. Return depth(C) as 1.
iii. Does B have a right tree? No, hr = 0.
iv. Return depth(B) as 2 (1 + depth(C)).
2. See if A has a right tree.
i. It does, D. Find depth(D).
ii. Does D have a left tree? No, hl = 0.
iii. Does D have a right tree? No, hr = 0.
iv. Return depth(D) as 1.
3. Return depth(A) as 3 (1 + max(depth(B), depth(D)).


HTH.


--
Andrew Poelstra
http://www.wpsoftware.net/andrew
From: Daniel Pitts on 11 Mar 2010 18:00
On 3/11/2010 8:51 AM, rake wrote:
> I have come accross with the code for finding Depth of tree, i am not
> getting this, please anyone throw a light on this ....
>
>
> http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg
>
> please explain in code level rather than theoratical level.
>
> int depth(treenode *p)
> {
// If I the node is null (there is no root) return 0
> if(p==NULL)return(0);
// If there is a left, get the depth of the sub-tree rooted to the left.
> if(p->left){h1=depth(p->left);}
// If there is a right, get the depth of the tree rooted to the right.
> if(p=>right){h2=depth(p->right);}
// This level is one more than the highest of the levels below me.
> return(max(h1,h2)+1);
> }
>

I might rewrite this as:
int depth(treenode *p) {
return p == NULL ? 0 : (1 + max(depth(p->left), depth(p->right));
}

It does the same thing, but more concisely. Note, conciseness is not a
goal in itself, but for a piece of code like this it is more readable IMO.


--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Ashton K on 14 Mar 2010 17:22
Daniel Pitts <newsgroup.spamfilter(a)virtualinfinity.net> wrote:
> On 3/11/2010 8:51 AM, rake wrote:
>> I have come accross with the code for finding Depth of tree, i am not
>> getting this, please anyone throw a light on this ....
>>
>>
>> http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg
>>
>> please explain in code level rather than theoratical level.
>>
>> int depth(treenode *p)
>> {
> // If I the node is null (there is no root) return 0
>> if(p==NULL)return(0);
> // If there is a left, get the depth of the sub-tree rooted to the left.
>> if(p->left){h1=depth(p->left);}
> // If there is a right, get the depth of the tree rooted to the right.
>> if(p=>right){h2=depth(p->right);}
> // This level is one more than the highest of the levels below me.
>> return(max(h1,h2)+1);
>> }
>>
>
> I might rewrite this as:
> int depth(treenode *p) {
> return p == NULL ? 0 : (1 + max(depth(p->left), depth(p->right));
> }
>
> It does the same thing, but more concisely. Note, conciseness is not a
> goal in itself, but for a piece of code like this it is more readable IMO.
>
>

And that's why I've always loved/hated C. Ridiculous one liners.

--Ashton
From: Daniel Pitts on 15 Mar 2010 13:56
On 3/14/2010 2:22 PM, Ashton K wrote:
> Daniel Pitts<newsgroup.spamfilter(a)virtualinfinity.net> wrote:
>> int depth(treenode *p) {
>> return p == NULL ? 0 : (1 + max(depth(p->left), depth(p->right));
>> }
>
> And that's why I've always loved/hated C. Ridiculous one liners.
Hmm. I don't think its ridiculous. Although, it doesn't hurt either way
to split it up.

Actually, I'm too used to Java, so in C I would write:

int depth(node *node) {
if (!node) return 0;
return 1 + max(depth(node->left), depth(node->right));
}

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
 | 
Pages: 1
Prev: Looking for a development tool to list all the functions in asource file
Next: ParallelQueueh ...