home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
modula2
/
compiler
/
taylmod2
/
tree.mod
< prev
Wrap
Text File
|
1988-06-30
|
2KB
|
94 lines
MODULE Tree;
FROM SYSTEM IMPORT TSIZE;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
FROM Storage IMPORT ALLOCATE;
CONST Iterations = 4000;
TYPE Ptr = POINTER TO Node;
Node = RECORD
key: CARDINAL;
left,
right: Ptr
END;
VAR root: Ptr;
x,
i,
seed,
Nodes,
Duplicates: CARDINAL;
PROCEDURE Search (x: CARDINAL);
VAR p, q: Ptr;
BEGIN
p := root;
q := NIL;
WHILE p # NIL DO
q := p;
IF x < p^.key THEN
p := p^.left
ELSIF x > p^.key THEN
p := p^.right
ELSE
INC (Duplicates);
RETURN
END
END;
ALLOCATE (p, TSIZE (Node));
p^.key := x;
p^.left := NIL;
p^.right := NIL;
IF q = NIL THEN
root := p
ELSIF x < q^.key THEN
q^.left := p
ELSE
q^.right := p
END
END Search;
PROCEDURE Traverse (ptr: Ptr);
BEGIN
IF ptr # NIL THEN
Traverse (ptr^.left);
INC (Nodes);
Traverse (ptr^.right)
END
END Traverse;
PROCEDURE Random (): CARDINAL;
BEGIN
seed := (seed * 13 + 29) MOD 2503;
RETURN seed
END Random;
BEGIN (* Tree *)
WriteString ('Binary Tree creation and traversal'); WriteLn;
WriteCard (Iterations, 5); WriteString (' Iterations'); WriteLn;
root := NIL;
Duplicates := 0;
Nodes := 0;
seed := 0;
FOR i := 1 TO Iterations DO
Search (Random ())
END;
Traverse (root);
WriteCard (Duplicates, 5); WriteString (' Duplicates'); WriteLn;
WriteCard (Nodes, 5); WriteString (' Nodes'); WriteLn
END Tree.