home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / simtel / sigm / vols000 / vol069 / tree2.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1984-04-29  |  3.4 KB  |  157 lines
  1. PROGRAM Tree2;
  2.     { Maintain a sorted list in a binary tree }
  3. TYPE
  4.     Tree = ^Node;
  5.     $STRING12 = STRING 12;
  6.     Node = RECORD
  7.         Name : $STRING12;
  8.         Left, Right : Tree
  9.         END;
  10.  
  11. VAR
  12.     k : $STRING12;
  13.     Root,t : Tree;
  14.     ch,c : CHAR;
  15.  
  16.     {--------------------------------------------}
  17. PROCEDURE InitTree (VAR  t : Tree);
  18.     { initialize the tree }
  19. BEGIN
  20.     t := NIL
  21. END;
  22.     {---------------------------------------------}
  23. PROCEDURE INSERT (VAR t : Tree;
  24.             k : $STRING12);
  25.     { insert k into the Tree t; if it is there
  26.         already then do nothing}
  27. BEGIN
  28.     IF t = NIL THEN 
  29.     BEGIN
  30.       NEW (t);
  31.       t^.Name := k;
  32.       t^.left := NIL;
  33.       t^.right := NIL
  34.     END
  35.     ELSE
  36.       IF k = t^.Name THEN
  37.         WRITELN (k,' already in tree')
  38.       ELSE
  39.         IF k < t^.Name THEN
  40.           Insert (t^.left, k)
  41.           ELSE
  42.           IF k > t^.Name THEN
  43.         Insert (t^.right, k)
  44. END;
  45.     {------------------------------------}
  46. PROCEDURE DeleteLeftMost (VAR t : Tree;
  47.               VAR DeleteName : $STRING12);
  48.     { delete the leftmost node in the tree t and
  49.         return its value in deleteName}
  50. BEGIN
  51.     IF t^.Left <> NIL THEN
  52.       DeleteLeftMost (t^.left, DeleteName)
  53.     ELSE
  54.       BEGIN
  55.         DeleteName := t^.Name;
  56.         t := t^.right
  57.       END
  58. END;
  59.     {------------------------------------}
  60. PROCEDURE DeleteRoot (VAR  t : Tree);
  61.     { deletes the root of the nonempty tree t by 
  62.       replacing it by its successor (or child)if
  63.       it has only one, or replacing its value by 
  64.       that of the leftmost descendant of the 
  65.       rightmost subtree}
  66. VAR
  67.     DeletedName : $STRING12;
  68. BEGIN
  69.     IF t^.left = NIL THEN
  70.       t := t^.right
  71.     ELSE
  72.       IF t^.right = NIL THEN
  73.         t := t^.left
  74.       ELSE
  75.         BEGIN
  76.         DeleteLeftMost (t^.right, DeletedName);
  77.         t^.Name := DeletedName
  78.         END
  79. END;
  80.     {--------------------------------------}
  81. PROCEDURE Delete (VAR t : Tree;
  82.            k : $STRING12);
  83.     {delete k from the tree t--if it is not
  84.      in the tree, do nothing}
  85. BEGIN
  86.     IF t = NIL THEN
  87.       WRITELN ( k, ' not in tree')
  88.     ELSE
  89.       IF k = t^.Name THEN
  90.         DeleteRoot (t)
  91.       ELSE
  92.         IF k < t^.Name THEN
  93.           Delete (t^.left, k)
  94.         ELSE
  95.         IF k > t^.Name THEN
  96.           Delete (t^.right, k)
  97. END;
  98.     {------------------------------------}
  99. PROCEDURE Preorder( p : Tree );
  100.     {prints data from left side of tree to right} 
  101. BEGIN
  102.     IF p <> NIL THEN
  103.     BEGIN
  104.         WRITELN( p^.Name );
  105.         Preorder( p^.Left );
  106.         Preorder( p^.Right )
  107.     END
  108. END;        {preorder}
  109.     {------------------------------------}
  110. PROCEDURE Inorder( p : Tree );
  111.     {prints data outer to inner of tree}
  112. BEGIN
  113.     IF p <> NIL THEN
  114.     BEGIN
  115.         Inorder( p^.Left );
  116.         WRITELN(p^.Name );
  117.         Inorder( p^.Right )
  118.     END
  119. END;        {inorder}
  120.     {-------------------------------------}
  121. PROCEDURE Postorder( p : Tree );
  122.     {prints data from leaves first then branchs'}
  123. BEGIN
  124.     IF p <> NIL THEN
  125.     BEGIN
  126.         Postorder( p^.Left );
  127.         Postorder( p^.Right );
  128.         WRITELN( p^.Name )
  129.     END
  130. END;        {postorder}
  131.     {--------------------------------------}
  132. BEGIN        { MAIN PROGRAM BLOCK }
  133.     InitTree (t);
  134.     WRITELN ('Type i (insert) or d (delete) followed ');
  135.     WRITELN ('      by a NAME ( "*" to Quit)');
  136.     READ (c);
  137.     WHILE (c = 'i') or (c = 'd') DO
  138.       BEGIN
  139.         READLN (k);
  140.         CASE c OF
  141.           'i' : Insert (t,k);
  142.           'd' : Delete (t,k)
  143.         END;
  144.         WRITELN; WRITELN;
  145.         Preorder(t); 
  146.         WRITELN;
  147.         Inorder(t);
  148.         WRITELN;
  149.         Postorder(t);
  150.         WRITELN;
  151.         WRITELN ('Type i (insert) or d (delete)');
  152.         WRITELN ('followed by an integer item, or');
  153.         WRITELN ('anything else to quit:  ');
  154.         READ (c)
  155.       END
  156. END.
  157.