找出二叉树中每个 node 在R中的深度

我想如果你明确地知道哪些 node 是终端，哪些不是，那么就可以解码.这里有一个函数可以用额外的信息来计算深度

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

它看起来像你画的树在迭代== 1时是treeupt == 2.我们可以在树上运行函数，

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

(如果你喜欢从0开始，你可以从向量中减go 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

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