scala - 二叉树折叠

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 方法的正确方法吗？

Answer 1

How would this work? I'm not sure I fully understand 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 的当前实现来做到这一点。 ，我们需要提供两种方法:

f1: A => B :给定一个 A , 项目一个 B值(value)

f2: (A, B, B) => B : 给定一个 A和两个 B值，项目 a 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))

这意味着如下:

如果我们遇到 Leaf节点并对其进行映射(通过在其上应用 f1)，我们只想提取它的值。

当遇到 Node元素(并对其应用 f2)，我们想取最右边的元素，它由第三个元素 z 投影在我们的方法中。

运行这个，产生预期的结果:50 .

如果我们想对任何 A 进行一般性扩展， 我们可以说:

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