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

Question

仅使用基数 R capabilities/tools 创建二叉树的最佳方式是什么（假设在这种情况下，最佳意味着“创建或访问的最快方式”）？我假设使用环境操作的某种形式的递归 and/or 数据结构是必要的？

更重要的是，我希望将二叉树的创建参数化为应该生成哪种类型的树（例如：一个完美的树，其中所有节点是否有两个子节点？）。

示例：

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

应该是一棵看起来像这样的树的表示：

注意：请随意使用 S3 或 S4，考虑到它们在基础 R 中提供。但是，看到没有它们的解决方案会很有趣。

Answer 1

下面我们只使用基数进行图形计算。我们只使用 igraph 包进行绘图，并且只使用绘图所需的任何计算。

一个简单的做法是将位置i的节点的2children存入位置2*i+0:1，将一棵二叉树存储为数组。对于示例中的树，请参见下面的代码。这允许简单的广度优先遍历（只是运行通过跳过 NAs 的数组），并找到 parent (floor(i/2)) 和 children 的位置（第一句中的公式) 其中 i 是节点的位置。

a <- numeric()
a[1] <- 1
a[2:3] <- 2:3 # 2*1+0:1 = 2:3
a[4] <- 4  # 2*2+0 = 4

图形

在这种方法中，我们将每个节点标记为 - 如果它是左节点 child 和 + 如果它是右节点 child。如果特定 parent 有两个 children，这会将它们绘制在 parent 的左侧和右侧。如果有一个 child 那么它将直接绘制在 parent 下面，但是你可以通过符号来判断它是左还是右 child 。在后面的部分中，我们将展示如何将所有 children 绘制到其 parent 的左侧或右侧，即使 parent 只有一个 child；但是，这里的这种方法涉及的代码更少。

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)), ])

更新

已更新上一节，以便图表始终显示左 child 到 parent 的左侧，右 child 显示到 parent 的右侧。如果有两个 children，它以前会这样做，但现在如果只有一个 child.

，它也会这样做

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

How to create a binary tree using only base R?

binary-tree

r

图形

生成随机图

更新