In this Scala programming assignment, you wil implement various set operations o
ID: 3740806 • Letter: I
Question
In this Scala programming assignment, you wil implement various set operations on Binary Search Tree implementations of Sets of integers. You will use "case classes" of Scala to represent a binary tree object BST abstract class BT case class Tree (eft: B7.value: Int, right: BT) extends B object Ni extends BT // returns the smallest element in BST t // returns the largest element in BSzt // returns true if t is a BST and false otherwise // r.turns true if is & menter e? ?5T t, fals. otherwise def menberBST (x: Int . tl BT): Boolean ??? // returns a new BST obtained by inserting x in BST t. // should return tifx is already int // returns the height of t; // returns a new BST obtained by deleting x in BST t. I/ should return t if x is not in t // returns the number of elements in t def toString (t ; String " t match { case Tree(left, value,right) tostringhefe)value.toString tostringtzight case Nil"nil case Tree (Left,value,right) Printin (toString2(5) } printintoStringts)+"
Explanation / Answer
abstract class Node
case class Node_Leaf(data: String) extends Node;
case class Node_Full(data: String, left: Node, right: Node) extends Node
case class Node_Left(data: String, left: Node) extends Node
case class Node_Right(data: String, right: Node) extends Node
object myTree extends App {
val words = List("john", "adam", "micheal",
"steve", "obama", "mellisa",
"smith", "cooper", "linda", "ilo");
def constructTree(A: List[String]): Node = {
def insert(tree: Node, value: String): Node = {
tree match {
case null => Node_Leaf(value)
case Node_Leaf(data) => if (value > data) {
Node_Left(data, Node_Leaf(value))
} else {
Node_Right(data, Node_Leaf(value))
}
case Node_Left(data, left) => if (value > data) {
Node_Left(value, Node_Left(data, left))
} else {
Node_Full(data, left, Node_Leaf(value))
}
case Node_Right(data, right) => if (value > data) {
Node_Full(data, Node_Leaf(value), right)
} else {
Node_Right(value, Node_Right(data, right))
}
case Node_Full(data, left, right) => if (value > data) {
Node_Full(data, insert(left, value), right)
} else {
Node_Full(data, left, insert(right, value))
}
}
}
var tree: Node = null;
for (item <- A) {
tree = insert(tree, item)
}
return tree
};
val f = (A: String) =>
System.out.println(A);
words.map(f);
var x = constructTree(words);
def recurseNode(A: Node, depth: Int) {
def display(data: String, depth: Int) {
for (i <- 1 to depth * 2) { System.out.print("-") }
System.out.println(data);
}
A match {
case null => {
display("[]", depth)
}
case Node_Leaf(data) => {
display(data, depth)
recurseNode(null, depth + 1)
recurseNode(null, depth + 1)
}
case Node_Full(data, left, right) => {
display(data, depth)
recurseNode(left, depth + 1)
recurseNode(right, depth + 1)
}
case Node_Right(data, right) => {
display(data, depth)
recurseNode(null, depth + 1)
recurseNode(right, depth + 1)
}
case Node_Left(data, left) => {
display(data, depth)
recurseNode(left, depth + 1)
recurseNode(null, depth + 1)
}
}
}
def output(A: Node, recurse: (Node, Int) => Unit) = {
recurse(A, 0)
}
def renderTree(A: Node) = {
output(x, recurseNode);
}
renderTree(x);
def renderSorted(A: Node, depth: Int) {
def display(data: String, depth: Int) {
System.out.println(data);
}
A match {
case null => {
}
case Node_Leaf(data) => {
display(data, depth)
}
case Node_Full(data, left, right) => {
renderSorted(left, depth + 1)
display(data, depth)
renderSorted(right, depth + 1)
}
case Node_Right(data, right) => {
renderSorted(null, depth + 1)
display(data, depth)
renderSorted(right, depth + 1)
}
case Node_Left(data, left) => {
renderSorted(left, depth + 1)
display(data, depth)
}
}
}
def sortedTree(A: Node) = {
output(x, renderSorted);
}
System.out.println("")
sortedTree(x);
}