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

Question

我有一个被约束到R的简单问题。我有一种实际上是二叉树的东西，只有终端叶子有与它们相关的值。这里可以看到一个玩具示例
本质上，我在深度最大的叶子之间执行操作(在深度相等的情况下，顺序无关紧要)。我在这里添加了它，但实际上，它们被插入了一个更复杂的公式中
我的代码限制为R。这个结构可以用这个命令来表示，尽管我是通过其他方式获得的：

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

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

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

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

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

得到对应于玩具示例中步骤1的树，该树在R中可以用表示

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

如果需要的话，我愿意使用包。只是不想在R中重写整个节点类/dfs，因为我对类系统没有太多经验。我研究过data.tree，但没能把我的嵌套列表强行插入到它们的数据结构中。

你能提供的任何帮助都会很棒！请原谅那些匆忙制作的ASCII树。我基本上是自学成才的，在这里没有问过很多问题，所以如果我需要调整我的格式，也请告诉我！谢谢

Answer 1

您可以使用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" 

Answer 2

听起来你已经成功了一半。只要找到最深的节点，就可以将索引输出到列表中。这里有一个伪代码中的递归函数，因为我不知道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