Давайте посмотрим на некоторые решения 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 необычно, но здесь полезно его использовать.