Scala 中的惰性树遍历迭代器

Question

如果我的树是这样定义的：

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

但是为了论证，假设访问 children 是昂贵的，所以我只想在实际需要时遍历它们。

如果 non-strict，Node 上的急切 DFS 遍历定义为

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

如何创建它的惰性副本？

理想情况下，我将有一个 iterator 方法，其中 returns 一个基于 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)
  }
}

Scala 中的惰性树遍历迭代器

Lazy tree traversal iterator in Scala

scala

iterator

lazy-evaluation

tree-traversal