algorithm - 如何构建一棵树然后遍历每个叶子(每次从根节点到叶子)？

Question

有一个文件内容如下(“1.txt”)

1.txt:

a,b
b,c
c,d
c,e
a,i
a,f
f,g
f,h

树结构如下:

             a   
        b    i     f
    c            g   h
 d   e     

预期:

a->b->c->d
a->b->c->e
a->i
a->f->g
a->f->h

Answer 1

这应该有效。我跳过了通过读取文本文件构建树的部分，因为它很简单。

case class Node(node: String, children: Seq[Node] = Seq()) {
  override def equals(that: Any): Boolean =
      that match {
          case that: Node if this.node == that.node => true
          case _ => false
   }
  override def toString = node
}

val d= Node("d")
val e = Node("e")
val g = Node("g")
val h = Node("h")
val i = Node("i")
val c = Node("c", Seq(d,e))
val f = Node("f", Seq(g, h))
val b = Node("b", Seq(c))
val a = Node("a", Seq(b,f,i))

val tree = a :: b :: c :: d :: e :: f :: g :: h :: i :: Nil

def traverse(tree: Seq[Node]): Seq[Seq[Node]] = {
  import scala.annotation.tailrec
    val leafNodes = tree.filter(x => x.children.isEmpty)
    @tailrec    
    def walk(node: Node, descendants: Seq[Node] = Seq()): Seq[Node] = {
        tree.find(x => x.children.contains(node)) match {
          case Some(x) =>  walk(x, (descendants :+ node))
          case None => descendants :+ node
        }
    }
    leafNodes.map(walk(_, Seq()).reverse)
}

输出:

scala> traverse(tree)
res26: Seq[Seq[Node]] = List(List(a, b, c, d), List(a, b, c, e), List(a, f, g), List(a, f, h), List(a, i))