home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / compiler / taylmod2 / tree.mod < prev   
Text File  |  1988-06-30  |  2KB  |  94 lines
  1. MODULE Tree;
  2.  
  3. FROM SYSTEM IMPORT TSIZE;
  4.  
  5. FROM InOut IMPORT WriteString, WriteCard, WriteLn;
  6. FROM Storage IMPORT ALLOCATE;
  7.  
  8. CONST  Iterations = 4000;
  9.  
  10. TYPE   Ptr  = POINTER TO Node;
  11.        Node = RECORD
  12.                 key:   CARDINAL;
  13.                 left,
  14.                 right: Ptr
  15.               END;
  16.  
  17. VAR    root:       Ptr;
  18.        x,
  19.        i,
  20.        seed,
  21.        Nodes,
  22.        Duplicates: CARDINAL;
  23.  
  24. PROCEDURE Search (x: CARDINAL);
  25.  
  26. VAR    p, q: Ptr;
  27.  
  28. BEGIN
  29.  
  30.   p := root;
  31.   q := NIL;
  32.   WHILE p # NIL DO
  33.     q := p;
  34.     IF x < p^.key THEN
  35.       p := p^.left
  36.     ELSIF x > p^.key THEN
  37.       p := p^.right
  38.     ELSE
  39.       INC (Duplicates);
  40.       RETURN
  41.     END
  42.   END;
  43.   ALLOCATE (p, TSIZE (Node));
  44.   p^.key   := x;
  45.   p^.left  := NIL;
  46.   p^.right := NIL;
  47.   IF q = NIL THEN
  48.     root := p
  49.   ELSIF x < q^.key THEN
  50.     q^.left := p
  51.   ELSE
  52.     q^.right := p
  53.   END
  54.  
  55. END Search;
  56.  
  57. PROCEDURE Traverse (ptr: Ptr);
  58.  
  59. BEGIN
  60.  
  61.   IF ptr # NIL THEN
  62.     Traverse (ptr^.left);
  63.     INC (Nodes);
  64.     Traverse (ptr^.right)
  65.   END
  66.  
  67. END Traverse;
  68.  
  69. PROCEDURE Random (): CARDINAL;
  70.  
  71. BEGIN
  72.  
  73.   seed := (seed * 13 + 29) MOD 2503;
  74.   RETURN seed
  75.  
  76. END Random;
  77.  
  78. BEGIN  (* Tree *)
  79.  
  80.   WriteString ('Binary Tree creation and traversal');  WriteLn;
  81.   WriteCard (Iterations, 5);  WriteString (' Iterations');  WriteLn;
  82.   root := NIL;
  83.   Duplicates := 0;
  84.   Nodes      := 0;
  85.   seed       := 0;
  86.   FOR i := 1 TO Iterations DO
  87.     Search (Random ())
  88.   END;
  89.   Traverse (root);
  90.   WriteCard (Duplicates, 5);  WriteString (' Duplicates');  WriteLn;
  91.   WriteCard (Nodes, 5);  WriteString (' Nodes');  WriteLn
  92.  
  93. END Tree.
  94.