home *** CD-ROM | disk | FTP | other *** search
/ ftp.barnyard.co.uk / 2015.02.ftp.barnyard.co.uk.tar / ftp.barnyard.co.uk / cpm / walnut-creek-CDROM / CPM / LANGUAGS / MODULA2 / TREE.MOD < prev    next >
Text File  |  2000-06-30  |  2KB  |  101 lines
  1. (* Insertion and deletion in a binary tree.  Read a sequence
  2.    of integers.  A positive integer signifies that it should
  3.    be inserted in an ordered binary tree as the key of a node.
  4.    A negative integer signifies that a node with its absolute
  5.    value as key should be searched and deleted. *)
  6.  
  7. MODULE tree;
  8.  
  9. FROM Storage  IMPORT ALLOCATE;
  10. FROM InOut IMPORT WriteString, WriteCard, WriteLn, ReadInt, WriteInt;
  11.  
  12. TYPE ref = POINTER TO word;
  13.      word = RECORD
  14.             key : CARDINAL;
  15.             count : CARDINAL;
  16.             left, right : ref;
  17.             END;
  18.  
  19. VAR root : ref;
  20.     k : INTEGER;
  21.  
  22. PROCEDURE printTree(w : ref; l : CARDINAL);
  23. VAR i : CARDINAL;
  24. BEGIN
  25.   IF w # NIL THEN
  26.     WITH w^ DO
  27.       printTree(left, l+1);
  28.       FOR i := 1 TO l DO
  29.         WriteString("   ");
  30.       END;
  31.       WriteCard(key,6);
  32.       WriteLn;
  33.       printTree(right, l+1);
  34.     END; (* with *)
  35.   END; (* if *)
  36. END printTree;
  37.  
  38. PROCEDURE search(x : CARDINAL; VAR p : ref);
  39. BEGIN
  40.   IF p = NIL THEN (* word is not in tree; insert it *)
  41.   NEW(p);
  42.   WITH p^ DO
  43.    key := x;
  44.    count := 1;
  45.    left := NIL;
  46.    right := NIL;
  47.   END; (* with *)
  48.   ELSIF x<p^.key THEN search(x, p^.left)
  49.   ELSIF x > p^.key THEN search(x,p^.right)
  50.   ELSE p^.count := p^.count + 1;
  51.   END;
  52. END search;
  53.  
  54. PROCEDURE delete(x : CARDINAL; VAR p : ref);
  55. VAR q : ref;
  56.   PROCEDURE del(VAR r : ref);
  57.   BEGIN
  58.     IF r^.right # NIL THEN
  59.      del(r^.right)
  60.     ELSE
  61.      q^.key := r^.key; 
  62.      q^.count := r^.count;
  63.      q := r;
  64.      r := r^.left;
  65.     END;
  66.   END del;
  67.  
  68. BEGIN (* delete *)
  69.   IF p = NIL THEN
  70.     WriteString(" word is not in tree");
  71.     WriteLn;
  72.   ELSIF x < p^.key THEN delete(x, p^.left)
  73.   ELSIF x > p^.key THEN delete(x,p^.right)
  74.   ELSE
  75.     q := p;
  76.     IF q^.right = NIL THEN p := q^.left
  77.     ELSIF q^.left = NIL THEN p := q^.right
  78.     ELSE del(q^.left);
  79.     END;
  80.   END;
  81. END delete;
  82.  
  83. BEGIN (*main*)
  84.   root := NIL;
  85.   ReadInt(k);
  86.   WHILE k # 0 DO
  87.    IF k > 0 THEN
  88.      WriteString(" insert");
  89.      WriteInt(k,6);
  90.      search(k,root);
  91.    ELSE
  92.      WriteString(" delete");
  93.      WriteInt(0-k,6);
  94.      delete(CARDINAL(0-k), root);
  95.    END;
  96.    printTree(root,0);
  97.    ReadInt(k);
  98.   END; (*while *)
  99. END tree.
  100.  
  101.