COSC2436 – FA LAB5 – Data Structure: Generic Binary Search Tree BST and Generic AVLTree Demo

TITLE: – COSC2436 – FA LAB5 – Data Structure: Generic Binary Search Tree BST and Generic AVLTree Demo

Read input file, Write to file – Data Structure: Generic Binary Search Tree BST and Generic AVLTree Demo

Time to complete:

Two weeks for 16 weeks class – 1 week for 8 week class

HOW TO DO LAB 5 Data Structures and Algorithms in Java

From now and on yourLastName will be changed to your last name

*Step1: Read the requirement of each part.

Reuse UML of class FA2021_Student_yourLastName

Provide the pseudo-code or flowchart of main()

*Step2:

-start editor eclipse, create the project with the project name:

FA2021_LAB5_yourLastName

-add data type classes: class FA2021_Student_yourLastName

-add data structure classes: class GenericTree.java, Class GenericBST.java, GenericAVLTree.java (DOWNLOAD from the topic Binary Search Tree and AVL Tree at HOW TO DO LAB)

-Add the driver class

FA2021_StudentWithGenericTreeDataStructure_yourLastName

*Step3: follow UML and step by step in the pseudo-code to write the java code of all the classes

*Step4: compile and run the program

*Step5: debug if there are any errors to complete the program

LAB 5 REQUIREMENT

DATA TYPE CLASS

Re-use the data type class Student_yourLastName from lab3:

The class will hold the information of a student: student id (String), last name (String), first name (String), address (String), no-argument constructor, parameterized constructor.

-Then add to the class the following:

-Beside no-argument constructor, parameterized constructor, you should add to the class Student_yourLastName::

//constructor

public Student(String id) {

studentId = id;

}

//accessor method

public String getStudentId() {

return studenttId;

}

//method to compare to id of student obj to id of the current object this

public int compareTo(Student obj {

return studentId.compareTo(obj.getId());

}

DATA STRUCTURE CLASS

Download the following classes relating to the data structures from eCampus:

Class GenericTree.java

Class GenericBST.java

Class GenericAVLTree.java

DRIVER CLASS

Add the following function to the driver class and call it to print out the tree level.

//AVL always maintains the tree balanced

//This function helps you to see the different BST tree and AVL tree when insert nodes

static int treeLevel(GenericBST<FA2021_Student_yourLastName> tree, String id)

{

Int level = 0;

ArrayList<GenericBST.TreeNode< FA2021_Student_yourLastName > path =

tree.path(new FA2021_Student_yourLastName (id));

if (path.size() > level)

level = path.size();

return level;

}

In main():

Create an application that allows users to practice on implement operations of the data structure Binary Search Tree and AVL tree. The application, first, display the main menu:

FA2021_StudentWithGenericTreeDataStructure_Smith.java

SELECT TREE TYPE MAIN MENU – JAMES SMITH

———————————————————————–

1.Binary Search Tree

2.AVL Tree

0.exit

Read selected type

CREATE THE DATA STRUCTURE

If users select 1 for Type 1, create the GenericBST data structure

If users select 2 for Type 2: create the GenericAVLTree data structure.

HINT: Since GenericAVLTree is a child class of GnericBST, apply polymorphism to this situation, you should use the same object of GenericBST to point to either GenericBST data structure or GenericAVLTree data structure.

For each type of the tree do the following:

OPEN INPUT FILE – READ – INSERT EXISTING STUDENTS TO THE DATA STRUCTURE

Download file studentInfo.xlsx from eCampus then save as with extension csv with name studentInfo.csv

Open and Read the input file studentInfo.csv

For each line in the input file, read it as a string, then slit the line into pieces of information of students

For example one line from the input file:

1212121, Bellamy, Kevin, 2146545676,34 Greenville Richardson TX 75080

After split the line we have:

Student id = 1212121

Last name = Bellamy

First name = Kevin

Phone = 214555676

Address = 34 Greenville Richardson TX 75080

Create the object of class FA2021_Stuent_yourLastName with the above information and insert the object to selected data structure

Read next line and do the same until the end of the input file then close file.

DISPLAY THE TASK MENU:

FA2021_StudentWithGenericTreeDataStructure_Smith.java

SELECT TASKS MENU – JAMES SMITH

—————————————————————————-

1.Display all students in the data structure

2.Insert one new student

3.Search and Display the information of one student

4.Modify information of one student

5.Delete one student

0.Exit and Update Database

TASK 1.DISPLAY ALL STUDENTS IN THE SELECTED TREE

Display all students in the selected tree by using the operation inorder() of the tree

TASK 2.INSERT ONE NEW STUDENT

Ask information of one student about student id, last name, first name, phone, address then create the object of FA2021_Student_yourLastName, insert it to selected tree by using the operation insert()

Check result and display message: “Insert successfully” OR display message: “Insert failed”

Call the above method treeLevel() to print output level of the tree after inserting a new node

TASK 3. CHECK IF A STUDENT EXISTS – SEARCH STUDENT

Ask users to enter student id that they want to search

Create the object of Student with the id then search it in the selected tree by operation search()

If it is found, display the message “Student is found”

Otherwise, display the message “Student is not found”

TASK 4.READ INFORMATION OF ONE STUDENT

Ask users to enter student id, read (fetch) from the student from the data structure

If it exists display the information of student

———————————————-

STUDENT ID: 1234567

STUDENT NAME: Mary Lane

STUDENT PHONE: 2147251234

STUDENT ADDRESS: 123 Home street

———————————————–

Otherwise display message: “Student cannot be found”

TASK 5.UPDATE ONE STUDENT INFORMATION

Ask users to enter student id, access the method fetch() to have the object temp

Create the object named update by using copy constructor from temp

Display the menu to allow users to select information to change:

FA2021_StudentWithGenericTreeDataStructure_Smith.java

Update Information – JAMES SMITH

————————————————————————————

1. Change last name and first name

2. Change phone

3. Change address

0. DONE.

When users select one information, display message to ask new information and use the object update to access mutator method of that field to change.

When users select 0 for DONE then delete the object temp and insert the object update

If both delete and insert are success then display the message: “Update student successfully” otherwise display the message: “Update failed”

TASK 6. DELETE ONE STUDENT

Ask users to enter student id, create the student object with student id then delete the object from the tree by access the operation delete

If delete success display the message: “Delete Student successfully”; otherwise, display message: “Delete student gets failed”

Call the above method treeLevel() to print output level of the tree after inserting a new node

TASK 0.EXIT

When users select 0 before terminating the program, you should write all the student information in the tree to the output file that has the name as the name of input file studentInfo.csv

The information of one student is written on one line. The information will be separated by comma “,”

Each line in the following format:

Student id, lastname, firstname, phone, address

HOW TO TURN IN THE LAB

FA2021_LAB5_YourLastName.docx (UML, pseudocode or flowchart and output pictures)

FA2021_Student_yourLastName.java

GenericTree.java

GenericBST.java

GenericAVLTree.java

FA2021_StudentWithGenericTreeDataStructure_yourLastName.java

FA2021_Student_yourLastName.class

GenericTree.class

GenericBST.class

GenericAVLTree.class

FA2021_StudentWithGenericTreeDataStructure_yourLastName.class

HOW TO GRADE THE LAB