home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PASCALA.ZIP / ASSIGN9.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1991-05-09  |  6.3 KB  |  209 lines
  1.   (**********************************************)
  2.   (* ALEJO ALAMILLO                *)
  3.   (* COSC 055                    *)
  4.   (* ASST. #9                    *)
  5.   (* SPRING 1991                *)
  6.   (**********************************************)    
  7.  
  8. (*************************************************************)
  9. (*  Several procedures for binary tree processing are        *)
  10. (*  contained in the module below.                           *)
  11. (*  This is NOT a complete module ready to link up with a    *)
  12. (*  driver program.        PRB 10/90                         *)
  13. (*************************************************************)
  14. PROGRAM TreeMod(Input,Output);
  15.  
  16.   TYPE  DataType = Real;
  17.         NodePointer = ^NodeRec;
  18.         NodeRec= RECORD
  19.                    Data: DataType;
  20.                    Level: 0..Maxint;
  21.                    LeftLink,RightLink: NodePointer;
  22.                  END;
  23.         AverageOfTree  = Array [0..25] of Integer;
  24.         StoreAverage = Array [1..50] of real;
  25.         Maxlevel = Array [1..50] of Integer;
  26.  
  27.  
  28.  
  29.   VAR   Root,CurrentNode: NodePointer;
  30.         Seed,Seedy,
  31.         NumofTrees,
  32.         P : Integer;
  33.         TotalAve : Real;
  34.         DataIn: DataType;
  35.         Max : Maxlevel;
  36.         Storeave:storeaverage;
  37.         Ave : AverageOfTree ;
  38.  
  39. (***************************************************)
  40. (*  Generates a random number ( 0 <= R < 1 )       *)
  41. (*  Seed must be initialized ONCE before using     *)
  42. (***************************************************)
  43. FUNCTION Random(VAR Seed: Integer): Real;
  44.   CONST Modulus = 65536;
  45.         Multiplier = 25173;
  46.         Increment = 13849;
  47.  
  48.   BEGIN
  49.   Seed:=((Multiplier*Seed) + Increment) MOD Modulus;
  50.   Random:= Seed/Modulus;
  51.   END;
  52. (***************************************************)
  53. (* Disposes of the nodes of an existing, unneeded  *)
  54. (* Tree.  Recursively called in postorder.        *)
  55. (***************************************************)
  56. PROCEDURE DisposeTree(VAR CurrentNode:NodePointer);
  57. BEGIN
  58.   WITH CurrentNode^ DO
  59.     BEGIN
  60.     IF LeftLink <> NIL THEN
  61.       DisposeTree(LeftLink);
  62.     IF RightLink <> NIL THEN
  63.       DisposeTree(RightLink);
  64.     DisposeTree(CurrentNode);
  65.   END;
  66. END;
  67. (***************************************************)
  68. (*  Recursively searches for node to insert DataIn *)
  69. (*  Inserts data DataIn into a tree in order       *)
  70. (***************************************************)
  71. PROCEDURE AddaNode(VAR Current: NodePointer;
  72.                            DataIn: DataType;
  73.                              CurrentLevel: Integer);
  74. BEGIN
  75. IF Current = nil THEN     (* Place is found *)
  76.   BEGIN
  77.   New(Current);
  78.   Current^.Data:= DataIn;
  79.   Current^.Level:= CurrentLevel;
  80.   Current^.LeftLink:= nil;
  81.   Current^.RightLink:= nil;
  82.   END
  83. ELSE                    (* Search farther *)
  84.   IF (DataIn < Current^.Data) THEN
  85.     AddaNode(Current^.LeftLink, DataIn, CurrentLevel+1)
  86.   ELSE
  87.     AddaNode(Current^.RightLink, DataIn,CurrentLevel+1); (* Duplicate keys   *)
  88. END;                                                     (* are inserted in  *)
  89.                                                          (* original order   *)
  90. (**************************************)
  91. (*                                    *)
  92. (**************************************)
  93.   PROCEDURE FormTree(VAR Root:NodePointer);
  94.     CONST NumberofNodes = 127;
  95.     VAR I: Integer;
  96.         DataIn: DataType;
  97.   (*************************************)
  98.   (*  Currently randomly generated     *)
  99.   (*************************************)
  100.   PROCEDURE GetData(VAR DataIn: DataType);
  101.     BEGIN
  102.     DataIn:=100*Random(Seed)+1;
  103.     END;
  104.  
  105. BEGIN (* FormTree *)
  106. Root:= nil;
  107. FOR I:= 1 TO NumberofNodes DO
  108.   BEGIN
  109.   GetData(DataIn);
  110.   AddaNode(Root, DataIn, 0);
  111.   END;
  112. END;
  113. (**********************************************)
  114. (*  ShowTree   Recursively displays a tree    *)
  115. (*             in L-R order.                  *)
  116. (**********************************************)
  117. PROCEDURE ShowTree(CurrentNode: NodePointer);
  118.  
  119. BEGIN
  120. WITH CurrentNode^ DO
  121.   BEGIN                     (* Reversed for rotated display *)
  122.   IF RightLink<> nil THEN
  123.     ShowTree(RightLink);
  124.   Writeln('   ',Trunc(Data):3*(1+Level));
  125.   IF LeftLink<>nil THEN
  126.     ShowTree(LeftLink);
  127.   END;
  128. END;
  129.  
  130. (*****************************************************************)
  131. (* This Procedure puts the level of each node into an array      *)
  132. (*****************************************************************)
  133.  
  134. Procedure FindAve (Current : NodePointer;
  135.                   Var Ave :AverageOfTree ;
  136.                   VAR StoreAve:StoreAverage;
  137.                   NumofTrees:Integer);
  138.     Var  C,Total, Levels : Integer;
  139.          TreeAve : Real;
  140.  
  141.    Begin
  142.     With Current^ do
  143.      Begin
  144.       IF rightlink <> Nil then
  145.           FindAve (rightlink,Ave,StoreAve,NumofTrees);
  146.       Ave[level] := Ave[level] + 1;
  147.        IF leftlink <> Nil then
  148.          FindAve(leftlink,ave,StoreAve,NumofTrees);
  149.        Total := 0;
  150.        For C := 1 to 25  do
  151.         Begin
  152.          Levels := Ave[C] * C;
  153.          Total := Total + levels;
  154.         End;
  155.        Treeave := Total / 127;
  156.        StoreAve[NumofTrees] := TreeAve;
  157.  
  158.      End;
  159.     End;
  160.  
  161. (**************************************************************)
  162. (* This procedure finds the maximum level for each tree       *)
  163. (**************************************************************)
  164.  
  165. Procedure FindMax (Ave: AverageOfTree ; Var Max : Maxlevel; NumofTrees: Integer);
  166.  
  167.        Var I, Maximum: Integer;
  168.  
  169.     Begin
  170.      I := 26;
  171.      Repeat
  172.      I := I - 1;
  173.      Maximum := I;
  174.        until ave[I] <> 0;
  175.     Max[NumofTrees] := maximum;
  176.     End;
  177.  
  178.  
  179.  
  180.  
  181.  
  182. BEGIN   (*************  MAIN *************)
  183.   (* Initialize *)
  184.   Seed := 0;
  185.   (* Describe *)
  186.   Write('Enter a Seed value for the random generator: ');
  187.   Readln(Seedy);
  188.  
  189.   For NumofTrees := 1 to 50 do
  190.    Begin
  191.     Seed := NumofTrees * Seedy;
  192.     FormTree(Root);
  193.     FindAve(Root,Ave,StoreAve,NumofTrees);
  194.     FindMax(Ave,Max,NumofTrees);
  195.     For p := 1 to 25 do
  196.       Ave[p]:=0;
  197.    End;
  198.   Writeln;
  199.   Writeln('Maximum Level        Average Level');
  200.   Writeln;
  201.   For P := 1 to 50 do
  202.    Begin
  203.    Writeln(Max[P]:4,'           ',StoreAve[P]:4:2);
  204.    TotalAve := TotalAve + StoreAve[P];
  205.   End;
  206.    TotalAve := TotalAve / 50;
  207.    Writeln('The average level for 50 trees is: ',TotalAve:4:2);
  208. END.
  209.