Skip to content

Instantly share code, notes, and snippets.

@k4200
Last active August 29, 2015 14:19
Show Gist options
  • Save k4200/1570639e58ec4fa3f4ad to your computer and use it in GitHub Desktop.
Save k4200/1570639e58ec4fa3f4ad to your computer and use it in GitHub Desktop.
再帰を使って木構造をたどる
// 頭が慣れていないので、再帰むずい
case class Tree(id: Int, children: List[Tree])
val n8 = Tree(8, Nil)
val n4 = Tree(4, Nil)
val n5 = Tree(5, Nil)
val n6 = Tree(6, List(n8))
val n7 = Tree(7, Nil)
val n2 = Tree(2, List(n4, n5))
val n3 = Tree(3, List(n6, n7))
val n1 = Tree(1, List(n2, n3))
import scala.annotation.tailrec
def traverseTree(t: Tree): List[Int] = {
@tailrec
def _traverseTree(rest: List[Tree], result: List[Int]): List[Int] = {
rest match {
case Nil =>
result.reverse
case x :: xs =>
_traverseTree(x.children ::: xs, x.id :: result)
}
}
_traverseTree(List(t), Nil)
}
traverseTree(n1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment