scala版 二叉搜索树 BinarySearchTree

BinarySearchTree.scala

package t1

object BinarySearchTree {

  def mkTree[K <% Ordered[K], T](key : K, v : T) : Tree[K, T] =
    new Node(key, v, Empty, Empty)

  case class Person(id : String, name : String)

  def main(args : Array[String]) : Unit = {
    var tree = mkTree(200, Person("2-1", "songpp"))
    tree = tree.insert(100, Person("3-1", "god"))
    tree = tree.insert(300, Person("4-1", "dog"))
    tree = tree.insert(290 ,Person("5-1","cat"))
    
    val tr = Empty.insert("hello",1)
    
    Console println tree
    Console println tr
  }
}

abstract class Tree[+K, +T] {
  def insert[X >: K <% Ordered[X], U >: T](key : X, v : U) : Tree[X, U]
  def search() = throw new UnsupportedOperationException
}

case object Empty extends Tree[Nothing, Nothing] {
  def insert[K <% Ordered[K], T](key : K, v : T) : Tree[K, T] = {
    new Node(key, v, Empty, Empty)
  }
}

case class Node[K <% Ordered[K], +T](k : K, value : T, left : Tree[K, T], right : Tree[K, T]) extends Tree[K, T] {
  def insert[X >: K <% Ordered[X], U >: T](key : X, v : U) : Tree[X, U] = {
    if (key == k)
      this
    else if (key < k)
      new Node(k, value, left.insert(key, v), right)
    else
      new Node(k, value, left, right.insert(key, v))
  }
  def search(key : K) = throw new UnsupportedOperationException
}