修复Fortran二叉树递归子程序仅左节点赋值问题

我需要通过递归方式构建二叉树，具体需求如下：

• 创建带左右子节点的根节点
• 从根节点派生不同值，分别赋值给左右子节点
• 对左右子节点重复上述操作，持续递归扩展节点

但当前程序仅能为左节点赋值和插入节点，我清楚问题根源但不知道如何修正，希望实现递归时能同时处理左右子节点。输入为形如((3*(4+7)):((4+2)*(3-1)))的表达式（始终包含外层括号）。

现有代码 #

二叉树类型定义 #

type tree
    character(len=80)::expression
    type(tree), pointer::left,right
end type tree

递归拆分的核心子例程 #

recursive subroutine split(str)

    character(len=80):: str
    type(tree),pointer:: point
  
    allocate(point)
    point%expression = str

    call find_bracket(point%expression)
       
    if(found_bracket) then           ! 查找右括号")"
        allocate(point%left)
        allocate(point%right)

        call find_zero_niveau(str)  
        call empty_slots(str)

        ! 赋值新的表达式内容
        point%left%expression = str(2 : zero_niv - 2)                
        point%right%expression = str(zero_niv  : 80 - spaces - 1)
        point%expression = str(zero_niv - 1 : zero_niv - 1 )

        ! 这里的指针操作错误，导致无法正确访问根节点的右子节点
        point => point%left
        call split(point%expression)

        point => point%right            
        call split(point%expression)          ! 这显然无法正常工作
    end if 

end subroutine split

辅助子例程：查找括号层级为0的位置 #

subroutine find_zero_niveau(str)

    character(len=80)::str
    integer::j, bracket_niv
    logical::bracket_check = .false.

    call empty_slots(str)

    j = 80 - spaces                     
    bracket_niv = 0

    do while (j >= 1)  
        j = j - 1
        call getnextchar(str,j)

        if (next_char == ")") then
            bracket_check = .true.
            bracket_niv = bracket_niv + 1
        else if (next_char == "(") then
            bracket_niv = bracket_niv - 1
        end if

        if (bracket_niv == 0 .and. bracket_check) then
            zero_niv = j
            exit
        end if
    end do

end subroutine find_zero_niveau

辅助子例程：统计末尾空格数 #

subroutine empty_slots(str)

    character(len=80)::str
    integer::i 

    spaces = 0

    do i=1,80
        call getnextchar(str,i) ! 从字符串中提取指定位置的字符
        if (next_char == " ") then
            spaces = spaces + 1
        else if (next_char /= " ") then
            spaces = 0
        end if
    end do

end subroutine empty_slots

问题分析与修正 #

问题出在指针的重新赋值上：当执行point => point%left后，原来指向当前根节点的point指针已经被替换为指向左子节点，后续的point => point%right实际是在访问左子节点的右指针，而非最初根节点的右子节点，自然无法正确处理右子树的递归构建。

修正方法很简单：直接使用根节点的left和right指针来调用递归，不要修改原来的point指针。同时建议新增输出参数明确返回构建的节点，避免内部指针混乱，修改后的split子例程如下：

recursive subroutine split(str, node)
    ! 新增node参数，返回构建好的节点，避免内部指针的混乱
    character(len=80):: str
    type(tree), pointer:: node
  
    allocate(node)
    node%expression = str

    call find_bracket(node%expression)
       
    if(found_bracket) then           
        allocate(node%left)
        allocate(node%right)

        call find_zero_niveau(str)  
        call empty_slots(str)

        node%left%expression = str(2 : zero_niv - 2)                
        node%right%expression = str(zero_niv  : 80 - spaces - 1)
        node%expression = str(zero_niv - 1 : zero_niv - 1 )

        ! 直接对左右子节点递归调用，不修改当前node指针
        call split(node%left%expression, node%left)
        call split(node%right%expression, node%right)
    end if 

end subroutine split

调用时只需声明指针变量并传入：

type(tree), pointer:: root
call split(input_str, root)

这样就能同时递归处理左右子节点，正确构建出完整的表达式二叉树。

内容的提问来源于stack exchange，提问作者2GR8