Use the requirement in the attached zip fileUse the java files in that attached zip file
assign5/Assign5.docx Objective Create a bag, called RingBSTLinkedBag.java, to maintain a sorted list of Ring. Use the Ring.java, IntBTNode.java, IntBSTLinkedBag.java in the included zip file to create RingBTNode.java and RingBSTLinkedBag.java Also create a RingBagDriver.java, the driver class Requirements Follow the following steps in order to implement your collection. · Use the Ring.java class. It should have the Comparable interface. · Implement the RingBTNode.java class that is similar to IntBTNode but the data field is of type Ring instead of int. Then, change all methods accordingly. · Define the BST class RingBSTLinkedBag.java Implement the following methods in the RingBSTLinkedBag.java class. Remember that this is a binary search tree. 1. public void add(Ring element): adds an element to the bag. 2. public int size(): returns the number of elements in the bag. 3. public void search(String str): displays all the things that have search key equal to str. 4. public int countOccurrences(Ring element): returns the number of elements that are equal to element. 5. public boolean contains(String str) : returns true if and only if there is at least one element that has its search key equal to str. 6. public int countRange(Ring low, Ring high): returns the number of elements that are greater than or equal to low and less than or equal to high. 7. public int total(): returns the total of the field for every element used for computing aggregate information. 8. public boolean remove(Ring target):removes exactly one instance of target if it is found and returns true. Otherwise, it returns false without deleting anything. 9. public void displayLowToHigh(): displays all the elements from low to high, based on the search key. This is basically the inorder traversal of the tree. 10. public void addAll(RingBSTLinkedBag other): copies every element in other to this bag. Note that, you may adapt the add and remove methods we discussed in class. For all other methods, you must use recursive solutions. One way of doing this is to implement a private auxiliary method. For example, in IntBSTLinkedBag, for implementing countOccurrences, one could create the following private auxiliary method: private int countOccurrencesAux(IntBTNode root, int value) { if (root == null) { return 0; } int count = 0; if (root.getData() == value) { count = 1; } return count + countOccurrencesAux(root.getLeft(), value) + countOccurrencesAux(root.getRight(), value); } Then the method countOccurrences is implemented as follows: public int countOccurrences(int value) { return countOccurrencesAux(this.root,value); } assign5/IntBSTLinkedBag.java assign5/IntBSTLinkedBag.java /** * This class implements a Bag where element are organized in a BST * * Invariant of the IntBSTreeBag: * 1. the elements in the bag are stored in a binary search tree * 2. the instance variable root is a reference to the root of the binary search * tree or null for an empty tree. * */ public class IntBSTLinkedBag { private IntBTNode root; /** * constructor to create an empty bag */ public IntBSTLinkedBag(){ this.root = null;} public int size() { return IntBTNode.treeSize(this.root); } public void add(int element){ //Create IntBTNode with data = element IntBTNode newNode = new IntBTNode(element,null,null); if (root == null) //if the tree is empty, the new node becomes the root root = newNode; else{ //if the tree is not empty, start from the root and go down the tree IntBTNode cursor = root; IntBTNode parentOfCursor = null; while (cursor != null){ //need to keep track of parent of the new node parentOfCursor = cursor; if (element <= cursor.getdata()) cursor =" cursor.getLeft();" else="" cursor =" cursor.getRight();" }="" //at this point of time, the new element can be inserted as a child of parent="" =""><= parentofcursor.getdata()) parentofcursor.setleft(newnode);="" else="" parentofcursor.setright(newnode);="" }="" ="" ="" }="" ="" ///////bag traversals="" public void inordertraversal(){="" if (root !=" null)" root.inorderprint();="" }="" ="" public void postordertraversal(){="" if (root !="null)" root.postorderprint();="" }="" ="" public void preordertraversal(){="" if (root !="null)" root.preorderprint();="" }="" ="" ="" /**="" * a method to count the number of occurrences of a particular element in this bag="" * iterative implementation="" * @param target -- value to count="" * @return -- number of occurrences of target="" */="" /*="" public int countoccurrences(int target){="" ="" //start from the root, and go down the tree="" intbtnode cursor =" root;" int count =" 0;" ="" while (cursor !=" null){" ="" if (cursor.getdata() ="= target)" count++;="" if (cursor.getdata() ="">= target) cursor = cursor.getLeft(); else cursor = cursor.getRight(); } return count; } */ //****************************************************************************************/ //recursive implementation of countOccurances using an auxiliary method public int countOccurrences(int value) { return countOccurrencesAux(this.root,value); } private int countOccurrencesAux(IntBTNode root, int value) { if (root == null) return 0; int tempCount = 0; if (root.getData() == value) tempCount = 1; return tempCount + countOccurrencesAux(root.getLeft(), value) +countOccurrencesAux(root.getRight(), value); } //toString implementation that returns a String that includes //the inorder travesal of the tree public String toString() { return toStringAux(this.root); } private String toStringAux(IntBTNode root) { if (root == null) return ""; else { return toStringAux(root.getLeft()) + "\t" + root.getData() + "\t" + toStringAux(root.getRight()); } } } assign5/IntBTNode.java assign5/IntBTNode.java /** * This class provides a node for a binary tree that hold integer elements. * Invariant of the IntBTNode class: 1. Each node has one integer, stored in the * instance variable data. 2. The instance variables left and right are * references to the node's left and right children. */ public class IntBTNode { private int data; private IntBTNode left; private IntBTNode right; /** * Initialize IntBTNode with a specified initial data and links to children. * Note that a child link may be the null reference, which indicates that the * new node does not have that child. * * @param initialData -- the initial data of this new node * @param initialLeft -- a reference to the left child of this new node- * @param initialRight -- a reference to the right child of this new node- **/ public IntBTNode(int initialData, IntBTNode initialLeft, IntBTNode initialRight) { this.data = initialData; this.left = initialLeft; this.right = initialRight; } // Getters and Setters public int getData() { return data; } public void setData(int data) { this.data = data; } public IntBTNode getLeft() { return left; } public void setLeft(IntBTNode left) { this.left = left; } public IntBTNode getRight() { return right; } public void setRight(IntBTNode right) { this.right = right; } /** * Accessor method to get the data from the leftmost node of the tree below this * node. This is the minimum value if the tree is a Binary Search Tree * * @return -- the data from the deepest node that can be reached from this node * by following left links. **/ public int getLeftmostData() { if (left == null) return data; else return left.getLeftmostData(); } /** * Accessor method to get the data from the rightmost node of the tree below * this node. This is the maximum value if the tree is a Binary Search Tree * * @return -- the data from the deepest node that can be reached from this node * by following right links. **/ public int getRightmostData() { if (right == null) return data; else return right.getRightmostData(); } /** * Accessor method to determine whether a node is a leaf. * * @return -- true (if this node is a leaf) or false otherwise. **/ public boolean isLeaf() { return (this.left == null) && (this.right == null); } /** * Count the number of nodes in a binary tree. * * @param root -- a reference to the root of a binary tree which may be null * when the tree is empty * @return -- the number of nodes in the binary tree **/ public static int treeSize(IntBTNode root) { if (root == null) return 0; else return 1 + treeSize(root.left) + treeSize(root.right); } public static IntBTNode treeCopy(IntBTNode root) { if ( root == null) return null; else { IntBTNode leftCopy = treeCopy(root.left); IntBTNode rightCopy = treeCopy(root.right); return new IntBTNode(root.data,leftCopy,rightCopy); } } /////////// TREE TRAVESALS////////////////// /** * Uses a preorder traversal to print the data from each node of the binary * tree. **/ public void preorderPrint() { System.out.print(this.data + "\t"); if (left != null) left.preorderPrint(); if (right != null) right.preorderPrint(); } /** * Uses a postorder traversal to print the data from each node of the binary * tree. **/ public void postorderPrint() { if (left != null) left.postorderPrint(); if (right != null) right.postorderPrint(); System.out.print(this.data + "\t"); } /** * * Uses a inorder traversal to print the data from each node of the binary * tree. */ public void inorderPrint() { if (left != null) left.inorderPrint(); System.out.print(data + "\t"); if (right != null) right.inorderPrint(); } /** * removes the right most node of the tree with this node as its root */ public IntBTNode removeRightmost() { if (right == null) // the right most node is at the root becuase there is no right child return left; else { // a recursive call removes the rightmost node if my own right child right = right.removeRightmost(); return this; } } public IntBTNode removeLeftmost() { if (left == null) // the right most node is at the root becuase there is no right child return right; else { // a recursive call removes the rightmost node if my own right child left = left.removeLeftmost(); return this; } } public int treeSum() { if (isLeaf()) return this.getData(); else return this.getData() + this.getLeft().treeSum() + this.getRight().treeSum(); } } assign5/Ring.java assign5/Ring.java public class Ring implements Comparable
{ /** * instance variables */ private String ring; private int size; /** * Contrustor * @param ring * @param size */ public Ring(String ring, int size) { this.ring = ring; this.size = size; } /** * Getters and Setters * @return */ public String getRing() { return this.ring; } public void setRing(String ring) { this.ring = ring; } public int getSize() { return this.size; } public void setSize(int size) { this.size = size; } /** * returns a string represent a ring */ @Override public String toString() { String output = ""; output += "Ring type-" + "["+this.ring +": "; output += this.size +"]"; return output; } /** * equals method to */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Ring other = (Ring) obj; if (ring == null) { if (other.ring != null) return false; } else if (!ring.equalsIgnoreCase(other.ring)) return false; if (size != other.size) return false; return true; } /** * */ @Override public int compareTo(Ring otherRing) { int output = 0; if (this.ring.equalsIgnoreCase(otherRing.ring)) { if (this.size > otherRing.size) output = 1; else if(this.size < otherring.size) { output =" -1;" }="" else {="" output =" 0;" }="" }=""><0){ output = -1; } else { output = 1; } return output; } } output =" -1;" }="" else {="" output =" 1;" }="" return output; ="" }="">