# re: 二叉樹求和問題[未登錄] 回復 更多評論
2013-04-17 11:08 by
object TreeVisitor {
trait Monoid[A] {
def mempty: A
def mappend(a: A, b: A): A
}
implicit object IntMonoid extends Monoid[Int] {
def mempty = 0
def mappend(a: Int, b: Int) = a * 10 + b
}
implicit object StringMonoid extends Monoid[String]{
def mempty = ""
def mappend(a:String,b:String) = a+b
}
trait Tree[A]
case class TreeNode[A](n: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case class Leaf[A](num: A) extends Tree[A]
def visitTree[A: Monoid](t: Tree[A], path: A): List[A] = {
val ev = implicitly[Monoid[A]]
t match {
case TreeNode(n, left, right) =>
visitTree(left, ev.mappend(path, n)) ++ visitTree(right, ev.mappend(path, n))
case Leaf(num) => List(ev.mappend(path, num))
}
}
def main(args: Array[String]): Unit = {
val t1 = TreeNode(10, Leaf(7), Leaf(8))
val t2 = TreeNode(200, t1, Leaf(9))
val t3 = TreeNode(3000, t2, t2)
val t4 = TreeNode(40000, t3, t2)
val sumt = visitTree(t4,0).sum
println(sumt)
val s1 = TreeNode("1",Leaf("2"),Leaf("3"))
val s2 = TreeNode("2",s1,Leaf("4"))
val sums = visitTree(s2,"") map {x=>x.toInt}
println(sums.sum)
}
}