二叉树折叠

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
  }

有人要求我使用折叠方法 return 树中最右边的值。这将如何工作？我不确定我是否完全理解折叠，但我认为折叠的重点是对树中的每个元素进行一些操作。我怎样才能使用它来 return 树的最右边的值？

我也不确定如何调用该方法。我不断遇到未指定参数类型的问题。有人可以告诉我调用此 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 值
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))

意思如下：

如果我们遇到 Leaf 节点并映射到它（通过在其上应用 f1），我们只想提取它的值。
当遇到 Node 元素（并对其应用 f2 时），我们要取 最右边的元素 ，它由我们方法中的第三个元素 z。

运行这会产生预期的结果：50.

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

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

Answer 2

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

这应该有效，因为该方法接受类型 A 和 returns 类型 A。它告诉方法我们是否在叶子上，只是 return 叶子值。如果我们有一个节点和一个左树和一个右树，return 右树的值。

二叉树折叠

Binary tree folding

scala

tree

fold