/** * Exercise 7.2.2 Consider the following definitions representing trees of * integers. These definitions can be seen as an alternative representation of * IntSet: * * abstract class IntTree * case object EmptyTree extends IntTree * case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree * * Complete the following implementations of function contains and insert for * IntTree's. * * def contains(t: IntTree, v: Int): Boolean = t match {} * def insert(t: IntTree, v: Int): IntTree = t match {} */ abstract class IntTree case object EmptyTree extends IntTree case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree def contains(t: IntTree, v: Int): Boolean = t match { case EmptyTree => false case Node(elem, _, _) if (elem == v) => true case Node(elem, left, _) if (elem < v) => contains(left, v) case Node(elem, _, right) if (elem > v) => contains(right, v) } def insert(t: IntTree, v: Int): IntTree = t match { case EmptyTree => new Node(v, EmptyTree, EmptyTree) case Node(elem, left, _) if (v < elem) => new Node(elem, insert(left, v), right) case Node(elem, left, right) => new Node(elem, left, insert(right, v)) } |