Fortran递归树实现中的分段错误

Question

我需要在Fortran中为一个项目实现一个树结构，所以我已经在线阅读了各种指南，解释了如何实现它。但是，我不断收到错误或奇怪的结果。

比方说，我想建立一个二叉树，其中每个节点存储一个整数值。我也希望能够将新值插入树中并打印树的节点。所以我写了一个类型“树”，它包含一个整数，两个指向子树的指针和一个布尔值，我设置为.true。如果没有子树：

module class_tree 
implicit none 

type tree 
    logical :: isleaf 
    integer :: value 
    type (tree), pointer :: left,right 
end type tree 

interface new 
    module procedure newleaf 
end interface 

interface insert 
    module procedure inserttree 
end interface 

interface print 
    module procedure printtree 
end interface 

contains 

subroutine newleaf(t,n) 
    implicit none 
    type (tree), intent (OUT) :: t 
    integer, intent (IN) :: n 

    t % isleaf = .true. 
    t % value = n 
    nullify (t % left) 
    nullify (t % right) 
end subroutine newleaf 

recursive subroutine inserttree(t,n) 
    implicit none 
    type (tree), intent (INOUT) :: t 
    integer, intent (IN) :: n 
    type (tree), target :: tleft,tright 

    if (t % isleaf) then 
     call newleaf(tleft,n) 
     call newleaf(tright,n) 

     t % isleaf = .false. 
     t % left => tleft 
     t % right => tright 
    else 
     call inserttree(t % left,n) 
    endif 
end subroutine inserttree 

recursive subroutine printtree(t) 
    implicit none 
    type (tree), intent (IN) :: t 

    if (t % isleaf) then 
     write(*,*) t % value 
    else 
     write(*,*) t % value 
     call printtree(t % left) 
     call printtree(t % right) 
    endif 
end subroutine printtree 
end module class_tree 

除非尝试插入叶子，否则插入总是在左侧的子树中完成。在这种情况下，将插入操作完成到两个子树中，以确保节点总是有0个或2个子节点。打印是在前缀遍历中完成的。

现在，如果我尝试运行下面的程序：

program main 
use class_tree 
implicit none 
type (tree) :: t 

call new(t,0) 
call insert(t,1) 
call insert(t,2) 
call print(t) 
end program main 

我得到所需的输出0 1 2 2 1。但是如果我添加“呼叫插入（T，3）”后，“呼叫插入（ t，2）“并再次运行，输出为0 1 2 0，然后出现段错误。

我想看看插入或打印时是否发生了故障，所以我试图运行：

program main 
use class_tree 
implicit none 
type (tree) :: t 

call new(t,0) 
call insert(t,1) 
call insert(t,2) 
write(*,*) 'A' 
call insert(t,3) 
write(*,*) 'B' 
call print(t) 
end program main 

它使段错误消失，但我得到一个非常奇怪的输出AB 0 1 2673568 6 1566250180.

当在网上搜索类似的错误时，我得到了类似here的结果，它说这可能是由于递归调用太多。然而，插入（t，3）的调用应该只包含3次递归调用......我也尝试使用gfortran进行编译，使用-g -Wall -pedantic -fbounds-check并使用调试器运行。看来故障发生在打印子程序中的“if（t％isleaf）”行，但我不知道如何理解这一点。

编辑：

继意见，我与-g -fbacktrace -fcheck=all -Wall在gfortran编译并试图检查存储器的状态。我很新，所以我不确定我是否正确使用我的调试器（gdb）。

在三次插入之后，在呼叫print之前，看起来一切都很顺利：例如，当我在gdb中键入p t % left % left % right % value时，我得到期望的输出（即3）。如果我输入p t，则输出是（.FALSE。，0，x，y），其中x和y是十六进制数字（我猜是内存地址）。但是，如果我尝试p t % left，我得到的东西像一个指针的“说明”：

PTR TO -> (Type tree 
logical(kind=4) :: isleaf 
integer(kind=4) :: value 

它重演，因为每个指针指向包含两个指针树很多。我本来期望输出与p t类似，但我不知道这是否正常。

我也试图检查内存：例如，如果我输入x/4uw t % left，我得到4个字，第2个话似乎对应isleaf和value，最后2到内存地址。通过像这样的内存地址，我设法访问所有节点，我没有发现任何错误。

段错误发生在打印程序中。如果在故障后输入p t，则说我无法访问0x0地址。这是否意味着当我尝试打印它时，我的树会以某种方式被修改？

Answer 1

你出现问题的原因是事实上超出范围的变量不再有效。这与像Python这样的语言形成鲜明对比，其中现有指针的数量是相关的（refcount）。

你的具体情况，这意味着，到newleaf(left, n)和newleaf(right, n)呼叫设置的left和right，RESP。值，但这些变量得到OUF的范围，因此无效。

更好的方法是根据需要分配每个叶（除了第一个叶，因为它已经分配并且不会超出范围直到程序结束）。

recursive subroutine inserttree(t,n) 
    implicit none 
    type (tree), intent (INOUT) :: t 
    integer, intent (IN) :: n 

    if (t % isleaf) then 
    allocate(t%left) 
    allocate(t%right) 
    call newleaf(t%left,n) 
    call newleaf(t%right,n) 

    t % isleaf = .false. 
    else 
    call inserttree(t % left,n) 
    endif 
end subroutine inserttree