1.2.19.6. Trees

An efficient sorting program can be constructed using a data structure that is a binary tree. The resulting program, tree_sort, has an expected running time proportional to n log₂ n.

It is quite difficult to write nonrecursive programs to process trees, so we will think of trees as recursive structures. Using this approach, a binary tree of integers is either empty or an integer, followed by two binary trees of integers, called the left subtree and right subtree.

Sorting with Trees

To sort numbers with a tree, we will construct a special kind of ordered binary tree with the property that the number at the top or root node of the tree is greater than all the numbers in its left subtree and less than or equal to all the numbers in its right subtree. This property will hold not only for the most accessible node at the top of the tree, but for all nodes of the tree.

The sorting process consists of inserting the values to be sorted, one at a time, into the tree (after starting with and empty tree) and then printing the values in the tree in the correct (infix) order.

Type Declarations for Trees

The declaration for the node of a tree must contain two pointers, one to the left subtree and

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

The subroutine that inserts a new number into the tree is a straightforward implementation of the following informal recipe: If the tree is empty, make the new entry the only node of the tree; if the tree is not empty and the number to be inserted is less than the number at the root, insert the number in the left subtree; otherwise, insert the number in the right subtree.

The recipe for printing the nodes of the tree follows from the way the tree has been built: It is simply to print in order the values in the left subtree of the root, print the value at the root node, and then print in order the values in the right subtree. This subroutine is shown in the following complete module and program that sort a file of integers by reading them all in, constructing an ordered binary tree, and then printing out the values in the tree in order:

   module tree_module

   public :: insert, print_tree

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

   contains

     recursive subroutine insert (t, number)

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

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

     end subroutine insert
     recursive subroutine print_tree (t)
     ! Print tree in infix order

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

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

     end subroutine print_tree

   end module tree_module

   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.

      use tree_module

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

      t => null () ! Start with empty tree
      do
        read (unit = *, fmt = *, iostat = ios) number
        if (ios < 0) then
           exit
        end if
        call insert (t, number) ! Put next number in tree
      end do
      ! Print nodes of tree in infix order
      call print_tree (t)

   end program tree_sort

1.2.20. Input and Output

The input/output statements are

read

print

write

open

close

inquire

backspace

endfile

rewind

The read, write, and print statements are the ones that do the data transfer; the open and close statements deal with the connection between an input/output unit and a file; the inquire statement provides the means to find out things about a file or unit; and the backspace, endfile, and rewind statements affect the position of the file.

Input and output operations deal with collections of data called files. The data in files are organized into records, which may correspond to lines on a computer terminal, lines on a printout, or parts of a disk file. The descriptions of records and file are to be considered abstractions and do not necessarily represent the way data is stored physically on any particular device.