在scala中生成一棵树

Question

我正在学习 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]

其中一项练习是计算树中的节点数。我写了这个函数，但我无法检查它是否有效，因为我没有任何树的例子。

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

一次向树中添加一个元素可能是可能的，但看起来工作量很大。

Answer 1

就像

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

那应该是树

您可以在更大的树中重复使用它。关键是你自下而上构建，你不能在底部的东西，这需要从头开始创建一棵新树

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))
  }

Answer 2

@Didier 的回答很适合手工制作自己的树，但是如果你想自动生成树，你可以使用一个小的递归生成器来实现：

def generate(p: Double): Tree[Int] = {
  if (util.Random.nextDouble < p)
    Branch(generate(p), generate(p))
  else
    Leaf(0)
}

然后你就这样做：

val t = generate(0.5)
println(t)

你会得到一棵随机树。降低 p 会使树变小；提高它会使它们变大。

显然这将使所有叶子的树都具有相同的值。如果你想要随机叶值，试试：

 Leaf(util.Random.nextInt(100))

在scala中生成一棵树

generate a tree in scala

tree

scala

data-structures