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

发布时间：2020-12-16 18:34:16 所属栏目：安全来源：网络整理

导读：如果我的树定义如下： case class Node(value: Int,children: Seq[Node]) 但是为了论证,让我们说访问孩子是昂贵的,所以我只想在我需要时才能遍历它们. 如果Node上的非严格,急切的DFS遍历被定义为 def traverse(node: Node): Unit = { node.children foreach

如果我的树定义如下：

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

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

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

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

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

理想情况下,我将有一个迭代器方法,该方法返回一个基于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

解决方法

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!