Scala 二叉树

Scala 二叉树

///用foldLeft就可以了，我重新定义了泛型，应该比较完美了
trait Tree[+T]

case object Empty extends Tree[Nothing]

case class Node[T](val value: T, val left: Tree[T], val right: Tree[T]) extends Tree[T]

////////////////////////

def insert[T](x: T, tree: Tree[T])(implicit order: Ordering[T]): Tree[T] = {
tree match {
case Empty => Node(x, Empty, Empty)
case Node(v, left, right) if order.gt(x, v) => Node(v, left, insert(x, right))
case Node(v, left, right) if order.lt(x, v) => Node(v, insert(x, left), right)
case Node(v, left, right) if order.equiv(x, v) => Node(v, left, right) //其实没有必要重新创建

}
}
def mkBinarySearchTree[T](list: List[T])(implicit order: Ordering[T]) = {
list.foldLeft[Tree[T]](Empty)((tree, value) => insert(value, tree))
}
def main(args: Array[String]) {
mkBinarySearchTree(List(1, 2, 3))
}追问请问Tree[T]和 Tree 有什么区别 我是初学者 谢谢追答泛型哦，用Tree[T]的话，可以支持任意类型的Tree。比如你这里的Tree，相当于Tree[Int]追问那 要生成一个新的树t' 是如何实现的？ 万飞感谢追答这里的insert就是生成新的树哦，case里的每个分支最后都是一颗新的树