program postord (infile1,output);

{ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

      TREE ADT  -  DECLARATIONS}

type
  infotype = integer;
  list = ^listype;
  position = list;
  listype = record
              info: infotype;
              next: list
            end;
  tree = ^nodetype;
  nodeposition = tree;
  nodetype = record
               info: infotype;
               child: list;
               next: tree
             end;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

var
  infile1: text;
  T: tree;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

       LIST ADT (WITHOUT HEADER)  -  CODE}

function FIRST (var L: list): position;
  begin
    FIRST:=L
  end;
function ENDLIS (L: list): position;
  begin
    ENDLIS:= nil
  end;
function NEXT (p: position; L:list): position;
  begin
    NEXT:= p^.next
  end;
function LOCATE (x: infotype; L: list): position;
  var
    p: position;
    found: boolean;
  begin
    p:= L;
    found:= false;
    while ((p<>nil) and (not found)) do
      if p^.info = x
        then
          found:= true
        else
          p:= p^.next;
    LOCATE:= p
  end;
function RETRIEVE (p: position; L: list): infotype;
  begin
    RETRIEVE:= p^.info
  end;
procedure DELETE (var p: position; var L: list);
  var
    s,t: position;
  begin
    if p=L
      then
        begin
          L:= L^.next;
          p:= L
        end
      else
        begin
          s:= L;
          t:= L^.next;
          while t<>p do
            begin
              s:= s^.next;
              t:= t^.next
            end;
          s^.next:= p^.next;
          s:= p;
          p:= p^.next;
          dispose (s)
        end
  end;
procedure MAKENULLIS (var L: list);
  begin
    L:=nil
  end;
procedure INSERT (x: infotype; p: position; var L: list);
  var
    q, s, t: position;
  begin
    new(q);
    q^.info:=x;
    if p=L
      then
        begin
          q^.next:= L;
          L:=q
        end
      else
        begin
          s:= L;
          t:= L^.next;
          while t<>p do
            begin
              s:= s^.next;
              t:= t^.next
            end;
          s^.next:= q;
          q^.next:= p
        end
  end;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

        TREE ADT  -  CODE}

function LOCATENODE (x: infotype; T: tree): nodeposition;
  var
    p: nodeposition;
    found: boolean;
  begin
    p:= T;
    found:= false;
    while ((p<>nil) and (not found)) do
      if p^.info = x
        then
          found:= true
        else
          p:= p^.next;
    LOCATENODE:= p
  end;
function LEFTMOST_CHILD (n: nodeposition; T: tree): nodeposition;
  var
    L: list;
  begin
    L:= n^.child;
    if FIRST(L)=ENDLIS(L)
      then
        LEFTMOST_CHILD:= nil
      else
        LEFTMOST_CHILD:= LOCATENODE(RETRIEVE (FIRST(L), L), T)
  end;
function RIGHT_SIBLING (n: nodeposition; T:tree): nodeposition;
  var
    p: nodeposition;
    p2: position;
    L: list;
    found: boolean;
  begin
    p:= T;
    found:= false;
    while ((p<>nil) and (not found)) do
      begin
        L:= p^.child;
        p2:= LOCATE (n^.info, L);
        if p2<>ENDLIS(L)
          then
            found:= true;
        p:= p^.next
      end;
    if found
      then
        begin
          p2:= NEXT (p2, L);
          if p2<>ENDLIS(L)
            then
              RIGHT_SIBLING:= LOCATENODE(RETRIEVE (p2, L), T)
            else
              RIGHT_SIBLING:= nil {n IS the RIGHTMOST SIBLING so it has no
                                 right sibling ! !}
        end
      else
        RIGHT_SIBLING:= nil {n must be the root - so it has no right sibling!}
  end;
function ROOT (T: tree): nodeposition;
  begin
    ROOT:= T
  end;
procedure MAKENULLT (var T: tree);
  begin
    T:= nil
  end;
procedure INSERTNODE (x: infotype; p: nodeposition; var T: tree);
  var
    n,q: nodeposition;
  begin
    new(q);
    q^.info:= x;          
    q^.next:= nil;
    MAKENULLIS(q^.child);
    if p=nil
      then
        T:= q
      else
        begin
          INSERT(x, ENDLIS(p^.child), p^.child);
          n:= T;
          while n^.next<>nil do
            n:= n^.next;
          n^.next:= q
        end
  end;
function NODELABEL (n: nodeposition; T: tree): infotype;
  begin
    NODELABEL:= n^.info
  end;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

procedure read_in (var f: text; var T: tree);
    {read_in reads the input text file and puts the elements in tree T.
     Each line consists of one single digit integer for the tree node
     information, a space and then the tree node information of it's parent.
     a zero for the parent information signals the root node.}
  var
    i,p : infotype;
  begin
    MAKENULLT(T);
    while not eof(f) do
      begin
        readln (f,i,p);
        writeln (i:4,p:4);
        INSERTNODE (i, LOCATENODE (p,T), T);
      end
  end;

procedure POSTORDER (n: nodeposition; T: tree);
  var
    c: nodeposition;
  begin
    c:= LEFTMOST_CHILD(n, T);
    while c<>nil do
      begin
        POSTORDER(c, T);
        c:= RIGHT_SIBLING(c, T)
      end;
    write (NODELABEL (n, T):4)
  end;

{     *  *  *     MAIN PROGRAM CODE STARTS HERE    *  *  *}

begin
  reset (infile1);
  read_in (infile1,T);
  writeln;
  writeln ('POST ORDER LISTING OF THE NODES FOLLOWS:');
  writeln;
  POSTORDER (T,T)
end.