{############################################################################
 # TREE ADT USING ARRAY            +---------------------------------------+
 # Shown here is a forest      f-->|    f.a              f.space       [i] |
 # 'f' with two trees present.     |   +----+     +---+-----------+---+    |
 # Tree 1 is at f.space[3], and    |   | 5  |-+   | 0 |  elem-t1  | 0 | 1  |
 # tree 2 is a single node tree    |   +----+ |   +---+-----------+---+    |
 # at f.space=4.                   |          |   | 0 |  elem-t1  | 0 | 2  |
 #                                 |          |   +---+-----------+---+    |
 # NOTE: 1) The user must include  |          |   | 2 |  elem-t1  | 1 | 3  |
 #          a file called TREE.TYP |          |   +---+-----------+---+    |
 #          that holds treelement, |          |   | 0 |  elem-t2  | 0 | 4  |
 #          et.al. In this file the|          |   +---+-----------+---+    |
 #          user may change the    |          +-> |   |           | 6 | 5  |
 #          meaning of the element.|              +---+-----------+---+    |
 #       2) The driver program     |              |   |           | 0 | max|
 #          should contain a file  |              +---+-----------+---+    |
 #          called TREE.EXT that   |              left   element  right    |
 #          contains all external  +---------------------------------------+
 #          funct/proc's of this 
 #          module.
 #       3) Final linkage consists of TREE and your particular Driver program
 #
 # by DAVE HEYLIGER - AMUS STAFF
 #
 # Last update : 08/27/85
 ############################################################################}

MODULE TREE;

{+--- This module implements a TREE adt.
 |  The operations provided are the following:
 |
 |
 |  tree_init_forest  - creates an empty forest
 |
 |  tree_create       - creates a single node tree
 |
 |  tree_empty        - returns the empty tree
 |
 |  tree_build        - links to trees to a new tree
 |
 |  tree_left         - returns left subtree of a given tree
 |
 |  tree_right        - returns right subtree of a given tree
 |
 |  tree_root_elem    - returns the root element of a tree
 |
 |  NOTE : TREE.PAS contains a traversal procedure. The origional
 |         code contained inorder, however, if a user desires to
 |         modify this to postorder or preorder, be sure to change
 |         TREE.EXT to contain the proper external procedure.
 +------------------------------------------------------------------}

{$I tree.typ}

procedure treeinitforest(var f: treeforest);
{+--- on entry - true
 |    on exit  - f is an empty forest
 +--------------------------------------}

var
  i: integer;

begin { tree_init_forest }
for i:=1 to max - 1 do
   f.space[i].right := i+1;
   f.space[max].right := 0;
   f.a := 1;
end; { tree_init_forest }


function treecreate(e: treelement; var f: treeforest): tree;
{+--- on entry - f was created previously
 |    on exit  - a single node tree is placed into the forest and returned
 +-------------------------------------------------------------------------}

var
  t: tree;

begin { tree_create }
if f.a = 0 then writeln('Module: tree, function: tree_create, no space')
           else begin { new tree }
                t := f.a;
                f.a := f.space[f.a].right;
                f.space[t].element := e;
                f.space[t].left := 0;
                f.space[t].right := 0;
                treecreate := t;
                end; { new tree }
end; { tree_create }


function treempty(f: treeforest): tree;
{+--- on entry - f has been initialized previously 
 |    on exit  - an empty tree is returned
 +--------------------------------------------------}

begin { tree_empty }
treempty := 0;
end; { tree_empty }


function treebuild(e: treelement; l,r: tree; var f:treeforest): tree;
{+---   entry - f initialized previously,  l,r are defined trees in f
 |     on exit  - a new tree t is constructed with e being the element of 
 |                the root and l,r being the left and right subtree 
 +------------------------------------------------------------------------}

var
  t: tree;

begin { tree_build }
t := treecreate(e,f);
f.space[t].left := l;
f.space[t].right := r;
treebuild := t;
end; { tree_build }


function treeleft(t: tree; f: treeforest): tree;
{+--- on entry - f was initialized previously, t is defined tree in f 
 |    on exit  - t's left subtree is returned
 +----------------------------------------------------------------------}

begin { tree_left }
treeleft := f.space[t].left;
end; { tree_left }


function treeright(t: tree; f: treeforest): tree;
{+--- on entry - f was previously initialized, t is defined tree in f
 |    on exit  - t's right subtree is returned
 +----------------------------------------------------------------------}

begin { tree_right }
treeright := f.space[t].right;
end; { tree_right }


function treerootelem(t: tree; f: treeforest): treelement;
{+--- on entry - f was previously initialized, t is defined and non empty in f
 |    on exit  - t's root element is returned
 +---------------------------------------------------------------------------}

begin { tree_root_elem }
treerootelem := f.space[t].element;
end; { tree_root_elem }


procedure treeinorder(t: tree; f: treeforest; var out: text);
{+--- on entry - f was initialized previously, t is defined in f,
 |               out is an opened file
 |    on exit  - t is traversed in inorder calling visit for each node element
 +---------------------------------------------------------------------------}

begin { tree_inorder }
if t <> treempty(f)
   then begin { non empty tree }
        write(out,'(');
        treeinorder(treeleft(t,f),f,out);
        visit(out,treerootelem(t,f));
        treeinorder(treeright(t,f),f,out);
        write(out,')');
        end; { non empty tree }
end; { tree_inorder }
.

.