6

我正在尝试Seq[X]使用相当昂贵的递归算法重构当前生成 a 的组件，以便它生成 a Stream[X]，因此X可以按需加载/计算 's ，并且生产者不必事先尝试猜测如何为了满足消费者，它必须做很多挖掘工作。

根据我的阅读，这是“展开”的理想用途，所以这就是我一直试图采取的路线。

这是我的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=())
*/

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

4

2 回答 2

6

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

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
}
于 2011-04-30T00:14:03.117 回答
1

这是 Moritz 答案的完整版本，带有更正的部分函数（最后一种情况与原始问题中的任何内容都不匹配）：

case class CNode[A](data: A, children: List[CNode[A]]=Nil) {
  override def toString: String = if (children.isEmpty) s"node($data)" else
    s"node($data, children=(${ children.map(_.data).mkString(",") }))"
}

object Main extends App {
  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)
  }

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

  val traversed = unfold(tree) {
    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 Nil =>
      None
  }

  println(traversed.force.mkString("\n"))
}
于 2017-10-31T00:28:11.460 回答