# Board index » delphi » Binary Search Trees

## Binary Search Trees

I need to find out how to create several recursive functions/procedures
for manipulating binary search trees
specifically:

Counting the nodes of a tree  {i can't do this unless I use global vars}
finding the sum of integers
in the tree                   {same global var problem}
disposing of a whole tree     {i get pointer erorrs might be able to
fix}
finding the height of a tree  {not sure how to implement}

if you know where I can look for this info or have the answers they
would be greatly appreciated

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
James David Allan                          umall...@cc.umanitoba.ca
U of M  Comp. Eng. II         http://home.cc.umanitoba.ca/~umalla21
-------------------------------------------------------------------

## Re:Binary Search Trees

On Wed, 26 Feb 1997 10:15:42 -0600,  James David Allan

##### Quote
<umall...@cc.umanitoba.ca> wrote:
>I need to find out how to create several recursive functions/procedures
>for manipulating binary search trees
>specifically:

>Counting the nodes of a tree  {i can't do this unless I use global vars}
>finding the sum of integers
>in the tree               {same global var problem}
>disposing of a whole tree     {i get pointer erorrs might be able to
>fix}
>finding the height of a tree  {not sure how to implement}

>if you know where I can look for this info or have the answers they
>would be greatly appreciated

A recursive routine is a form of divide and conquer tactic.  When designing a
recursive routine try to limit yourself to the current instance.  e.g.  When
designing a procedure to delete a tree, think in terms of the single pointer to
a node that you are given. If it's NIL then do nothing!  Otherwise delete left
and right nodes (recursive calls), then delete my node.  Hopefully when you were
thinking of having to manage the process for one node you realized that the node
shouldn't be deleted until after both left and right nodes had been deleted.
Deleting the tree in this order should eliminate pointer errors.

Rather than pass a VAR parameter or use a global you could make the recursive
function a subprocedure.  This would allow using a local variable in the parent
procedure/function.  For example, you could have a node counting function that
would be passed a pointer to a tree.  It has a local "count" variable that it
initializes to zero and calls a subprocedure, passing the root node.  The
subprocedure increments the parents "count" variable then calls itself with the
left and then the right nodes.

You could use something similar to find the height of the tree.  This time the
parent has two variables.  One for the current depth, another for the tree
depth.  The parent procedure begins by setting both variables to zero then calls
the subprocedure with the root node.  The subprocedure increments the current
depth when it begins, updates the tree depth if the current depth is larger than
the tree depth, and decrements the current depth before leaving the routine.

When the above routines end, the parent returns the answer.  Naturally the
subprocedures do nothing if the pointer to the node is nil.

...red

## Re:Binary Search Trees

On Wed, 26 Feb 1997 10:15:42 -0600,  James David Allan

##### Quote
umall...@cc.umanitoba.ca> wrote:
>I need to find out how to create several recursive functions/procedures
>for manipulating binary search trees
>specifically:

>Counting the nodes of a tree  {i can't do this unless I use global vars}
>finding the sum of integers
>in the tree                   {same global var problem}
>disposing of a whole tree     {i get pointer erorrs might be able to
>fix}
>finding the height of a tree  {not sure how to implement}

>if you know where I can look for this info or have the answers they
>would be greatly appreciated

Counting Nodes:

Function Count(p : TNode) : longint;
begin
If p = nil then
Count := 0
else
Count := Count(p^.Left,p^.Right)+1;
end;

Disposing Tree:

Procedure FreeIt(p : TNode);
begin
if p <> nil then
begin
FreeIt(p^.Left);
FreeIt(p^.Right);
freemem(p,sizeof(TNode));
end;
end;

Height of Tree:

Function Height(p : TNode) : longint;
var
H, Max : longint;
begin
if p = 0 then
Height := 0
else
begin
Max := Height(p^.Left);
H := Height(p^.Right);
if H > Max then
Height := H+1
else
Height := Max+1;
end;
end;

--
MyKey
Fif{*word*249} Minutes of Fame
HTTP://www.{*word*104}g8t.com/jwhite/fame15.htm

## Re:Binary Search Trees

##### Quote
Mike White wrote:
> [snip to keep my browser happy :( ]
> Counting Nodes:

> Function Count(p : TNode) : longint;
> begin
>   If p = nil then
>     Count := 0
>   else
>     Count := Count(p^.Left,p^.Right)+1;

Perhaps this should be :
Count := Count( p^.Left) + Count( p^.Right) + 1

To keep the compiler happy :)

Regards

Remco

--
--------------------------------------------------------------------------------
This is an automatically generated signature for Remco Vietor in
netscape.
The views expressed in this message should be taken as the personal views
of
the author, unless stated otherwise.

## Re:Binary Search Trees

--

edit .signature
Tom Holt
T.D.H...@exeter.ac.uk