いくつかの Scala ソリューションを見てみましょう。まず、非常に基本的なバイナリ ツリーを定義します。
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])
次のツリーを使用します。
1
/ \
2 3
/ / \
4 5 6
次のようにツリーを定義します。
val myTree = Tree(1,
Some(Tree(2,
Some(Tree(4, None, None)),
None
)
),
Some(Tree(3,
Some(Tree(5, None, None)),
Some(Tree(6, None, None))
)
)
)
各要素に目的の関数を適用してツリーを走査する、breadthFirst 関数を定義します。これで、印刷関数を定義し、次のように使用します。
def printTree(tree: Tree[Any]) =
breadthFirst(tree, (t: Tree[Any]) => println(t.value))
printTree(myTree)
さて、Scala ソリューション、再帰的、リストはありますが、キューはありません:
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
def traverse(trees: List[Tree[T]]): Unit = trees match {
case Nil => // do nothing
case _ =>
val children = for{tree <- trees
Some(child) <- List(tree.left, tree.right)}
yield child
trees map f
traverse(children)
}
traverse(List(t))
}
次に、Scala ソリューション、キュー、再帰なし:
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
import scala.collection.mutable.Queue
val queue = new Queue[Option[Tree[T]]]
import queue._
enqueue(Some(t))
while(!isEmpty)
dequeue match {
case Some(tree) =>
f(tree)
enqueue(tree.left)
enqueue(tree.right)
case None =>
}
}
この再帰的なソリューションは完全に機能しますが、さらに単純化できるのではないかと不安に思っています。
キューバージョンは機能しませんが、非常に効果的です。オブジェクトのインポートについては、Scala では珍しいことですが、ここではうまく利用されています。