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

那应该是树

      *
    /   \
   *     8
  /  \
 12   *
     /  \
     3   4

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

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