tree_insert Subroutine

public recursive subroutine tree_insert(t, number)

NAME

tree_insert(3f) - [M_sort:sort:treesort] sort a number of integers by building a
                  tree, sorted in infix order
(LICENSE:MIT)

SYNOPSIS

subroutine tree_insert(t,number)

type(tree_node), pointer :: t
integer             :: number

DESCRIPTION

Sorts a number 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.

AUTHOR

Copyright (c) 1990 by Walter S. Brainerd, Charles H. Goldberg, and Jeanne C. Adams. This code may be copied and used without restriction as long as this notice is retained.

EXAMPLE

sample program

program tree_sort
use M_sort, only : tree_node, tree_insert, tree_print
implicit none
type(tree_node), pointer :: t     ! A tree
integer             :: number
integer             :: ios
nullify(t)                        ! Start with empty tree
infinite: do
   read (*,*,iostat=ios) number
   if(ios.ne.0)exit infinite
   call tree_insert(t,number)     ! Put next number in tree
enddo infinite
call tree_print(t)                ! Print nodes of tree in infix order
end program tree_sort

Arguments

Type IntentOptional Attributes Name
type(tree_node), pointer :: t
integer, intent(in) :: number

Source Code

recursive subroutine tree_insert (t, number)
implicit none

! ident_61="@(#) M_sort tree_insert(3f) sort a number of integers by building a tree sorted in infix order"

type (tree_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
      nullify (t % left)
      nullify (t % right)
      ! otherwise, insert into correct subtree
   else if (number < t % value) then
      call tree_insert (t % left, number)
   else
      call tree_insert (t % right, number)
   endif
end subroutine tree_insert