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