Can someone kindly help me with this assignment!? Instructions Download a copy o
ID: 3920474 • Letter: C
Question
Can someone kindly help me with this assignment!?
Instructions
Download a copy of SimpleSet.java. Implement this interface within the package csc143.data_strctures. Name the implementation class SimpleTreeSet. Use a binary search tree as the underlying data structure.
Implementation notes:
Binary search trees require some mechanism to order the values. In keeping with the tree-based collection in java.util, this implementation of SimpleSet will use the natural order of the generic type parameter, E. This natural order is supplied by the java.lang.Comparable interface. So, your implementation can cast the values it is working with to java.lang.Comparable as required. If the object does not implement this interface, a ClassCastException will be thrown, an unchecked exception. That is to be expected. This cast is an unchecked conversion. Use the @SuppressWarnings annotation to compile without warning messages. Minimize the scope of the @SuppressWarnings annotation. My implementation uses only one, on a constructor which only contains assignments for the fields of the class.
add
The algorithm in the notes uses an expensive exception to indicate a duplicate value. For the Check Level, you may implement add using the exception mechanism. For the learning activity, do not be concerned about efficiency, that is, there is no requirement to implement any form of balancing for the underlying BST.
size
The method can be implemented using either a special field or recursive calculation.
toString
Facilitates debugging and checking. More information about toString follows this list.
Recursion is your friend. Make sure that you structure it "appropriately". That is, the recursive methods are not necessarily the methods inherited from SimpleSet.
Important:
Do NOT use any resources from the java.util package. You must create the underlying binary search tree "from scratch."
The toString Method
The toString method should show the structure of the tree, not only its contents. These shall use a pre-order traversal of the tree. Use nested parenthetical expressions, in which each tree or subtree is indicated by enclosing it in parentheses. Empty trees are indicated by ( ).
For example, given the following BST:
The nested parenthetical toString would give:
(5 (4 (2 () (3 () ())) ()) (7 (6 () ()) (9 (8 () ()) ())))
Note: There is no space immediately after the opening paren or immediately before the closing paren. However, there is one space between the value for a given node and the left subtree, and one space between the two subtrees.
Plus Level
For the Plus Level, implement the add method without using an exception to indicate a duplicate. Yes, this means that your recursive add function can return a boolean value. So, the add method of the set can return the boolean value from the recursive method.
SimpleSet.java
4 2Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// SimpleTreeSet.java
/**
* I have added a constraint to the type of E, so that it will always be a
* Comparable one, so we dont have to perform any annoying unchecked
* casts,suppressing warnings etc
*/
public class SimpleTreeSet<E extends Comparable<E>> implements SimpleSet<E> {
// attributes
private Node<E> root;
private int size;
// constructor
public SimpleTreeSet() {
root = null;
size = 0;
}
@Override
public boolean add(E e) {
if (contains(e)) {
// not adding if already exists
return false;
}
Node<E> newNode = new Node<E>(e);
if (root == null) {
// root value
root = newNode;
} else {
// adding in proper position
add(root, newNode);
}
size++; // incrementing size
return true;
}
/**
* helper method to add the new node in proper position using recursion
*/
private boolean add(Node<E> root, Node<E> newNode) {
if (root.getData().compareTo(newNode.getData()) > 0) {
// adding to the left subtree
if (root.getLeft() == null) {
// new left node
root.setLeft(newNode);
return true;
} else {
return add(root.getLeft(), newNode);
}
} else {
// adding to the right subtree
if (root.getRight() == null) {
// new right node
root.setRight(newNode);
return true;
} else {
return add(root.getRight(), newNode);
}
}
}
@Override
public void clear() {
/**
* clearing the tree
*/
root = null;
size = 0;
}
@Override
public boolean contains(E e) {
if (root == null) {
// empty tree
return false;
}
return contains(root, e);
}
/**
* helper method to check if a value exist in the tree using recursion
*/
private boolean contains(Node<E> root, E data) {
if (root == null) {
return false;
}
if (root.getData().compareTo(data) > 0) {
// checking left subtree
return contains(root.getLeft(), data);
} else if (root.getData().compareTo(data) < 0) {
// checking right subtree
return contains(root.getRight(), data);
} else {
return true; // found
}
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
return toString(root);
}
/**
* helper method to traverse the tree in inorder and return a string
* containing all nodes info, recursively
*/
private String toString(Node<E> root) {
String str = "(";
if (root == null) {
str += ")";
return str;
}
//attaching current node's data
str += root.getData() + " ";
//attaching left subtree's data
str += toString(root.getLeft()) + " ";
//attaching right subtree's data
str += toString(root.getRight());
str += ")"; //closing the brace
return str;
}
}
// Node.java
/**
* class to represent a Node in SimpleTreeSet
*/
public class Node<E> {
//attributes
private E data;
private Node<E> left;
private Node<E> right;
//constructor
public Node(E data) {
this.data=data;
left=null;
right=null;
}
//getters and setters
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
}
// Test.java
public class Test {
public static void main(String[] args) {
/**
* Creating a SimpleTreeSet and testing all methods
*/
SimpleTreeSet<Integer> intSet=new SimpleTreeSet<Integer>();
intSet.add(5);
intSet.add(4);
intSet.add(7);
intSet.add(2);
intSet.add(6);
intSet.add(9);
intSet.add(8);
intSet.add(3);
System.out.println(intSet);
System.out.println("Size: "+intSet.size());
System.out.println("Contains 2? "+intSet.contains(2));
System.out.println("Contains 55? "+intSet.contains(55));
System.out.println("Trying to add 6");
if(intSet.add(6)){
System.out.println("Successful!");
}else{
System.out.println("Failed, cannot add duplicate values!");
}
System.out.println("Trying to add 12");
if(intSet.add(12)){
System.out.println("Successful!");
}else{
System.out.println("Failed, cannot add duplicate values!");
}
System.out.println(intSet);
}
}
/*OUTPUT*/
(5 (4 (2 () (3 () ())) ()) (7 (6 () ()) (9 (8 () ()) ())))
Size: 8
Contains 2? true
Contains 55? false
Trying to add 6
Failed, cannot add duplicate values!
Trying to add 12
Successful!
(5 (4 (2 () (3 () ())) ()) (7 (6 () ()) (9 (8 () ()) (12 () ()))))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.