(*  This program builds a binary tree of characters from
user input data and prints out the nodes of a tree in
infix, prefix, and postfix notation.  An input line con-
sists of the character, its position in the tree, and the
position of its two children; each item is separated from
the next by a blank.  

Variables -
   MaxNumNodes - maximum number of nodes in a tree
   One - index of the root
   NodeCharacter - constitutes a node in the tree
   NodeIndex - position of node in the tree
   ExpressionTree - binary tree which is created
   DataFile - file which holds user data    *)

program TreeTraversal(Input,Output);

const  MaxNumNodes = 20;
       One = 1;

type   Subscr = 0..MaxNumNodes;
       Node = record
              Symbol : char;
              Left : Subscr;
              Right : Subscr
              end;
       Tree = array[Subscr] of node;

var    NodeCharacter : char;
       NodeIndex : integer;
       ExpressionTree : Tree;
       DataFile : text;

(* ---------------------------------------------------*)
procedure BuildTree;    (* build tree from user input *)
var FindRoot : boolean; 

    procedure AddNode;  (* add a node to the tree *)
    begin 
        write(NodeCharacter : 3, NodeIndex: 3);
        with ExpressionTree[NodeIndex] do begin
            Symbol:=NodeCharacter;  
            read(DataFile,Left); write(Left : 3); 
            read(DataFile,Right); write(Right : 3);
            readln(DataFile);
            writeln
            end   
    end; (* AddNode *)

begin 
    FindRoot := false;
    writeln('INPUT IS:'); writeln;
    AddNode;
    repeat
        read(DataFile,NodeCharacter,NodeIndex); 
        if NodeIndex = 1 then FindRoot := true
        else AddNode
    until (FindRoot) or (eof(DataFile));
    writeln               
end; (* BuildTree *)

(* -------------------------------------------------- *)
procedure Infix(NodeIndex : Subscr); (* write out the
       tree in infix notation *)
begin
    with ExpressionTree[NodeIndex] do 
        if Left <> 0 then begin
            write('(' : 1);                      
            Infix(Left);
            write(Symbol : 2);
            Infix(Right);
            write(')' : 1)
            end (* if *)
        else write(Symbol : 2)
end; (* Infix *)

(* -------------------------------------------------- *)
procedure Prefix(NodeIndex : Subscr); (* write out the
       tree in prefix notation *)
begin
    with ExpressionTree[NodeIndex] do 
        if Left <> 0 then begin
            write(Symbol : 2);
            Prefix(Left); 
            Prefix(Right) 
            end   (* if *)
        else write(Symbol : 2)
end; (* Prefix *)

(* -------------------------------------------------- *)
procedure Postfix(NodeIndex : Subscr); (* write out the
       tree in postfix notation *)
begin 
    with ExpressionTree[NodeIndex] do 
        if Left <> 0 then begin
            Postfix(Left);
            Postfix(Right); 
            write(Symbol : 2)
            end (* if *)                                 
        else write(Symbol : 2)
end; (* Postfix *)

(* -------------------------------------------------- *)
(* The main program reads in user data and displays the
   tree in Infix, Prefix, and Postfix notation. *)

begin (* TreeTraversal *)
    reset(DataFile,':F1:DATA2'); 
    writeln; writeln; writeln;
    read(DataFile,NodeCharacter,NodeIndex);
    while not eof(DataFile) do begin
        BuildTree; 
        writeln; writeln('INFIX:');
        Infix(One); 
        writeln; writeln('PREFIX:');
        Prefix(One);
        writeln; writeln('POSTFIX:');
        Postfix(One);
        writeln; writeln
        end;
    writeln; writeln
end. (* TreeTraversal *)
