r语言 - 检查树(嵌套列表)是否是二叉搜索树

Question

我正在尝试从这里到 R 实现解决方案，但我无法弄清楚如何在 R 中正确执行此操作

检查树是否为二叉搜索树

我将这棵树转换为列表：

1
/ 
2   2
/  / 
3  4 4  3
tree <- list("node"=1, "left"=list("node"=2, "left"=list("node"=3), "right"=list("node"=4)), "right"=list("node"=2, "left"=list("node"=3), "right"=list("node"=4)) )

使用data.tree包我可以绘制它：

> data.tree::FromListSimple(tree, nodeName = "1")
      levelName
1 1            
2  ¦--left     
3  ¦   ¦--left 
4  ¦   °--right
5  °--right    
6      ¦--left 
7      °--right

我试图将上面的链接中的 Java 版本转换为 R，但我无法让它工作：

isBST <- function(node, mini, maxi) {
  if(is.null(node)) return(TRUE)
  if(node < mini | node > maxi) return(FALSE)
  return(isBST(left, mini, node-1) & isBST(right, node+1, maxi))
}

isBST(tree, -10, 10)

Answer 1

检查树是否为二进制的最简单方法很简单：

tree$isBinary

该函数利用了 data.tree 功能：

isBinary = function() {
    all(2 == Get(Traverse(self, filterFun = function(x) !x$isLeaf), "count"))
}

显然，您也可以自己实现它，例如使用递归，如链接的示例所示。虽然我不推荐它，因为递归在 R 中通常很慢。