时间戳

首页 > 解决方案 > 斯卡拉 | 在二叉树中折叠

scala - 斯卡拉 | 在二叉树中折叠

问题描述


fold我在我的 scala 代码中 实现了一个方法。我可以用它来确定树的size和depth。
现在我想实现这些方法max，map它们应该像这里一样工作。
不同之处在于，该值保存在分支而不是叶子中。
到目前为止，这是我的代码：

sealed trait Tree[+A] {
  def size(): Int = fold(this)(() => 1)((l, r, v) => 1 + l + r)

  def depth(): Int = fold(this)(() => 0)((left: Int, right: Int, v: A) => 1 + (left max right))

  def fold[X, B](t: Tree[X])(f: () => B)(g: (B, B, X) => B): B = t match {
    case Leaf() => f()
    case Branch(left, right, v) => g(fold(left)(f)(g), fold(right)(f)(g), v)
  }
}

case class Leaf[A]() extends Tree[A]

case class Branch[A](left: Tree[A], right: Tree[A], v: A) extends Tree[A]

有人可以帮我吗？

标签： scalafunctional-programmingbinary-tree

解决方案

首先，您可以放入fold伴生对象Tree（因为fold不使用thisie 是“静态的”）。

其次，从实施map您的案例开始

def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf() => ???_1
  case Branch(l, r, v) => ???_2 // here l, r are Tree[A]'s i.e. subtrees of t
}

看看它是如何为叶子中的值的树实现的。

然后用使用的那个替换这个实现fold

def map[B](f: A => B): Tree[B] = 
  fold[A, Tree[B]](this)(() => ???_1_)((l: Tree[B], r: Tree[B], v: A) => ???_2_))
  // here l, r are Tree[B]'s i.e. results of map for subtrees

???_1_并且???_2_是???_1, ???_2，您将递归调用替换为map, l，r它们是递归调用的结果。???_1_正是如此???_1。

推荐阅读