在R语言中计算二叉树网络中所有链路到链路1的总长度

现有一个用data.frame定义的二叉树结构数据，包含数值型链路名称、两个子链路字段（PL，-1表示无子链路，不存在单链路的情况），以及每条链路的长度。需要生成新表，记录每条链路到链路1起点的总距离（即从链路1到该链路的路径长度总和）。

测试数据 #

test_data <- data.frame(Link = seq(1, 9, 1),
                        PL1 = c(2, 4, 6, -1, -1, -1, 8, -1, -1),
                        PL2 = c(3, 5, 7, -1, -1, -1, 9, -1, -1),
                        Len = c(15, 17, 81, 9, 42, 7, 13, 64, 36))

期望结果 #

result <- data.frame(Link = seq(1, 9, 1),
                     Len = c(15, 15+17, 15+81, 15+17+9, 15+17+42, 15+81+7, 15+81+13, 15+81+13+64, 15+81+13+36))

比如链路7的总长度为L1 + L3 + L7，最终需得到各链路的路径长度求和结果。

解决方案 #

步骤1：构建父节点映射 #

原数据中的PL1和PL2记录的是当前链路的子节点，我们需要先反向构建每个链路的父节点映射：

# 初始化父节点映射表
parent_map <- data.frame(Link = integer(), Parent = integer())

# 遍历每条链路，提取子节点的父节点关系
for(i in 1:nrow(test_data)) {
  current_link <- test_data$Link[i]
  child1 <- test_data$PL1[i]
  child2 <- test_data$PL2[i]
  
  if(child1 != -1) {
    parent_map <- rbind(parent_map, data.frame(Link = child1, Parent = current_link))
  }
  if(child2 != -1) {
    parent_map <- rbind(parent_map, data.frame(Link = child2, Parent = current_link))
  }
}

步骤2：递归计算总距离 #

定义递归函数，从目标链路向上遍历到链路1，累加路径上的所有链路长度：

# 递归函数：计算单个链路到链路1的总距离
get_total_distance <- function(link_id, parent_map, len_data) {
  # 获取当前链路的长度
  current_len <- len_data$Len[len_data$Link == link_id]
  
  # 链路1是起点，直接返回自身长度
  if(link_id == 1) {
    return(current_len)
  }
  
  # 找到当前链路的父节点
  parent_link <- parent_map$Parent[parent_map$Link == link_id]
  
  # 递归累加父节点的总距离与当前链路长度
  return(current_len + get_total_distance(parent_link, parent_map, len_data))
}

# 对所有链路应用函数，计算总距离
test_data$Total_Len <- sapply(test_data$Link, get_total_distance, 
                              parent_map = parent_map, len_data = test_data)

# 生成最终结果表
result <- test_data[, c("Link", "Total_Len")]
colnames(result)[2] <- "Len"

运行后result将完全匹配期望的输出结果。

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