如何遍歷一個n元樹作爲迭代器或流

Question

我想在我的Tree類中創建一個函數來遍歷一個n元樹[T]以獲取帶有（level，T）的元組，以便該樹的用戶可以像

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() 
    ... 
} 

我可以遍歷樹使用遞歸遍歷或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（問：如何使用流實現N叉樹懶遍歷），但無法得到的代碼工作。讓我絆倒的是如何Stream.cons的孩子。

我對流或迭代器都可以。關鍵是在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)) 

Upd

一個稍微修改版本，它爲您提供縮進：

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) 
    }