# Building a Tree with a Recursive Function

Page 1 of 1

## 0 Replies - 1427 Views - Last Post: 25 November 2007 - 02:26 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=38138&amp;s=a53b0e87f53ed05b47e13548ca3d29c4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 bobby19

Reputation: 0
• Posts: 2
• Joined: 21-November 07

# Building a Tree with a Recursive Function

Posted 25 November 2007 - 02:26 PM

Hey,

I am building a BSP tree using a recursive function, however, I seem to be stuck in getting out of the function. I'll paste my code and explain along the way:

```module tree
type treenode
type (treenode), pointer :: left, right
integer :: n
real :: data
endtype

type (treenode), pointer :: root
real :: tree_xmin, tree_xmax
! Counters
integer :: nodes, work

contains
function create_node( ) result (node)
type (treenode), pointer :: node
integer :: ierr
allocate( node, stat=ierr )
if (ierr .ne. 0) then
print *, "Allocate Failed"
stop
endif
nullify( node%right )
nullify( node%left )
node%n = 0
end function create_node

```

This code was given to us. Just the definition for the treenone and a create_node function

```  integer function partition_data( xdata, xmiddle )
implicit none

real,INTENT(INOUT), dimension(:) :: xdata !Data Array
real,INTENT(IN) :: xmiddle

integer ::  l = 1, i
integer ::  r = 16
real :: temp

do

if (xdata(l) < xmiddle) then !Data Value less than middle
if (l == r) then
partition_data = l
return
end if

l = l + 1 !Increment Counter

else

do
if (xdata(r) >= xmiddle) then
if (l == r) then
partition_data = (l - 1)
return
end if

r = r -1

else

temp = xdata(l)
xdata(l) = xdata(r)
xdata(r) = temp
exit

end if
end do

end if

end do

end function partition_data

```

This code I wrote. Essentially, it takes in a set array (given) and partitions the array so that any values lower than the x middle value are put to the left and value greater are put to the right. Then the function returns the array index of the element to the left of the xmiddle value. I have tested this function by itself, and it works fine and gives the expected results.

```recursive function make_node( xdata, xmin, xmax ) result (node)
implicit none
type (treenode), pointer :: node
real, intent(inout) :: xdata(:)
real, intent(inout) :: xmin, xmax
real :: xmiddle
integer :: p, i, arraySize

REAL, ALLOCATABLE, DIMENSION(:) :: newArray1, newArray2

node => create_node()

xmiddle = ((xmin + xmax) / 2)

arraySize = size(xdata)
print *, "The arraysize is ", arraysize

if (arraySize  == 1 ) then
node%data = xdata(1)
node%n = 1

else

p = partition_data(xdata, xmiddle)
print *, "THe partition value is", p
print *, "THe xmiddle value is ", xmiddle

ALLOCATE(newArray1(p)) !Allocate memory for the LEFT array

do i = 1,p !Copy data from xdata to newarray1
newArray1(i) = xdata(i)
enddo

print *, newArray1(1:p)

node%left => make_node(newArray1, xmin, xmiddle)

!	   ALLOCATE(newArray2((p+1):arraySize)) !Allocate memory for the RIGHT array

!	   do i = (p+1),arraySize !COpy data from xdata to newarray2
!		  newArray2(i) = xdata(i)
!	   enddo

!	   node%right => make_node(newArray2, xmiddle, xmax)

end if
!
end function make_node

```

This part I also wrote myself. (There are some print statements and commented out code for debugging purposes) This recursive function is used to make the nodes. The problem I am having is that this function never seems to hit the case where arraysize is equal to one. The parition value always stays constant and the new array that is suppose to be sent in, does not get changed. Tracing it out on paper, the function seems like it should work.

```  subroutine build_tree( xdata, xmin, xmax )
implicit none
real, intent(inout)  :: xdata(:)
real, intent(in)  :: xmin, xmax

if (size(xdata) == 0) then
print *, "No data provided"
return
endif

tree_xmin = xmin
tree_xmax = xmax
root => make_node( xdata, tree_xmin, tree_xmax )
end subroutine build_tree
end module tree

```

This was the build_tree subroutine given to us.

```program treetest
use tree
implicit none
integer, parameter :: ndata = 16
real, target :: xdata(ndata)
integer ::  partition_value, i
real :: xpartition = 0.7
!  call random_number( xdata )
xdata = (/ 0.00392, 0.0251, 0.453, 0.667, 0.963, 0.838, 0.335, 0.975, &
0.796, 0.833, 0.345, 0.871, 0.0899, 0.888, 0.701, 0.735 /)

nodes = 0
! call build_tree( xdata, 0.0, 1.0 )
print *,"Tree Built: nodes ",nodes

print *, xdata(1:16)

partition_value = partition_data(xdata, xpartition)

print *, "The partition value is ", partition_value
print *, "The partitioned array is "
do i=1,16
print *, xdata(i)
end do

end program treetest

```

This is the main driver program.

I apologize for the length of this post, however, any help at all would be appreciated. This is the only forum I can find offering Fortran help.

Thanks!

This post has been edited by bobby19: 25 November 2007 - 02:27 PM

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }