! 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