scala - 玫瑰树的惰性，广度优先遍历？

Question

我正在尝试重构当前生成 Seq[X] 的组件使用相当昂贵的递归算法来生成 Stream[X]相反，所以 X可以按需加载/计算，并且生产者不必事先猜测它必须进行多少挖掘才能满足消费者。

从我读到的内容来看，这是“展开”的理想用途，所以这就是我一直试图采取的路线。

这是我的 unfold函数，派生自 David Pollak's example ，经过某位莫里斯先生的审核:

def unfold[T,R](init: T)(f: T => Option[(R,T)]): Stream[R] = f(init) match {
  case None => Stream[R]()
  case Some((r,v)) => r #:: unfold(v)(f)
}

这里有一棵小树可以试试运气:

case class Node[A](data: A, children: List[Node[A]]) {
  override def toString = "Node(" + data + ", children=(" + 
                                children.map(_.data).mkString(",") + 
                                "))"
}

val tree = Node("root", List(
  Node("/a", List(
    Node("/a/1", Nil),
    Node("/a/2", Nil)
  )),
  Node("/b", List(
    Node("/b/1", List(
      Node("/b/1/x", Nil),
      Node("/b/1/y", Nil)
    )),
    Node("/b/2", List(
      Node("/b/2/x", Nil),
      Node("/b/2/y", Nil),
      Node("/b/2/z", Nil)
    ))
  ))
))

最后，这是我使用展开的广度优先遍历失败的尝试:

  val initial = List(tree)
  val traversed = ScalaUtils.unfold(initial) {
    case node :: Nil =>
      Some((node, node.children))
    case node :: nodes =>
      Some((node, nodes))
    case x =>
      None
  }
  assertEquals(12, traversed.size) // Fails, 8 elements found

/* 
traversed foreach println => 

Node(root, children=(/a,/b))
Node(/a, children=(/a/1,/a/2))
Node(/b, children=(/b/1,/b/2))
Node(/b/1, children=(/b/1/x,/b/1/y))
Node(/b/2, children=(/b/2/x,/b/2/y,/b/2/z))
Node(/b/2/x, children=())
Node(/b/2/y, children=())
Node(/b/2/z, children=())
*/

谁能给我一些关于如何修复(或重写)我的遍历逻辑以便返回所有节点的提示？谢谢!

Answer 1

您只是忘记在树的遍历过程中包含内部节点的子节点:

val traversed = unfold(initial) {
  case node :: Nil =>
    Some((node, node.children))
  case node :: nodes =>
    // breadth-first
    Some((node, nodes ::: node.children))
    // or depth-first: Some((node, node.children ::: nodes))
  case x =>
    None
}