如何仅使用基数R创建二叉树？
仅使用基本 R 功能/工具创建二叉树的最佳方式是什么（假设在这种情况下，最佳意味着“创建或访问的最快方式”）？我假设某种形式的递归和/或使用环境操作的数据结构是必要的？
更重要的是，我希望二叉树的创建被参数化为应该生成什么类型的树（例如：一个完美的，其中所有节点都有两个孩子？）。
例子：
my_tree <- grow_tree(perfect = FALSE, max_height = 3)
print(my_tree)
my_tree[1]
1
my_tree[1][left]
2
my_tree[1][right]
3
my_tree[1][left][left]
4
应该是一棵树的表示，看起来像：
1
/
2 3
/
4
注意：随意使用 S3 或 S4，考虑到它们是在基础 R 中提供的。但是，如果没有它们，看到解决方案会很有趣。
回答
下面我们仅使用 base 进行图形计算。我们只使用 igraph 包进行绘图和任何仅用于绘图所需的计算。
一种简单的方法是将二叉树存储为数组，方法是将位置 i 的节点的 2 个子节点存储在 position 中2*i+0:1。对于示例中的树，请参见下面的代码。这允许简单的广度优先遍历（只需遍历数组跳过 NA），并找到父节点 ( floor(i/2)) 和子节点的位置（第一句中的公式），其中 i 是节点的位置。
a <- numeric()
a[1] <- 1
a[2:3] <- 2:3 # 2*1+0:1 = 2:3
a[4] <- 4 # 2*2+0 = 4
图形
在这种方法中，我们将每个节点标记为 - 如果它是左孩子，而 + 如果它是右孩子。如果一个特定的父母有两个孩子，这会将它们绘制在父母的左侧和右侧。如果有一个孩子，那么它将直接绘制在父母的下方，但您可以通过符号判断它是左孩子还是右孩子。在后面的部分中，我们将展示如何将所有子项绘制在其父项的左侧或右侧，即使该父项只有一个子项；但是，这里的这种方法涉及的代码较少。
library(igraph)
ix <- seq_along(a)
edges <- cbind(ix, floor(ix/2))[-1, ]
# label right child as + and left child as - . Root is +1.
edges <- apply(edges, 2, function(x) paste0(ifelse(x %% 2, "+", "-"), x))
g <- graph_from_edgelist(edges)
plot(g, layout = layout_as_tree(g, root = "+1", mode = "all"))
（在图像后继续）
生成随机图
这是生成深度不超过 n 的随机树的示例。（igraph 作者帮助简化了我发布的初始绘图代码）。
library(igraph)
set.seed(7)
n <- 4
a <- rnorm(2^n-1)
a[-1] <- ifelse(runif(length(a)) > .8, NA, a)[-1] # -1 to exclude root
for(i in seq_along(a)) if (i > 1 && is.na(a[floor(i/2)])) a[i] <- NA
a
## [1] 2.2872471613405239 -1.1967716822223495 -0.6942925104354590
## [4] -0.4122929511368025 -0.9706733411194832 NA
## [7] 0.7481393402905512 -0.1169552258871516 NA
## [10] 2.1899781073293796 0.3569862303290225 NA
## [13] NA 0.3240205401385159 NA
现在绘制它。
library(igraph)
# create graph from edgelist
make_graph <- function(edgelist) {
edges <- apply(edgelist, 2, as.character)
graph_from_edgelist(edges)
}
# create full graph layout without random NAs
ix <- seq_along(a)
edges_f <- cbind(ix[-1], floor(ix[-1]/2))
g_f <- make_graph(edges_f)
layout_f <- layout_as_tree(g_f, root = "1", mode = "all")
# create random subset graph by removing edges connected to NA nodes
edges_s <- na.omit(edges_f + 0*replace(edges_f, TRUE, a[c(edges_f)]))
g_s <- make_graph(edges_s)
# plot using corresponding layout rows from full graph
plot(g_s, layout = layout_f[names(V(g_f)) %in% names(V(g_s)), ])
更新
更新了最后一部分，以便图表始终显示左孩子在父母的左边，右孩子在父母的右边。以前如果有两个孩子，它会这样做，但现在如果只有一个孩子，它也会这样做。
- It must be done breadth first because we need to NA out the parent before we NA out the child and also we don't want to NA out the root or else we get an empty graph.