如何在R语言中计算二叉树各节点的深度？

针对你提供的按深度优先左遍历排序的二叉树数据框，我们可以通过递归遍历每个树的结构来计算节点深度，核心思路是利用深度优先遍历的结构特性：每个非终端节点的左子树是连续的一段序列，遍历完左子树后才会处理右子树。

实现步骤 #

1. 递归计算单棵树的深度：定义递归函数，针对单棵树的节点序列，先确定根节点深度为0，再递归计算左子树和右子树的深度（子树节点深度=父树深度+1）。
2. 分组处理多棵树：按iteration和treeNum分组，对每组单独应用递归函数计算深度，最后合并到原数据框。

完整代码 #

library(dplyr)

# 定义递归计算深度的函数
calculate_depth <- function(node_df) {
  if (nrow(node_df) == 0) return(numeric(0))
  
  # 根节点深度为0
  depth_vec <- 0
  root_terminal <- node_df$terminal[1]
  
  if (!root_terminal) {
    # 找到左子树的结束位置：从第2个节点开始，直到栈归0（左子树遍历完成）
    stack <- 1
    left_end <- 1
    for (i in 2:nrow(node_df)) {
      if (!node_df$terminal[i]) {
        stack <- stack + 1
      } else {
        stack <- stack - 1
      }
      left_end <- i
      if (stack == 0) break
    }
    
    # 分割左子树和右子树
    left_subtree <- node_df[2:left_end, ]
    right_subtree <- node_df[(left_end + 1):nrow(node_df), ]
    
    # 递归计算左右子树深度，加上当前层级偏移
    left_depth <- calculate_depth(left_subtree) + 1
    right_depth <- calculate_depth(right_subtree) + 1
    
    # 合并结果
    depth_vec <- c(depth_vec, left_depth, right_depth)
  }
  
  depth_vec
}

# 为数据框添加depth列
df_with_depth <- df %>%
  group_by(iteration, treeNum) %>%
  mutate(depth = calculate_depth(cur_data())) %>%
  ungroup()

# 查看结果
print(df_with_depth)

验证示例 #

对于iteration=1且treeNum=2的树，运行后得到的depth列值为0,1,1,2,3,3,2，与你预期的结果一致。

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