tree_insert(3f) - [M_sort:sort:treesort] sort a number of integers by building a
tree, sorted in infix order
(LICENSE:MIT)
subroutine tree_insert(t,number)
type(tree_node), pointer :: t
integer :: number
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.
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.
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
Type | Intent | Optional | Attributes | Name | ||
---|---|---|---|---|---|---|
type(tree_node), | pointer | :: | t | |||
integer, | intent(in) | :: | number |
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