How to determine the height of a binary tree 
Author Message
 How to determine the height of a binary tree

Hi,
Can anyone here help me? Our class was given a homework to write a recursive
function that can determine the height of binary (standard Binary tree ADT).
And so far, I haven't been able to do the function as I just can't seem to
figure out the logic of writing the recursive function. So I would really
appreciate it if someone could tell me the algorithm for solving this
problem(or better provide me with the source codes !) or at least show me
where I can find some info on solving this problem

TDR



Wed, 18 Jun 1902 08:00:00 GMT  
 How to determine the height of a binary tree

Quote:

>Hi,
>Can anyone here help me? Our class was given a homework to write a recursive
>function that can determine the height of binary (standard Binary tree ADT).
>And so far, I haven't been able to do the function as I just can't seem to
>figure out the logic of writing the recursive function. So I would really
>appreciate it if someone could tell me the algorithm for solving this
>problem(or better provide me with the source codes !) or at least show me
>where I can find some info on solving this problem

Function Height(p:node):word;
var l,r:word;
Begin
  if p=nil then begin
     Height:=1;
     exit;
  End;
  l:=height(p^.left);
  r:=height(q^.right);
  if r<l then Height:=r
         else Height:=l;
End;

The above code has a few deliberately inserted errors so you have to
figure how it works before presenting it.

A general principle of a recursive routine is:

1) check for the termination condition
2) call the function recursively with modified parameters one or more times
3) process the results of the recursive calls.

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 How to determine the height of a binary tree


Quote:

> Function Height(p:node):word;
> var l,r:word;
> Begin
>   if p=nil then begin
>      Height:=1;

Why not 0?

Quote:
>      exit;
>   End;
>   l:=height(p^.left);
>   r:=height(q^.right);

Mm..
    l:=height(p^.left)+1;
    r:=height(p^.right)+1;
Did you mean this?

Quote:
>   if r<l then Height:=r
>          else Height:=l;
> End;

Well, what is height of a binary tree? I guess it should be 'if r>l' but
this can be discussed.

Quote:
> The above code has a few deliberately inserted errors so you have to
> figure how it works before presenting it.

> A general principle of a recursive routine is:

> 1) check for the termination condition
> 2) call the function recursively with modified parameters one or more
times
> 3) process the results of the recursive calls.

> Osmo

  4) check for bugs :-)

(I do not guarantee that I didn't add any)

Ingmar

Sent via Deja.com http://www.deja.com/
Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 How to determine the height of a binary tree
Hi,


Quote:
> Can anyone here help me? Our class was given a homework to write a recursive
> function that can determine the height of binary (standard Binary tree ADT).
> And so far, I haven't been able to do the function as I just can't seem to
> figure out the logic of writing the recursive function.

For any given node, the height of the tree on top of which it sits is one
plus the height of the trees under it (if they are not equal in height,
take the greater one).

That should pretty much explain it, because it is a recursive definition,
and if you start with the tree's root, the height you calculate from there
is the height of the whole tree.

 - Sebastian

--
Always remember: "Batch" is NOT a programming language!



Wed, 18 Jun 1902 08:00:00 GMT  
 How to determine the height of a binary tree


Quote:


>> Function Height(p:node):word;
>> var l,r:word;
>> Begin
>>   if p=nil then begin
>>      Height:=1;

>Why not 0?

>>      exit;
>>   End;
>>   l:=height(p^.left);
>>   r:=height(q^.right);

>Mm..
>    l:=height(p^.left)+1;
>    r:=height(p^.right)+1;
>Did you mean this?

>>   if r<l then Height:=r
>>          else Height:=l;
>> End;

>Well, what is height of a binary tree? I guess it should be 'if r>l' but
>this can be discussed.

>> The above code has a few deliberately inserted errors so you have to

   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Quote:
>> figure how it works before presenting it.

   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quote:

>> A general principle of a recursive routine is:

>> 1) check for the termination condition
>> 2) call the function recursively with modified parameters one or more
>times
>> 3) process the results of the recursive calls.

>> Osmo

>  4) check for bugs :-)

Well you found all the bugs I inserted. Now you gave the guy his
homework.

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 How to determine the height of a binary tree


Quote:

> Well you found all the bugs I inserted. Now you gave the guy his
> homework.

> Osmo

Oops! I lost one line of you message and was wondering if Osmo is
sleeping or drunk. Sorry.

--
Ingmar

Sent via Deja.com http://www.deja.com/
Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. The use of coprcessor reals (previously Re: Stack overflow at binary tree balance)

2. Stack overflow at binary tree balance

3. binary search tree

4. Binary tree problem

5. Binary Tree

6. Binary Search tree runtime error 103

7. Binary Search Tree help needed

8. Recursion and Binary Tree

9. Recursion and Binary Tree

10. Binary tree proof.

11. Showing Binary trees

 

 
Powered by phpBB® Forum Software