使用函数"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 中添加另一个方法 toList，它位于顶部方法 fold 并从二叉树的中序遍历构建一个 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

我发现简单地使用 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 class 层次结构相匹配。

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 的方法签名如何匹配 class 层次结构，甚至细化到每个实现 class 所持有的值。（旁白：为简洁起见，我使用了一个非常简单的 fold 实现，它既不高效也不堆栈安全。生产实现应该是尾递归的或使用循环和可变缓冲区，但关键是方法签名将是相同的。）

我们可以为您的 BSTree class 做同样的事情，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 以获得不错的性能。

Answer 2

首先，您的折叠不是尾递归的，对于大输入可能会导致 WhosebugException。我鼓励您尝试使用 Stack 自行实施。作为参考，我将在 post.

的底部放置一个示例实现

其次，正如评论中已经提到的那样 - 您可能想要使用 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)
}

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

Build List from binary tree inorder traversal using function "fold"

binary-tree

scala

higher-order-functions