如何仅使用基数 R 创建二叉树？

Question

仅使用基本 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 中提供的。但是，如果没有它们，看到解决方案会很有趣。

Answer 1

下面我们仅使用 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)), ])

更新

更新了最后一部分，以便图表始终显示左孩子在父母的左边，右孩子在父母的右边。以前如果有两个孩子，它会这样做，但现在如果只有一个孩子，它也会这样做。