Skip to content

Instantly share code, notes, and snippets.

@kyo-ago
Last active Dec 27, 2015
Embed
What would you like to do?
trait Node {
val number: Int
def max: Int = this.number
def min: Int = this.number
def sum: Int = this.number
def avg: List[Int] = List(this.number)
def find(e: Int): Option[Node] = if (this.number == e) Some(this) else None
}
case class Branch(left: Node, number: Int, right: Node) extends Node {
override def max: Int = List(left.max, this.number, right.max).max
override def min: Int = List(left.min, this.number, right.min).min
override def sum: Int = left.sum + this.number + right.sum
override def avg: List[Int] = this.number :: List(left.avg, right.avg).flatten
override def find(e: Int): Option[Node] = (e < this.number, e > this.number) match {
case (true, _) => left.find(e)
case (_, true) => right.find(e)
case _ => Some(this)
}
}
case class Leaf(number: Int) extends Node {}
case class BTree(node: Node) {
def max: Int = this.node.max
def min: Int = this.node.min
def sum: Int = this.node.sum
def avg: Int = this.node.sum / this.node.avg.length
def find(e: Int): Option[Node] = this.node.find(e)
}
val bTree1 = BTree(Leaf(1))
val bTree2 = BTree(Branch(Leaf(1), 2, Leaf(3)))
val bTree3 = BTree(Branch(Branch(Leaf(1), 2, Leaf(3)), 4, Branch(Leaf(5), 6, Leaf(7))))
def makeTree(list: List[Int]): Node = {
if (list.length == 1) {
return Leaf(list(0))
}
val (left, mid :: right) = list.splitAt(list.length / 2)
Branch(makeTree(left), mid, makeTree(right))
}
BTree(makeTree((1 to 7).toList))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment