二叉树折叠

Question

我被给予了以下二叉树的定义

abstract class Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

并且以下函数

def fold_tree[A,B](f1: A => B)(f2: (A, B, B) => B)(t: Tree[A]): B = t match {
    case Leaf(value) => f1(value)
    case Node(value, l, r) => f2(value, fold_tree(f1)(f2)(l), fold_tree(f1)(f2)(r)) //post order
  }

我被要求使用fold方法返回树中最右边的值。这应该如何实现？我不确定我完全理解fold的含义，但我认为fold的目的是对树中的每个元素执行一些操作。我如何使用它来只返回树的最右边的值？

我也不确定如何调用该方法。我一直遇到未指定参数类型的问题。有人能展示一下调用fold_tree方法的正确方式吗？

- Vandexel

---

你能展示一下你目前尝试过的吗？ - Alec

当然。我相当迷失了。我最初想尝试调用函数并查看结果。我对Scala不是很熟悉，也不确定如何输入正确的变量/类型。我已经尝试过类似下面这样的内容： fold_tree[A，Int]（t => 1）（t，t，t => 1）（t） 只是为了看看能否使方法运行并以某种方式返回一个，但我认为我没有正确理解它。 - Vandexel

实际上，我可能已经想出了如何做到这一点。你能确认/否认这个推理吗？fold_tree[A,A]( t => t)((t,x,z) => z)(t) 这应该可以工作，因为该方法接受类型A并返回类型A。它告诉方法，如果我们在叶子节点，只需返回叶子节点的值。如果我们有一个节点和左树和右树，则返回右树的值。这正确吗？ - Vandexel

没错！将其发布为答案并接受它！评论中的一些风格：t => t 被定义为 identity，通常最好在你不使用参数的位置放置下划线: (_,_,z) => z。 - Alec

你打算在SO上发布你的作业所有问题吗？ - The Archetypal Paul

Answer 1

这个怎么运作？我不确定我完全理解fold。

你的foldTree方法是在递归地遍历树，在此过程中对每个遇到的Node或Leaf应用自身。该方法还有两个类型参数需要应用，即A和B，取决于所提供的树的类型。

为了举例说明，让我们假设我们定义了一个像这样的Tree[Int]:

val n = Node(1, Leaf(2), Node(3, Leaf(5), Node(4, Leaf(42), Leaf(50))))

这段文本的英译中文是：

树的结构看起来像这样：

我们想要获取最右边的值，也就是50。为了使用当前的foldTree实现来实现这个目标，我们需要提供两种方法：

1. f1: A => B：给定一个A，返回一个B值
2. f2: (A, B, B) => B：给定一个A和两个B值，返回一个B。

我们可以看到f1被应用于一个Leaf上，而f2被应用于一个Node上（因此每种方法提供的元素数量不同）。因此，这给了我们一个提示，即我们提供给foldTree的函数将分别应用于每个元素。

有了这些知识，假设我们有以下树：

val n = Node(1, Leaf(2), Node(3, Leaf(55), Node(4, Leaf(42), Leaf(50))))

我们提供以下方法：

println(foldTree[Int, Int](identity)((x, y, z) => z)(n))

这意味着以下内容：

1. 如果我们遇到一个Leaf节点并对其进行映射（通过应用f1），我们只想提取它的值。
2. 当遇到一个Node元素（并应用f2）时，我们希望取最右边的元素，该元素由方法中的第三个元素z投影。

运行此代码将产生预期结果：50。

如果我们想要通用地扩展任何A，我们可以说：

def extractRightmostValue[A](tree: Tree[A]) =
  foldTree[A, A](identity)((x, y, z) => z)(tree)

- Yuval Itzchakov

---

谢谢！只是确认一下，我们之所以在这里使用[Int，Int]是因为这个二叉树只包含整数，对吗？我在我的代码中使用[A，A]，它可以工作。那是因为树/节点/叶子和函数都在使用A吗？ - Vandexel

@Vandexel 是的，没错。如果我创建一个 Tree[A]，那就意味着我可以应用任何 A。在这种情况下，我选择将其应用于 Tree[Int]。但是，如果你想通用地应用到任何 A，那么你可以像你所做的那样去做。 - Yuval Itzchakov

我遇到了一些困难，无法理解另一个问题。这个问题要求我返回一棵树的镜像，其中左右子树递归翻转。例如，Node(4,Leaf(1),Leaf(2))将产生Node(4,Leaf(2),Leaf(1))。但我不确定为什么以下代码无法工作： fold_tree[A,A](t => t)((x,y,z) => (x,z,y)(t) 对我来说，这段代码的意思是：输入A类型，输出A类型。我们传入一棵树，如果它是叶子节点则返回它本身，如果它是非叶子节点，则返回其自身并翻转lt和rt。但是这会产生类型不匹配的错误：需要A类型，但却发现(A,A,A)类型。这是什么意思？我哪里想错了吗？ - Vandexel

我会在另一个问题中提问，以使其更清楚。 - Vandexel

Answer 2

fold_tree[A,A](identity)((_,_,z) => z)(t)

这应该有效，因为该方法接受类型 A 并返回类型 A。它告诉方法如果我们在一个叶子节点上，只需返回叶子的值。如果我们有一个节点、左树和右树，则返回右树的值。

- Vandexel