在scala中生成一棵树

发布时间：2020-12-16 10:06:39 所属栏目：安全来源：网络整理

导读：我正在学习 scala和我正在使用的书要求练习来定义树结构上的一些功能. 树被定义为： sealed trait Tree[+A]case class Leaf[A](value: A) extends Tree[A]case class Branch[A](left: Tree[A],right: Tree[A]) extends Tree[A] 其中一个练习是计算树中的节点

我正在学习 scala和我正在使用的书要求练习来定义树结构上的一些功能.

树被定义为：

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A],right: Tree[A]) extends Tree[A]

其中一个练习是计算树中的节点数.
我写了这个函数,但我无法检查它是否正常工作,因为我没有任何树的例子.

如何生成可用于测试代码的小树？

可能有可能在树上添加一个元素,但它似乎很多工作.

解决方法

就像这样

val tree = Branch(
             Branch(
               Leaf(12),Branch(
                 Leaf(3),Leaf(4))),Leaf(8))

那应该是树

06001

您可以在更大的树中重复使用它.关键在于你自下而上构建,你不能在底层构建,这需要从头开始创建一个新树

val biggerTree = Branch(Branch(something,tree),stillSomethingElse)

作为@dhg的答案的补充,生成具有给定数量的分支的树的变体(注意：总是有一个叶子而不是分支,因此分支叶子的总数总是奇数).这应该使测试变得简单

def randomTree(branchCount: Int): Tree[Int] =
  if(branchCount == 0) Leaf(0) // whatever,you can put a random here
  else {
     val branchCountAtLeft = util.Random.nextInt(branchCount) 
          // between 0 and branchCount - 1
     val branchCountAtRight = branchCount - 1 - branchCountAtLeft
     Branch(randomTree(branchCountAtLeft),randomTree(branchCountAtRight))
  }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!