有 n 个分支的 R 树

Question

如何生成一个有n个节点的树，每个节点有m个子节点，条件是每个子节点都是fun(parent)得到的？

我已经从 this post 中收集了一些逻辑，但我仍然停留在如何生成最多 n 个名称，以及如何生成将新生成的子项递归分配给它们的父项的函数上。（在这里插入乌托邦笑话）

-编辑-

我在下面尝试使用 TheTime 的解决方案，这确实回答了这个问题。但是，我没有问我想要的问题。因为这个问题有一个很好的答案，在某些情况下可能会有用，所以我发布了一个新问题来询问我的真正意思。

Answer 1

递归是一种方法，或者您可以使用 'stack' 数据结构。我不确定您正在考虑使用哪种函数或您计划存储哪种值，所以这里只是一个函数，它也使用父节点的名称创建子节点的名称。

## Function to apply to nodes to create children
nodeNamer <- function() {
    i <- 0
    function(node) sprintf("%s -> %g", node$name, (i <<- i+1))
}

make_tree <- function(depth, m, fn) {
    root <- Node$new('root')

    ## Some helper function to recurse
    f <- function(node, depth) {
        if (depth <= 0) return( root )
        for (i in seq.int(m)) {
            val <- fn(node)  # apply some function to parent node
            child <- node$AddChild(val)
            Recall(child, depth-1)  # recurse, Recall refers to 'f'
        }
    }
    f(root, depth)
    return( root )
}

## Make a tree with depth of '2' and 3 branches from each node
## Note that the way I defined the naming function, you must call it 
## in order to reset the the counter to 0
res <- make_tree(2, 3, nodeNamer())

res
#                  levelName
# 1  root                   
# 2   ¦--root -> 1          
# 3   ¦   ¦--root -> 1 -> 2 
# 4   ¦   ¦--root -> 1 -> 3 
# 5   ¦   °--root -> 1 -> 4 
# 6   ¦--root -> 5          
# 7   ¦   ¦--root -> 5 -> 6 
# 8   ¦   ¦--root -> 5 -> 7 
# 9   ¦   °--root -> 5 -> 8 
# 10  °--root -> 9          
# 11      ¦--root -> 9 -> 10
# 12      ¦--root -> 9 -> 11
# 13      °--root -> 9 -> 12

有 n 个分支的 R 树

R Tree With n Branches

tree

recursion

logic

r