ENSF594-Assignment 5 Solved

ENSF 594 – Principles of Software Development II 

Lab Assignment # 5 Binary Search Tree 

You are given an input ASCII text file (input.txt) containing an arbitrary number of student records in the following format:

Operation code: 1 character ('I' for insert)

Student number: 7 characters

Student last name: 25 characters

Home department: 4 characters

Program: 4 characters

Year: 1 character 

Each record is stored as one line in the text file; i.e. there is a newline character immediately following the year. Create a Java program that does the following:

Create a Java program that does the following:

1.                   Build a binary search tree using the data from the input file. The tree should be ordered by student last name (use a case insensitive comparison). There are only unique records in the input file. Each node must contain the student data (exclude the operation code), a left child pointer, and a right child pointer.  Submit a picture of the binary search tree named BST.jpeg.

2.                   Traverse the binary search tree recursively, printing out the nodes in ascending logical order; i.e. do a depth-first, in-order tree traversal. Print the node data to a text file named (output1.txt).

3.                   Traverse the binary search tree, starting at the top level (the root node), proceeding downwards levelby-level. At each level print out the nodes from left to right. In other words, do a breadth-first traversal. You may have to use a queue to implement this. Print the node data to a text file. (output2.txt)

Be sure to use proper headings and fixed-width columns for both of the output files.

Create your own input files to test your code. Start with a file that specifies insertions of data into the tree. An official input file is available on D2L; use this file to create your output files.

You must program all the data structures for this assignment from scratch; in other words, do not use any classes from the Java libraries to implement the binary search tree or queue. Also draw a picture of the binary search tree, as it appears after processing all the insertions specified in the input file. Within each node, only show the data that is used to order the tree. The picture can be hand drawn, or you may use a graphics application to create it.

Bonus (Optional)  

Create a second version of your program, called Lab05b, which uses an AVL tree to store the input data. This version of the program should do the appropriate rotations when inserting data into the tree. Only insertions into the tree need to be handled (i.e. use an input file that specifies only insertions, and no deletions)