Scala 二叉树

sealed abstract class Tree
case class mkTree(x: Int, Left: Tree, Right: Tree) extends Tree
case object Empty extends Tree

//插入新的元素  但是要生成一个新的数叫t' 该怎么写？
def insert (x: Int, t: Tree): Tree = {

t match{
...sealed abstract class Tree
case class mkTree(x: Int, Left: Tree, Right: Tree) extends Tree
case object Empty extends Tree

//插入新的元素  但是要生成一个新的数叫t' 该怎么写？
def insert (x: Int, t: Tree): Tree = {

t match{
case Empty=> mkTree(x,Empty,Empty)
case mkTree(v,left,right) if x< v =>
   mkTree(v,insert(x,left),right)
case mkTree(v,left,right) if x>v  =>
   mkTree(v,left,insert(x,right))
case mkTree(v,left,right) =>
   t
}

  }
//现在我又要写一个方法叫 mkBST 用 order 和 numberlist: list 来生成一棵树该怎么写？谢谢展开

manyfaces · 2018-4-30 02:07:45

///用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))
  }

Scala 二叉树

1 个回复