Scala 二叉树
答案:1 悬赏:30 手机版
解决时间 2021-04-01 12:21
- 提问者网友：箛茗
- 2021-03-31 14:06
Scala 二叉树
最佳答案
- 五星知识达人网友：轮獄道
- 2021-03-31 14:20
///用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里的每个分支最后都是一颗新的树
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里的每个分支最后都是一颗新的树
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯