求R中二叉树每个节点的深度？

Question

这个问题已被问过几次，但它们都是用不同的语言（例如，请参阅here for java和here for python，但我正在尝试在R中实现这一点。

我有一个树木数据框。我的树是按深度优先左侧遍历排序的，如下面的代码所示：

df <- data.frame(
  var = c("x2", NA, NA, "x1", NA, "x2", "x2", NA, NA, NA, "x2", NA, "x10", NA, NA, NA, "x1", NA, NA, "x5", NA, NA),
  node = c(1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3),
  terminal = c(FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE),
  iteration = c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2),
  treeNum = c(1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 1, 2, 2, 2, 3, 3, 3),
  stringsAsFactors = FALSE 
)

数据帧的结构如下：

var = 变量名（如果是终端节点或树桩，那么这只是 NA）

节点=节点号

terminal = 该节点是否是终端节点。

迭代=迭代次数

treeNum = 树编号

如您所见，我的数据框包含 3 棵树，经过 2 次迭代。

为了清楚起见，如果我们看一棵树（例如，迭代 1 中的树号 2），它将如下图所示（其中节点按照遍历方法进行编号）：

这棵树的深度（以深度优先左侧方法排序）为：0,1,1,2,3,3,2

最终，我想创建一个

depth

列来添加到我的数据框中，但我很难使代码正常工作。关于我如何做到这一点有什么建议吗？

Answer 1

我想如果你明确知道哪些节点是终端节点，哪些不是终端节点，那么就可以解码。所以这是一个可以用额外信息计算深度的函数

node_depth <- function(tree) {
  stopifnot(is.data.frame(tree))
  stopifnot("terminal" %in% names(tree))
  depths <- rep(0, nrow(tree))
  recurse <- function(idx, current_depth, depths) {
    if (idx > nrow(tree)) {
      return(list(idx=idx, depths=depths))
    }
    depths[idx] = current_depth
    if (tree$terminal[idx]) {
      return(list(idx=idx+1, depths=depths))
    }
    step <- recurse(idx+1, current_depth + 1, depths)
    step <- recurse(step$idx, current_depth + 1, depths=step$depths)
    list(idx=step$idx, depths=step$depths)
  }
  recurse(1, 1, depths)$depths
}

看起来你画的树在迭代==1时是treeNum==2。我们可以使用

在该树上运行该函数

node_depth(subset(df, iteration==1 & treeNum==2))
# [1] 1 2 2 3 4 4 3

（如果您希望从 0 开始，可以从向量中减去 1）。

我们可以在所有树上运行它

lapply(split(df, ~treeNum + iteration), 
  function(x) cbind(x, depth=node_depth(x)))

返回

$`1.1`
   var node terminal iteration treeNum depth
1   x2    1    FALSE         1       1     1
2 <NA>    2     TRUE         1       1     2
3 <NA>    3     TRUE         1       1     2

$`2.1`
    var node terminal iteration treeNum depth
4    x1    1    FALSE         1       2     1
5  <NA>    2     TRUE         1       2     2
6    x2    3    FALSE         1       2     2
7    x2    4    FALSE         1       2     3
8  <NA>    5     TRUE         1       2     4
9  <NA>    6     TRUE         1       2     4
10 <NA>    7     TRUE         1       2     3

$`3.1`
    var node terminal iteration treeNum depth
11   x2    1    FALSE         1       3     1
12 <NA>    2     TRUE         1       3     2
13  x10    3    FALSE         1       3     2
14 <NA>    4     TRUE         1       3     3
15 <NA>    5     TRUE         1       3     3

$`1.2`
    var node terminal iteration treeNum depth
16 <NA>    1     TRUE         2       1     1

$`2.2`
    var node terminal iteration treeNum depth
17   x1    1    FALSE         2       2     1
18 <NA>    2     TRUE         2       2     2
19 <NA>    3     TRUE         2       2     2

$`3.2`
    var node terminal iteration treeNum depth
20   x5    1    FALSE         2       3     1
21 <NA>    2     TRUE         2       3     2
22 <NA>    3     TRUE         2       3     2

因此，虽然深度优先前序遍历通常不能让您重建树，但如果您明确知道哪些节点是终端节点，哪些不是终端节点，则可以。