scala - 如何以迭代器或流的形式遍历一棵 n 叉树

Question

我想在我的 Tree 类中创建一个函数来遍历 n-ary Tree[T] 以取回具有 (level, T) 的元组，以便该 Tree 的用户可以执行类似

tree.traverse.foreach{ case(l, t) => printf("%-30s %s", "  "*l + t.id, info(t))

得到这样的报告

rootnode                       
  n1.0                         
    n1.0.1                     >> n1.0.1
    n1.0.2                     >> n1.0.2
    n1.0.3                     >> n1.0.3
  n3.0                         
    n3.0.1                     >> n1.0.1
      n3.0.1.1                 >> n1.0.1

树节点是

class TreeNode[T](val id: String, 
          private var _data: Option[T],
          private var _parent: String, 
          private var _treeNodeType: TreeNodeType) {
  private var _children: Set[String] = Set()
  ...
}

我可以使用 traverse 或 traversef 递归遍历树

class Tree[T] {
  private val ROOT = "rootnode"
  val rootNode = new TreeNode(ROOT, None.asInstanceOf[Option[T]], "", ROOTNODETYPE)
  var hmTree: HashMap[String, TreeNode[T]] = HashMap(ROOT -> rootNode)

def traverse: Unit = {
  def iter(s: String, l: Int): Unit = {
    val n = hmTree(s)
    printf("%-30s\n", "  "*l + n.id)
    n.children.foreach(c => iter(c, l+1))
  }
  iter(ROOT, 0)
}

def traversef(f: Option[T] => String): Unit = {
  def iter(s: String, l: Int): Unit = {
    val n = hmTree(s)
    printf("%-30s %s\n", "  "*l + n.id, f(n.data))
    n.children.foreach(c => iter(c, l+1))
  }
  iter(ROOT, 0)
}

...

我看了http://www.scala-lang.org/old/node/11275.html (问题:How to implement lazy traversal of n-ary tree using Streams?)但代码无法运行。让我感到困惑的是如何 Stream.cons children 。

我可以使用流或迭代器。关键是在Tree类中定义遍历方法，在外面使用。

提前致谢。

更新

非常感谢@Archeg——这是工作遍历

def traverse(t: TreeNode[T], depth: Int = 0): Stream[(TreeNode[T], Int)] = {  
  (t, depth) #:: t.children.foldLeft(Stream.empty[(TreeNode[T], Int)]) { 
          case (aggr, el) => aggr #::: traverse(hmTree(el), depth+ 1)   
  }
}

tree.traverse(tree.rootNode).
  foreach{ case(t, l) => printf("%-30s %s\n", "  "*l + t.id, t.id) }

Answer 1

我把它简化了，所以很容易理解:

 case class Tree[T](data: T, children: List[Tree[T]])

 def traverse[T](t: Tree[T]): Stream[T] =
    t.data #:: t.children.foldLeft(Stream.empty[T])((aggr, el) => aggr #::: traverse(el))

更新

为您提供缩进的略微修改版本:

def traverseInd[T](t: Tree[T], depth: Int = 0): Stream[(T, Int)] =
    (t.data, depth) #:: t.children.foldLeft(Stream.empty[(T, Int)]) { 
            case (aggr, el) => aggr #::: traverseInd(el, depth+ 1)
    }