二叉树折叠

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

Answer 1

这将如何运作？我不确定我是否完全了解折叠

您的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)