I need help with writing this in Java PART2: BINARY SEARCH TREE DATA STRUCTURE O
ID: 3818042 • Letter: I
Question
I need help with writing this in Java
PART2: BINARY SEARCH TREE DATA STRUCTURE
OBJECTIVES
-Students know how to implement the Binary Search Tree structure: How to insert a node to a tree, How to fetch, delete or update a node on the Binary Search tree.
-Also, students know how to display the information of all nodes on the tree
REQUIREMENT
Create an application that allows users can work on the information of students with the following tasks:
1. insert one new student
2. search the information of one student
3. delete one student
4. update the address of a student
5. show all students in the structure
6. exit the program
The users can continue using the program until they want to exit During the process, the application should use Binary Search Tree as the data structure
When the tree is empty, you need to display the message to tell: “There is no student on the Binary Search Tree data structure”
To search a student, if the student does not exist in the data structure, display the message “The student cannot be found”; else display the information of the student
Lab7
If delete a student successfully, display the message: “Remove the student successfully”
If update the information of a student, display the message: “Update sucessfully”
The information of a student that is stored in the database includes Student Id, last name, first name, address, phone number.
The information of one student is displayed in the following format:
Student name: Smith, James
Student ID: 1234567
Address: 123 Abrams Road Dallas, TX 75243
Phone: 4691234567
ANALYZE AND DESIGN
-Provide the UML of the data type class relating to the student information
-Provide the pseudo-code or the flowchart of main()
WHAT YOU SHOULD KNOW TO DO THE LAB
-Review the loop to manage the menu to re-display after each task to allow users to continue using the program until users want to exit
-The switch statement to handle all tasks after users select one
-Review how to write the constructors, method toString to display information of one object -Learn about the Data structure Binary Search tree: initialize, findNode, insert, fetch, delete, update, show all the nodes -How to create an object of the data type class -How to access data members of the data type class
HOW TO DO THE LAB
-Create the project named SP2017LAB7_PART2_YourLastname
-Add data type class name SP2017LAB7_Student_yourLastName then declare all data members and provide constructors, toString
-Add data structure class of BinarySearchTree_yourLastName (using the code from the book on page 394 - 396 for your reference). Note that the code from the book missing delete the root, you should add the code to delete the root in 3 cases
-Add driver class named as SP2017LAB7_StudentInformation_yourLastName then forllow the pseudocode to write the code
Explanation / Answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package binarySearchTreeStudent
import java.io.Serializable;
import java.util.Scanner;
/**
*
* @author Rashmi Tiwari
*/
class Student implements Serializable {
private String firstName;
private String lastName;
private Integer studentId;
private String phoneNumber;
private String address;
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public Integer getStudentId() {
return studentId;
}
public void setStudentId(Integer studentId) {
this.studentId = studentId;
}
public String getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(String phoneNumber) {
this.phoneNumber = phoneNumber;
}
public String getAddress() {
return address;
}
public void setAddress(String address) {
this.address = address;
}
}
class BinaryTreeNode {
BinaryTreeNode left, right;
Student data;
/* Constructor */
public BinaryTreeNode() {
left = null;
right = null;
}
/* Constructor */
public BinaryTreeNode(Student n) {
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BinaryTreeNode n) {
left = n;
}
/* Function to set right node */
public void setRight(BinaryTreeNode n) {
right = n;
}
/* Function to get left node */
public BinaryTreeNode getLeft() {
return left;
}
/* Function to get right node */
public BinaryTreeNode getRight() {
return right;
}
/* Function to set data to node */
public Student getData() {
return data;
}
public void setData(Student data) {
this.data = data;
}
}
/* Class BST */
class BST {
private BinaryTreeNode root;
/* Constructor */
public BST() {
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty() {
return root == null;
}
/* Functions to insert data */
public void insert(Student data) {
root = insert(root, data);
}
/* Function to insert data recursively */
private BinaryTreeNode insert(BinaryTreeNode node, Student data) {
if (node == null) {
node = new BinaryTreeNode(data);
} else {
if(compare(data,node.getData())<1) {
node.left = insert(node.left, data);
} else {
node.right = insert(node.right, data);
}
}
return node;
}
public BinaryTreeNode update(Student data) {
root = insert(root, data);
return root;
}
private BinaryTreeNode update(BinaryTreeNode node, Student data) {
BinaryTreeNode bst=null;
if (isEmpty()) {
System.out.println("Tree Empty");
return bst;
} else if (search(data.getStudentId()) == null) {
System.out.println("Sorry " + data.getStudentId()+ " is not present");
return bst;
} else {
bst=search(data.getStudentId());
bst.data.setAddress(data.getAddress());
}
return bst;
}
/* Functions to delete data */
public void delete(int k) {
if (isEmpty()) {
System.out.println("Tree Empty");
} else if (search(k) == null) {
System.out.println("Sorry " + k + " is not present");
} else {
root = delete(root, k);
System.out.println(k + " deleted from the tree");
}
}
private BinaryTreeNode delete(BinaryTreeNode root, int k) {
BinaryTreeNode p, p2, n;
if (root.getData().getStudentId() == k) {
BinaryTreeNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null) {
return null;
} else if (lt == null) {
p = rt;
return p;
} else if (rt == null) {
p = lt;
return p;
} else {
p2 = rt;
p = rt;
while (p.getLeft() != null) {
p = p.getLeft();
}
p.setLeft(lt);
return p2;
}
}
if (k < root.getData().getStudentId()) {
n = delete(root.getLeft(), k);
root.setLeft(n);
} else {
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
/* Functions to count number of nodes */
/* Functions to search for an element */
public BinaryTreeNode search(int val) {
return search(root, val);
}
/* Function to search for an element recursively */
private BinaryTreeNode search(BinaryTreeNode r, int val) {
BinaryTreeNode b=null;
while (r != null){
int rval = r.getData().getStudentId();
if (val < rval) {
r = r.getLeft();
} else if (val > rval) {
r = r.getRight();
} else {
b= r;
break;
}
b = search(r, val);
}
return b;
}
/* Function for inorder traversal */
public void inorder() {
inorder(root);
}
private void inorder(BinaryTreeNode r) {
if (r != null) {
inorder(r.getLeft());
System.out.print(r.getData() + " ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder() {
preorder(root);
}
private void preorder(BinaryTreeNode r) {
if (r != null) {
System.out.print(r.getData() + " ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder() {
postorder(root);
}
private void postorder(BinaryTreeNode r) {
if (r != null) {
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() + " ");
}
}
public int compare(Student data, Student data0) {
return data.getLastName().compareTo(data0.getLastName());
}
}
/* Class BinarySearchTree */
public class BinarySearchExample {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Binary Search Tree Test ");
char ch;
/* Perform tree operations */
do {
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. Insert One new Student ");
System.out.println("2. Search Information of Student");
System.out.println("3. Delete One Student");
System.out.println("4. Update Student Address");
System.out.println("5. Show Student Information");
System.out.println("6. Check if tree is empty");
System.out.println("7. Exit the program");
int choice = scan.nextInt();
switch (choice) {
case 1:{
System.out.println("Enter Student data to insert");
Student s=new Student();
System.out.println("Enter Student First Name");
s.setFirstName(scan.next());
System.out.println("Enter Student Last Name");
s.setLastName(scan.next());
System.out.println("Enter Student Id");
s.setStudentId(scan.nextInt());
System.out.println("Enter Student Phone Number");
s.setPhoneNumber(scan.next());
System.out.println("Enter Student Address");
s.setAddress(scan.next());
bst.insert(s);
}
break;
case 2:
{
System.out.println("Enter Student Id element to search");
if(bst.search(scan.nextInt())!=null){
BinaryTreeNode b=bst.search(scan.nextInt());
System.out.println("Student Name "+b.getData().getFirstName()+" "+b.getData().getLastName());
System.out.println("Student Student Id "+b.getData().getStudentId());
System.out.println("Student Phone Number "+b.getData().getPhoneNumber());
System.out.println("Student Address "+b.getData().getAddress());
}else{
System.out.println("The student cannot be found");
}
}
break;
case 3:
System.out.println("Enter Student Id element to delete");
bst.delete(scan.nextInt());
break;
case 4:
{
System.out.println("Enter Student Address data to update");
Student s=new Student();
System.out.println("Enter Student Id");
s.setStudentId(scan.nextInt());
System.out.println("Enter Student Address");
s.setAddress(scan.next());
BinaryTreeNode b;
b=bst.update(s);
if(b==null){
System.out.println("Data can not be updated");
}else{
System.out.println("Student Data updated successfully");
}
}
break;
case 5:{
System.out.println("Enter 1 for display student in pre order");
System.out.println("Enter 2 for display student in In order");
System.out.println("Enter 3 for display student in post order");
int c=scan.nextInt();
switch(c){
case 1:
System.out.print(" Pre order : ");
bst.preorder();
break;
case 2:
System.out.print(" In order : ");
bst.inorder();
break;
case 3:
/* Display tree */
System.out.print(" Post order : ");
bst.postorder();
break;
default:
System.out.println("Invalid choice");
}
}
case 6:
System.out.println("Empty status = " + bst.isEmpty());
System.out.println("There is no student on the Binary Search Tree data structure”");
break;
case 7:
System.exit(0);
default:
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}