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

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

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.

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

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;

To keep the compiler happy :)

Regards

Remco

--