Problem 1: In this problem you will implement a Binary Search Tree. The tree will be storing students information which you will insert and delete. You will also implement the inOrder() tree traversal. In addition, you will implement findKthSmallest() which finds the kth smallest node key. Implement the following classes: 1. class Node that includes: Three instance variables: private int ID; private double GPA; private Node Left; private Node Right A constructor that initializes the two instance variables ID and GPA. Set and get methods for each instance variable. .toString method that returns a string containing the student id, GPA) 2. class BSTree that includes: private Node Root. public boolean exist(int id) private boolean exist(Node s, int id) that checks whether a node with the same id exists in the BST Tree or not. public boolean insert(int id, double spa) private void insert(Node R, Node 5) that inserts a new node into the binary tree. If the student ID already exists the method will return false, otherwise it will return true after inserting. public boolean remove(int ID)that removes the student with the specified ID. If the student doesn't exist the method will return false, otherwise it will return true. public void inoder() private void inorder (Node R) That traverses and prints the contents of the tree in-order according to the ID. (From least to highest ID). public int kthSmallest (Node root, int k) that returns the kth smallest node key. 3. Write a test application named TestBST. In the main method, do the following: Kuwait University Fall 2020 College of Engineering and Petroleum CpE-207: Data Structures & Department of Computer Engineering Algorithms Create a BSTree object. Display a menu to the user and asking for a choice to be entered. As follows: The program can perform the following: 1- Insert Students 2- Remove a Student 3-Check if a Student Exists 4- Print InOrder 5- Find kthSmallest 6-Exit Please enter your selection: . The program will perform the action selected by the user and display a proper message when necessary. The program will repeat these actions until the user terminates the program. Problem 2: 1. Class Node that includes the following: instance variables: int Data: String Name: A constructor that initializes the instance variables. Setter and getter methods for the instance variables. 2. Class Max Heap that includes: The following instance variables Node] heapArray; int maxSize: // size of array int currentSize: // number of Nodes in heapArray A constructor that takes the maximum size allowed for the heap. The current size of the heap is set to 0, and the array of the heap is created. public boolean insert (int key, String Name) that inserts a value at the end of the heap then calls method reheapUp to apply the actual changes to the heap. private void reheap Up (int index) that applies the actual changes to the heap after insertion. Makes sure that a child node is always less than its parent. It starts at the end of the heap and moves up. public Node remove that removes the first (root) value from the heap. It calls method reheapDown to apply the actual changes to the heap for removal. Kuwait University Fall 2020 College of Engineering and Petroleum CpE-207: Data Structures & Department of Computer Engineering Algorithms private void reheapDown(int index) applies the actual changes to the heap after remove. Makes sure that a parent node is always greater than its children. It starts at the end of the root of the heap and moves down. public boolean isEmpty that checks whether the heap is empty or not public void mergeHeaps () that merges heap a[] and b[] into one heap merged() public void printHeap that prints the contents of the heap. Write a test application named TestHeap. In the main method, do the following: o Create a heap object. Display a menu to the user asking for a choice to be entered. As follows: Please choose a number from the following list: 1- Insert Node 2. Remove a Node 3- Check if Empty 4- Merge two heaps 5- Print Heap 5- Exit Your choice is: The program will perform the action selected by the user and display a proper message when necessary. The program will repeat these actions until the user terminates the program. Problem 1: In this problem you will implement a Binary Search Tree. The tree will be storing students information which you will insert and delete. You will also implement the inOrder() tree traversal. In addition, you will implement findKthSmallest() which finds the kth smallest node key. Implement the following classes: 1. class Node that includes: Three instance variables: private int ID; private double GPA; private Node Left; private Node Right A constructor that initializes the two instance variables ID and GPA. Set and get methods for each instance variable. .toString method that returns a string containing the student id, GPA) 2. class BSTree that includes: private Node Root. public boolean exist(int id) private boolean exist(Node s, int id) that checks whether a node with the same id exists in the BST Tree or not. public boolean insert(int id, double spa) private void insert(Node R, Node 5) that inserts a new node into the binary tree. If the student ID already exists the method will return false, otherwise it will return true after inserting. public boolean remove(int ID)that removes the student with the specified ID. If the student doesn't exist the method will return false, otherwise it will return true. public void inoder() private void inorder (Node R) That traverses and prints the contents of the tree in-order according to the ID. (From least to highest ID). public int kthSmallest (Node root, int k) that returns the kth smallest node key. 3. Write a test application named TestBST. In the main method, do the following: Kuwait University Fall 2020 College of Engineering and Petroleum CpE-207: Data Structures & Department of Computer Engineering Algorithms Create a BSTree object. Display a menu to the user and asking for a choice to be entered. As follows: The program can perform the following: 1- Insert Students 2- Remove a Student 3-Check if a Student Exists 4- Print InOrder 5- Find kthSmallest 6-Exit Please enter your selection: . The program will perform the action selected by the user and display a proper message when necessary. The program will repeat these actions until the user terminates the program. Problem 2: 1. Class Node that includes the following: instance variables: int Data: String Name: A constructor that initializes the instance variables. Setter and getter methods for the instance variables. 2. Class Max Heap that includes: The following instance variables Node] heapArray; int maxSize: // size of array int currentSize: // number of Nodes in heapArray A constructor that takes the maximum size allowed for the heap. The current size of the heap is set to 0, and the array of the heap is created. public boolean insert (int key, String Name) that inserts a value at the end of the heap then calls method reheapUp to apply the actual changes to the heap. private void reheap Up (int index) that applies the actual changes to the heap after insertion. Makes sure that a child node is always less than its parent. It starts at the end of the heap and moves up. public Node remove that removes the first (root) value from the heap. It calls method reheapDown to apply the actual changes to the heap for removal. Kuwait University Fall 2020 College of Engineering and Petroleum CpE-207: Data Structures & Department of Computer Engineering Algorithms private void reheapDown(int index) applies the actual changes to the heap after remove. Makes sure that a parent node is always greater than its children. It starts at the end of the root of the heap and moves down. public boolean isEmpty that checks whether the heap is empty or not public void mergeHeaps () that merges heap a[] and b[] into one heap merged() public void printHeap that prints the contents of the heap. Write a test application named TestHeap. In the main method, do the following: o Create a heap object. Display a menu to the user asking for a choice to be entered. As follows: Please choose a number from the following list: 1- Insert Node 2. Remove a Node 3- Check if Empty 4- Merge two heaps 5- Print Heap 5- Exit Your choice is: The program will perform the action selected by the user and display a proper message when necessary. The program will repeat these actions until the user terminates the program
