MODULE TREENODE
   TYPE NODE
	TYPE (NODE), POINTER :: LEFT
	INTEGER              :: INFO
	TYPE (NODE), POINTER :: RIGHT
   END TYPE NODE
END MODULE

PROGRAM TREESAMPLE
	USE TREENODE
	IMPLICIT NONE
	TYPE (NODE), POINTER  :: ROOT
	INTEGER COUNT,NUMNODE
        ! we include the interface for TREEPRINT here
	INTERFACE
	  RECURSIVE SUBROUTINE TREEPRINT(T, COUNT)
		USE TREENODE
		TYPE (NODE), POINTER :: T
		INTEGER COUNT
	  END SUBROUTINE
	  RECURSIVE FUNCTION GENTREE(N, NUMNODE) RESULT (T)
		USE TREENODE
		TYPE (NODE), POINTER :: T
		INTEGER N, NUMNODE
	  END FUNCTION
	END INTERFACE
	! (* initialization *)
	NUMNODE = 0
	COUNT = 0
	ROOT => GENTREE(16,NUMNODE)
	CALL TREEPRINT(ROOT, COUNT)
END PROGRAM

!* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
!*       F U N C T I O N   G E N T R E E                   *
!       This generates a tree.  n is a small positive integer
!	specifying an upper bound on the number of nodes
!	of the tree.  The nodes can have two children, and
!	an information field.  The information field is 
!*      given a sequential node number.                    *
!* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
RECURSIVE FUNCTION GENTREE(N, NUMNODE) RESULT (T)
	USE TREENODE
	IMPLICIT NONE
	INTEGER N, NUMNODE
	TYPE (NODE), POINTER ::T
	ALLOCATE(T)
	NUMNODE=NUMNODE+1 !numnode is the unique number
		          !stored in each node after its creation
	T%INFO = NUMNODE
	IF (N<=2) THEN
	   NULLIFY(T%LEFT)
	ELSE      
	   T%LEFT => GENTREE(N/2,NUMNODE)
	END IF
	IF (n<=2) THEN
	   NULLIFY(T%RIGHT)
	ELSE	
	   T%RIGHT => GENTREE(N/2,NUMNODE)
	END IF
END

!* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
!*      S U B R O U T I N E    T R E E P R I N T         *
!*	The information fields of the nodes of a tree
!	are printed so that the tree is rotated 90 degrees
!	counter-clockwise.  The nodes are given proper 
!*	depths.                                          *
!* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
RECURSIVE SUBROUTINE TREEPRINT(T, COUNT)
	USE TREENODE
	IMPLICIT NONE
	TYPE (NODE), POINTER :: T
	INTEGER COUNT, I
	COUNT = COUNT+1
                 !count serves as a counter of the depth
		 !of the node and permits the correct
		 !spacing before the node contents are printed.
	IF (ASSOCIATED(T)) THEN
		CALL TREEPRINT(T%RIGHT,COUNT)
		WRITE(6,*)("         ", i=0,COUNT-1), T%INFO
		CALL TREEPRINT(T%LEFT,COUNT)
	END IF
	COUNT=COUNT-1
END