使用 R 嵌套列表作为简单的二叉树

Question

我有一个限于 R 的简单问题。我有一种有效的二叉树，其中只有终端叶子具有与之关联的值。可见玩具示例here.
本质上，我在具有最大深度的叶子之间执行操作（在深度关系中，顺序无关紧要）。我在这里添加了它，但实际上，它们被插入到一个更复杂的公式中。
我的代码仅限于 R。这个结构可以用这个命令来表示，虽然我通过其他方式获得它：

testBranch<-list(list(list(list(20,15),40),list(10,30)),5) #Depth of 4

我有一个工作函数来确定最深层次的深度，但 R 中的嵌套列表令人难以置信。任何线索如何有效地找到 indexes 的集合以访问最深的值？例如，在上面的玩具示例中

testBranch[[1]][[1]][[1]]

会给我我想要的，一个包含 2 个元素的列表。使用我的加法示例，我可以这样做：

indexesOI<-getIndexes(testBranch) testBranch[indexesOI]<-testBranch[indexesOI][1]+testBranch[indexesOI][2] #testBranch now has depth of 3

生成对应于 toy example, 中步骤 1 的树，在 R 中可以表示为：

testBranchStep1<-list(list(list(35,40),list(10,30)),5)

如果需要，我愿意使用包。只是不想在 R 中重写整个节点 class/dfs，因为我对 class 系统没有太多经验。我调查了 data.tree，但没有运气将我的嵌套列表强制到它们的数据结构中。

如果您能提供任何帮助，那就太好了！请原谅匆忙制作的 ASCII 树。我主要是自学成才，在这里没有问很多问题，所以如果我需要调整格式，也请告诉我！谢谢！

Answer 1

听起来你已经完成了一半。无论何时找到最深的节点，都可以将索引输出到列表中。这是伪代码中的递归函数，因为我不知道 R.

If tree is a leaf node
   If current depth is greater than max-depth
      Delete list of indices
      Append current index into list of indices
   If current depth is equal to max-depth
      Append current index into list of indices
Else
   for each element in the tree
      Get current index
      Recursively call this function, passing in the current index

Answer 2

您可以使用 data.tree 来做到这一点。

library(data.tree)
testBranch <- list(list(list(list(20,15),40),list(10,30)),5)
tree <- FromListSimple(testBranch)
tree

这将打印树：

      levelName
1 Root         
2  °--1        
3      ¦--1    
4      ¦   °--1
5      °--2

data.tree 提供了许多实用函数和属性（请务必阅读小插图）。要知道深度，特别是使用这个：

height <- tree$height

产生：

> 4

然后您可以遍历树并找到最大高度的节点：

maxDepthLeaves <- Traverse(tree, filterFun = function(node) node$level == height)

此遍历是最大级别的节点列表（在本例中只有一个 Node）。然后，您可以使用 Get 从遍历中检索任何值，例如name、position 或 pathString：

Get(maxDepthLeaves, 'pathString')

显示为：

           1 
"Root/1/1/1"

使用 R 嵌套列表作为简单的二叉树

Using R nested lists as simple binary tree

tree

binary-tree

r

nested-lists

depth-first-search