Building a 2-3 tree
In this assignment you will be implementing a 2-3 tree to store int data.
Your tree will need methods to insert and find int data, find the current height of the tree, perform the split operations (all three cases as covered in the notes), and to perform preorder and inorder traversals. Do not attempt to implement a delete operation. Insert, Find, getHeight and Split may all be implemented iteratively or recursively. For preorder, output each node as a unit (that is, output all of the data currently stored in the node in one System.out.println statement so that it is clear what values are stored in that particular node). Insert should throw an exception if the number being inserted is a duplicate (this will not happen in the data, but should be implemented) and Find should throw an exception if the number being sought is not found (again, this should not happen). You will of course also have to implement a 2-3 Tree Node. The Node class will require a constructor, a toString method (if desired), get and set methods for each of the two data, and the three children. NOTE: since Java class names cannot start with a number, I recommend that you name your Node and Tree classes as Node or Node23 and Tree or Tree23 respectively (rather than say 23Node).
Implement a third, user, class, which will input a list of int values from a disk file, add each int value to the tree, and once built, perform a preorder traversal, determine the height of the tree, and find each value. You do not need to output the tree using the inorder traversal, but it might be a useful method for you during debugging. Run the program on the two sets of integer data files on the CMS site.
The output from data set one should look something like the following:
Pre order traversal:
Node values: First: 15
Node values: First: 5 Second: 13
Node values: First: 1 Second: 2
Node values: First: 8 Second: 9
Node values: First: 14
Node values: First: 19 Second: 22
Node values: First: 17 Second: 18
Node values: First: 20
Node values:
Tree height: 3 First: 25
Finding Values:
15 is first data in Node values: First: 15
20 is first data in Node values: First: 20 14 is first data in Node values: First: 14
5 is first data in Node values: First: 5 Second: 13 25 is first data in Node values: First: 25
8 is first data in Node values: First: 8 Second: 9
22 is second data in Node values: First: 19 Second: 22 1 is first data in Node values: First: 1 Second: 2
19 is first data in Node values: First: 19 Second: 22 2 is second data in Node values: First: 1 Second: 2 17 is first data in Node values: First: 17 Second: 18 13 is second data in Node values: First: 5 Second: 13
18 is second data in Node values: First: 17 Second: 18 9 is second data in Node values: First: 8 Second: 9
The input file for above example would be as below: 20, 1, 5, 2, 14, 15, 8, 19, 17, 13, 9, 18, 25, 22
Hand in your complete Java source code; and a copy of the results after running your program on given files
Upload your source code to CMS
Demonstrate your program to TA on/before/on the due day