Documentation for Tree.inc

The file tree.inc includes procedures for (I hope) every function you would
ever need when dealing with a binary search tree.

When you define the record structure for the tree's nodes, you must include two
integer variables in each node. They are "RCtr" and "LCtr". These variables
hold a count of the number of nodes in each nodes right and left branches and
are used to determine if the tree needs to be balanced or not.

You should also create a node that is not put into the tree. It is used if you
want to search for or delete a particular node.

Procedures included (with the arguments) are:

procedure InOrder (Root : Rec_Ptr);

Inorder will search the tree "inorder", in other words, it will look at
the left child, parent, right child in that order.


procedure PreOrder (Root : Rec_Ptr);

Preorder looks at the parent, left child, right child.


procedure PostOrder (Root : Rec_Ptr);

Postorder looks at the left child, right child, parent.


In these three search procedures, Root is the pointer to the node you
want to start the seach with. They all perform a procedure called
"PrintNode" (discussed later) that the user must write.


procedure FindNode (Root : Rec_Ptr;
var Ptr : Rec_Ptr;
Comp_Ptr : Rec_Ptr;
var Node_Found : boolean);

Findnode's arguments are :
Root : the root node to the tree
Ptr : a pointer that will point to the node you are
searching for if Node_Found is true
Comp_Ptr : a pointer to a node that has a key value equal to
the value you are searching for.
Node_Found : a boolean variable that is returned to tell you if
the key value was found or not.

procedure AddNode (var Root : Rec_Ptr;
Ptr : Rec_Ptr;
Cnt : integer;
var Node_Added : boolean);

Addnode will add the node pointed to by Ptr into the tree pointed to by
Root and set Node_Added to true if it was added or false if another
node with the same key value was found. Cnt is the number of nodes
being added (usually one).


procedure DeleteNode (var Root : Rec_Ptr;
Del_Ptr : Rec_Ptr;
var Node_Deleted : boolean);

DeleteNode will delete the node with the same key value as the node
pointed to by Del_Ptr from the tree pointed to by Root and set
Node_Deleted to true if it was deleted or false if it was not found.


procedure BalanceTree (var Root : Rec_Ptr);

BalanceTree will balance the tree pointed to by Root.


procedure CountNodes (Root : Rec_Ptr);

CountNodes will traverse the tree and set the counters for each node.
This procedure is included because the procedure RebuildTree needs it
if it cannot rebuild the tree.


procedure RebuildTree (var Root : Rec_Ptr;
var Tree_Rebuilt : boolean;
Old_Key: byte);

RebuildTree will restructure and balance the tree pointed to by Root
based on the current value of Key_Field. It also sets Tree_Rebuilt to
true if it was rebuilt or false if duplicate key values were found and
the tree was rebuilt using Old_Key as Key_Field. Old_Key should never
be the same value as Key_Field and should always be a value that has
been tested. The program will go into an infinite loop if both
Key_Field and Old_Key refer to fields that have duplicate values in the
tree.


There are two things you need to put into your main program when using these
procedures.

1) You will need to define a Byte called Key_Field for use in comparing the key
fields of nodes in the procedures. This field is only used in the procedures
CompareNodes (written by the user) and RebuildTree. If you only plan to use
one key field for the tree, this variable can be omitted (if you remove it from
RebuildTree.) If, however, you need to sort the tree data by (for example)
phone number as well as zip code, you will need to define this field.

2) You will need to write two procedures to include in your main program. They
are the following:

PrintNode (Ptr);


Ptr is a pointer type to the node you want to print, display or write.
If you need to perform more than one of these functions, you will have
to copy and modify some procedures. Printnode will print (display,
write) the data required whenever preorder, inorder or postorder
are called.


CompareNode (Comp_Ptr, Root, Relation);

Comparenode has the following arguments:
Comp_Ptr : the node in the tree you are currently interested in
Root : the parent of Comp_Ptr
Relation : a character you return based on (whatever) the
relationship between the two nodes is (L, G, E)

examples:

procedure PrintNode (Ptr : Rec_Ptr);
begin
writeln (Ptr^.Data, ' ', Ptr^.Data2, ' ', Ptr^.LCtr, ' ', Ptr^.RCtr);
end; { procedure PrintNode }


procedure CompareNode (Ptr1, Ptr2 : Rec_Ptr;
var Relation : char);
begin
case Key_Field of
1 : begin
if Ptr1^.Data < Ptr2^.Data then Relation := 'L';
if Ptr1^.Data > Ptr2^.Data then Relation := 'G';
if Ptr1^.Data = Ptr2^.Data then Relation := 'E';
end;
2 : begin
if Ptr1^.Data2 < Ptr2^.Data2 then Relation := 'L';
if Ptr1^.Data2 > Ptr2^.Data2 then Relation := 'G';
if Ptr1^.Data2 = Ptr2^.Data2 then Relation := 'E';
end;
else Relation := ' ';
end; { case Key_Field }
end; { procedure CompareNode }

Written by Alan K. Boyd [70107,1772] for the IBM PC using Dos 2.0 and higher
and Turbo Pascal 3.0 and higher.

No warranty is given, either expressed or implied, as to the fitness or
usability of these procedures.No liability is assumed for any loss or damage
claimed as a result of using (or misusing) these procedures.