comment construire un arbre puis traverser chaque feuille (du nœud racine à la feuille à chaque fois)?

Question

il y a un contenu de fichier comme ci-dessous ("1.txt")

1.txt:

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

la structure arborescente comme:

   a 
     b i  f 
    c   g h 
d e  

prévu:

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

Answer 1

Cela devrait fonctionner. J'ai sauté la partie où l'arbre est construit à partir de la lecture du fichier texte, car c'est assez simple.

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

sortie:

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