home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PASCALA.ZIP / TREEMOD.PAS < prev   
Encoding:
Pascal/Delphi Source File  |  1980-01-01  |  4.0 KB  |  125 lines
  1. (*************************************************************)
  2. (*  Several procedures for binary tree processing are        *)
  3. (*  contained in the module below.                           *)
  4. (*  This is NOT a complete module ready to link up with a    *)
  5. (*  driver program.        PRB 10/90                         *)
  6. (*************************************************************)
  7. PROGRAM TreeMod(Input,Output);
  8.  
  9.   TYPE  DataType = Real;
  10.         NodePointer = ^NodeRec;
  11.         NodeRec= RECORD
  12.                    Data: DataType;
  13.                    Level: 0..Maxint;
  14.                    LeftLink,
  15.                    RightLink: NodePointer;
  16.                  END;
  17.  
  18.   VAR   Root: NodePointer;
  19.         Seed: Integer;
  20.         DataIn: DataType;
  21.  
  22. (***************************************************)
  23. (*  Generates a random number ( 0 <= R < 1 )       *)
  24. (*  Seed must be initialized ONCE before using     *)
  25. (***************************************************)
  26. FUNCTION Random(VAR Seed: Integer): Real;
  27.   CONST Modulus = 65536;
  28.         Multiplier = 25173;
  29.         Increment = 13849;
  30.  
  31.   BEGIN
  32.   Seed:=((Multiplier*Seed) + Increment) MOD Modulus;
  33.   Random:= Seed/Modulus;
  34.   END;
  35. (***************************************************)
  36. (* Disposes of the nodes of an existing, unneeded  *)
  37. (* Tree.  Recursively called in postorder.        *)
  38. (***************************************************)
  39. PROCEDURE DisposeTree(VAR CurrentNode:NodePointer);
  40.  
  41. BEGIN
  42. WITH CurrentNode^ DO
  43.   BEGIN
  44.   IF LeftLink<> nil THEN
  45.     DisposeTree(LeftLink);
  46.   IF RightLInk<> nil THEN
  47.     DisposeTree(RightLink);
  48.   Dispose(CurrentNode);
  49.   END;
  50. END;
  51. (***************************************************)
  52. (*  Recursively searches for node to insert DataIn *)
  53. (*  Inserts data DataIn into a tree in order       *)
  54. (***************************************************)
  55. PROCEDURE AddaNode(VAR Current: NodePointer;
  56.                            DataIn: DataType;
  57.                              CurrentLevel: Integer);
  58. BEGIN
  59. IF Current = nil THEN     (* Place is found *)
  60.   BEGIN
  61.   New(Current);
  62.   Current^.Data:= DataIn;
  63.   Current^.Level:= CurrentLevel;
  64.   Current^.LeftLink:= nil;
  65.   Current^.RightLink:= nil;
  66.   END
  67. ELSE                    (* Search farther *)
  68.   IF (DataIn < Current^.Data) THEN
  69.     AddaNode(Current^.LeftLink, DataIn, CurrentLevel+1)
  70.   ELSE                                            
  71.     AddaNode(Current^.RightLink, DataIn,CurrentLevel+1); (* Duplicate keys   *)
  72. END;                                                     (* are inserted in  *)
  73.                                                          (* original order   *)
  74. (**************************************)
  75. (*                                    *)
  76. (**************************************)
  77.   PROCEDURE FormTree(VAR Root:NodePointer);
  78.     CONST NumberofNodes = 15;
  79.     VAR I: Integer;
  80.         DataIn: DataType;
  81.   (*************************************)
  82.   (*  Currently randomly generated     *)
  83.   (*************************************)
  84.   PROCEDURE GetData(VAR DataIn: DataType);
  85.     BEGIN
  86.     DataIn:=100*Random(Seed)+1;
  87.     END;
  88.  
  89. BEGIN (* FormTree *)
  90. Root:= nil;
  91. FOR I:= 1 TO NumberofNodes DO
  92.   BEGIN
  93.   GetData(DataIn);
  94.   AddaNode(Root, DataIn, 0);
  95.   END;
  96. END;
  97. (**********************************************)
  98. (*  ShowTree   Recursively displays a tree    *)
  99. (*             in L-R order.                  *)
  100. (**********************************************)
  101. PROCEDURE ShowTree(CurrentNode: NodePointer);
  102.  
  103. BEGIN
  104. WITH CurrentNode^ DO
  105.   BEGIN                     (* Reversed for rotated display *)
  106.   IF RightLink<> nil THEN
  107.     ShowTree(RightLink);
  108.   Writeln('   ',Trunc(Data):3*(1+Level));
  109.   IF LeftLink<>nil THEN
  110.     ShowTree(LeftLink);
  111.   END;
  112. END;
  113.  
  114. BEGIN   (*************  MAIN *************) 
  115.   (* Initialize *)
  116.   (* Describe *)
  117.   Write('Enter seed for the Random function: ');
  118.   Readln(Seed);  Writeln;
  119.  
  120.   FormTree(Root);
  121.   Writeln;  Writeln;  Writeln;
  122.   ShowTree(Root);
  123.   DisposeTree(Root);
  124. END.
  125.