懒散,广度优先遍历玫瑰树？

Question

我正在尝试重构一个当前产生Seq[X]使用相当昂贵的递归算法的组件,以便它产生一个Stream[X]代替,因此X可以按需加载/计算,并且生产者不必事先猜测如何为了满足消费者需要做很多事情.

从我所读到的,这是一个"展开"的理想用途,所以这是我一直试图采取的路线.

这是我的unfold功能,源于David Pollak的例子,该例子已由某位莫里斯先生审查过:

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
}