! Copyright (c) 1994 Unicomp, Inc.
!
! Developed at Unicomp, Inc.
!
! Permission to use, copy, modify, and distribute this
! software is freely granted, provided that this notice 
! is preserved.

program tree_sort
! Sorts a file of integers by building a
! tree, sorted in infix order.
! This sort has expected behavior n log n,
! but worst case (input is sorted) n ** 2.

   implicit none
   type node
      integer :: value
      type (node), pointer :: left, right
   end type node

   type (node), pointer :: t  ! A tree
   integer :: number, ios

   nullify (t)  ! Start with empty tree
   do
      read (*, *, iostat = ios) number
      if (ios < 0) exit
      call insert (t) ! Put next number in tree
   end do
   ! Print nodes of tree in infix order
   call print (t)

contains

   recursive subroutine insert (t)

      type (node), pointer :: t  ! A tree

      ! If (sub)tree is empty, put number at root
      if (.not. associated (t)) then
         allocate (t)
         t % value = number
         nullify (t % left)
         nullify (t % right)
      ! Otherwise, insert into correct subtree
      else if (number < t % value) then
         call insert (t % left)
      else
         call insert (t % right)
      end if

   end subroutine insert

   recursive subroutine print (t)
   ! Print tree in infix order

      type (node), pointer :: t  ! A tree

      if (associated (t)) then
         call print (t % left)
         print *, t % value
         call print (t % right)
      end if

   end subroutine print

end program tree_sort