使用函数"fold"从二叉树顺序遍历构建列表

Question

我正在学习scala。现在我有此代码段：

sealed abstract class BSTree {
    def fold[A](init: A)(f: (A, Int) => A): A = this match {
      case Empty => init
      case Node(left, data, right) =>
        val curInorder:A = f(left.fold(init)(f), data)
        right.fold(curInorder)(f)
    }
}
case object Empty extends BSTree
case class Node(left: BSTree, data: Int, right: BSTree) extends BSTree

我的目的是在class BSTree中添加另一种方法，该方法在顶部方法fold并从二进制树的inorder traversal构建List。

我当前的实施是：

sealed abstract class BSTree {
    def fold[A](init: A)(f: (A, Int) => A): = .....//code snippet skipped
    def toList: List[Int] =  
             fold(Nil: List[Int])((xs: List[Int], hd)=> hd::xs).reverse
}

，但我觉得构建List，然后将其逆转是丑陋的。有更优雅的方法吗？任何提示都将被赞赏。

Answer 1

首先，您的折叠不是尾部递归，对于大输入而言，这可能会导致StackOverflowException。我鼓励您使用Stack自行尝试并实施它。作为参考，我将在帖子的底部放置样本实现。

其次，正如注释中已经提到的那样 - 您可能需要使用ListBuffer，以便构建列表在反向顺序方面更有效(因此，无需将其倒回去(。

这是一个单线：

def toList: List[Int] = fold(ListBuffer.empty[Int])(_ += _).toList

和实施尾部回复fold的参考：

def fold[B](init: B)(op: (B, A) => B): B = {
  def go(stack: List[(A, Tree[A])], current: Tree[A], acc: B): B = (current, stack) match {
    case (Empty, Nil) => acc
    case (Empty, (d, r) :: xs) => go(xs, r, op(acc, d))
    case (Node(l, d, r), _) => go((d, r) +: stack, l, acc)
  }
  go(Nil, this, init)
}

Answer 2

我发现，只需使用xs :+ hd而不是hd::xs将值以正确的顺序(深度优先，从左到右(。

val testTree: BSTree =
  Node(Node(Empty, 0, Empty), 1, Node(Empty, 2, Node(Node(Empty, 3, Empty), 4, Empty)))
def toList(bSTree: BSTree): List[Int] =
  bSTree.fold(List[Int]())((acc, next) => acc :+ next)
toList(testTree) // List(0,1,2,3,4)

我上面的实现是 o(n²(。根据 @dkim的评论，我们可以通过使用ListBuffer将其改进为 o(n(，或者我们可以使用Vector，然后在完成后转换为List。

除了简单地修复toList方法外，我们可能会问为什么使用fold实现toList的结果不同意我们的直觉(为我们提供了向后列表，而不是向前列表(。可能有人指出列表的折叠签名与List类层次结构的结构匹配。

abstract class List[+A] {
  def fold[B](init: B)(step: (A, B) => B): B
}
case object Empty extends List[Nothing] {
  def fold[B](init: B)(step: (A, B) => B): B = init
}
case class Cons[+A](head: A, tail: List[A]) extends List[A] {
  def fold[B](init: B)(step: (A, B) => B): B =
    step(head, tail.fold(init)(step))
}

请注意，fold的方法签名如何匹配类层次结构，甚至与每个实现类所具有的值匹配。(顺便说一句：出于简洁的目的，我正在使用既不有效也不安全的fold的非常幼稚的实现。生产实现应该是尾部递归或使用循环和可变的缓冲区，但要点是方法签名将是相同。(

我们可以为您的BSTree类做同样的事情，fold签名将是：

abstract class BSTree {
  def fold[A](withEmpty: A)(withNode: (A, Int, A) => A): A
}

然后toList为tree.fold(List[Int]())((l, n, r) => l ++ List(n) ++ r)。但是，如果您预计tree甚至约50个条目，请使用缓冲区或Vector进行不错的性能。