home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / TURBOPAS / TREE.ZIP / TREE.DOC next >
Encoding:
Text File  |  1985-07-13  |  5.7 KB  |  159 lines
  1. Documentation for Tree.inc
  2.  
  3. The file tree.inc includes procedures for (I hope) every function you would
  4. ever need when dealing with a binary search tree.
  5.  
  6. When you define the record structure for the tree's nodes, you must include two
  7. integer variables in each node.  They are "RCtr" and "LCtr".  These variables
  8. hold a count of the number of nodes in each nodes right and left branches and
  9. are used to determine if the tree needs to be balanced or not.
  10.  
  11. You should also create a node that is not put into the tree.  It is used if you
  12. want to search for or delete a particular node.
  13.  
  14. Procedures included (with the arguments) are:
  15.  
  16. procedure InOrder (Root : Rec_Ptr);
  17.  
  18.     Inorder will search the tree "inorder", in other words, it will look at
  19.     the left child, parent, right child in that order.
  20.  
  21.  
  22. procedure PreOrder (Root : Rec_Ptr);
  23.  
  24.     Preorder looks at the parent, left child, right child.
  25.  
  26.  
  27. procedure PostOrder (Root : Rec_Ptr);
  28.  
  29.     Postorder looks at the left child, right child, parent.
  30.  
  31.  
  32.     In these three search procedures, Root is the pointer to the node you
  33.     want to start the seach with.  They all perform a procedure called
  34.     "PrintNode" (discussed later) that the user must write.
  35.  
  36.  
  37. procedure FindNode (Root       : Rec_Ptr;
  38.             var Ptr       : Rec_Ptr;
  39.             Comp_Ptr       : Rec_Ptr;
  40.             var Node_Found : boolean);
  41.  
  42.     Findnode's arguments are :
  43.         Root       : the root node to the tree
  44.         Ptr       : a pointer that will point to the node you are
  45.                  searching for if Node_Found is true
  46.         Comp_Ptr   : a pointer to a node that has a key value equal to
  47.                  the value you are searching for.
  48.         Node_Found : a boolean variable that is returned to tell you if
  49.                  the key value was found or not.
  50.  
  51. procedure AddNode (var Root      : Rec_Ptr;
  52.            Ptr          : Rec_Ptr;
  53.            Cnt          : integer;
  54.            var Node_Added : boolean);
  55.  
  56.     Addnode will add the node pointed to by Ptr into the tree pointed to by
  57.     Root and set Node_Added to true if it was added or false if another
  58.     node with the same key value was found.  Cnt is the number of nodes
  59.     being added (usually one).
  60.  
  61.  
  62. procedure DeleteNode (var Root           : Rec_Ptr;
  63.               Del_Ptr           : Rec_Ptr;
  64.               var Node_Deleted : boolean);
  65.  
  66.     DeleteNode will delete the node with the same key value as the node
  67.     pointed to by Del_Ptr from the tree pointed to by Root and set
  68.     Node_Deleted to true if it was deleted or false if it was not found.
  69.  
  70.  
  71. procedure BalanceTree (var Root : Rec_Ptr);
  72.  
  73.     BalanceTree will balance the tree pointed to by Root.
  74.  
  75.  
  76. procedure CountNodes (Root : Rec_Ptr);
  77.  
  78.     CountNodes will traverse the tree and set the counters for each node.
  79.     This procedure is included because the procedure RebuildTree needs it
  80.     if it cannot rebuild the tree.
  81.  
  82.  
  83. procedure RebuildTree (var Root     : Rec_Ptr;
  84.                var Tree_Rebuilt : boolean;
  85.                Old_Key        : byte);
  86.  
  87.     RebuildTree will restructure and balance the tree pointed to by Root
  88.     based on the current value of Key_Field.  It also sets Tree_Rebuilt to
  89.     true if it was rebuilt or false if duplicate key values were found and
  90.     the tree was rebuilt using Old_Key as Key_Field.  Old_Key should never
  91.     be the same value as Key_Field and should always be a value that has
  92.     been tested.  The program will go into an infinite loop if both
  93.     Key_Field and Old_Key refer to fields that have duplicate values in the
  94.     tree.
  95.  
  96.  
  97. There are two things you need to put into your main program when using these
  98. procedures.
  99.  
  100. 1) You will need to define a Byte called Key_Field for use in comparing the key
  101. fields of nodes in the procedures.  This field is only used in the procedures
  102. CompareNodes (written by the user) and RebuildTree.  If you only plan to use
  103. one key field for the tree, this variable can be omitted (if you remove it from
  104. RebuildTree.)  If, however, you need to sort the tree data by (for example)
  105. phone number as well as zip code, you will need to define this field.
  106.  
  107. 2) You will need to write two procedures to include in your main program.  They
  108. are the following:
  109.  
  110.   PrintNode (Ptr);
  111.  
  112.     Ptr is a pointer type to the node you want to print, display or write.
  113.     If you need to perform more than one of these functions, you will have
  114.     to copy and modify some procedures.  Printnode will print (display,
  115.     write) the data required whenever preorder, inorder or postorder
  116.     are called.
  117.  
  118.  
  119.  CompareNode (Comp_Ptr, Root, Relation);
  120.  
  121.     Comparenode has the following arguments:
  122.         Comp_Ptr : the node in the tree you are currently interested in
  123.         Root     : the parent of Comp_Ptr
  124.         Relation : a character you return based on (whatever) the
  125.                relationship between the two nodes is (L, G, E)
  126.  
  127. examples:
  128.  
  129. procedure PrintNode (Ptr : Rec_Ptr);
  130.     begin
  131.     writeln (Ptr^.Data, ' ', Ptr^.Data2, ' ', Ptr^.LCtr, ' ', Ptr^.RCtr);
  132.     end; { procedure PrintNode }
  133.  
  134.  
  135. procedure CompareNode (Ptr1, Ptr2   : Rec_Ptr;
  136.                var Relation : char);
  137.     begin
  138.     case Key_Field of
  139.          1 : begin
  140.              if Ptr1^.Data < Ptr2^.Data then Relation := 'L';
  141.              if Ptr1^.Data > Ptr2^.Data then Relation := 'G';
  142.              if Ptr1^.Data = Ptr2^.Data then Relation := 'E';
  143.          end;
  144.          2 : begin
  145.              if Ptr1^.Data2 < Ptr2^.Data2 then Relation := 'L';
  146.              if Ptr1^.Data2 > Ptr2^.Data2 then Relation := 'G';
  147.              if Ptr1^.Data2 = Ptr2^.Data2 then Relation := 'E';
  148.          end;
  149.          else Relation := ' ';
  150.     end; { case Key_Field }
  151.     end; { procedure CompareNode }
  152.  
  153. Written by Alan K. Boyd [70107,1772] for the IBM PC using Dos 2.0 and higher
  154. and Turbo Pascal 3.0 and higher.
  155.  
  156. No warranty is given, either expressed or implied, as to the fitness or
  157. usability of these procedures.    No liability is assumed for any loss or damage
  158. claimed as a result of using (or misusing) these procedures.
  159.