懒惰的树遍历Scala中的迭代器

Question

如果我的树定义如下:

case class Node(value: Int, children: Seq[Node])

但是为了论证,让我们说访问孩子是昂贵的,所以我只想在我需要时才能遍历它们.

如果将非严格的,急切的DFS遍历Node定义为

def traverse(node: Node): Unit = {
  node.children foreach { child => traverse(child) }
}

我如何创建它的懒惰对应物？

理想情况下,我将有一个iterator方法,它返回一个基于DFS遍历排序的迭代器,它只在对其next()调用时计算下一个元素:

val tree = Node(1, Seq(Node(2, Nil), Node(3, Nil)))
val dfsIt = tree.iterator // get a iterator with a DFS traversal ordering
val nextNode = dfsIt.next() // compute which element to return on demand

Answer 1

case class Node(value: Int, children: Seq[Node]) {

  def dfsIterator: Iterator[Node] = {
    println(value)
    children.iterator.map(_.dfsIterator).flatten ++ Iterator(this)
  }
}