COSC 3A

ASSIGNMENT 3A

Assignment 3A tests your knowledge of binary search trees and AVL trees. You can and should start with the examples from the textbook/presentation and adapt them to the assignment at hand and use the appropriate names and add the additional code and requirements bellow.

Design a program/project/driver class YourNameAssignment3A and the following classes (with exact1 names, replace YourName with your actual first name or the name you go by):

Class Description YourNameTree The complete version of the user-defined Tree interface from Chapter 25

(meaning you need to add the code for all methods that were not coded in the textbook/presentation and have a “Left as an exercise” comment).

YourNameBinarySearchTree The complete version of user-defined binary search tree BST class from Chapter 25 with an inner class TreeNode. Add an additional YourNamePrint method that outputs on different lines: the number of nodes/tree size, the tree in inorder traversal, the tree in preorder traversal and the tree in post order traversal (e.g.

Tree YourNamePrint method output 2

/ \

1 3

Number of nodes: 3

Inorder: 1 2 3

Preorder: 2 1 3

Postorder: 1 3 2

YourNameAVLTree Program a complete version of the user-defined self-balancing binary

search tree AVLTree class from Chapter 26 with an AVLTreeNode inner class, that code all the methods, and uses the YourNameBinarySearchTree instead of the BST.

YourNameAssignment3A

driver class main Read 10 values from the user2 and build instances of the user-defined YourNameBinarySearchTree and YourNameAVLTree above and test/demonstrate ALL functionality/methods for both: you should call insert, search, delete, inorder, postorder, and preorder methods and call the YourNamePrint after each of them to show their functionality. In addition, for your AVL tree object, you should call the balancing methods and call the the YourNamePrint after each one.

Create a Microsoft Word screenshots document called YourNameAssignment3A-Screenshot.docx (replace YourName with your actual name) that contains screenshots of the entire JAVA source code in the editor window (for all the JAVA classes) and the entire output window (from the driver class). If the entire class JAVA source code or the output does not fit in one screenshot andc not easily readable without zooming, create multiple screenshots and add them to the document.

Submit YourNameAssignment3A.java, YourNameTree.java, YourNameBinarySearchTree.java, and YourNameAVLTree.java Java source code files and YourNameAssignment3A-Screenshots.docx screenshots document on eCampus under Assignment 3A. Do not archive the files (no ZIP, no RAR, etc) or submit other file formats. You are not going to earn any credit if the files are not named as requested.

1 Use the exact names (spelling, caps), parameters, returned values, functionality, and do not add or remove fields or methods. Yes, you may find examples in the textbook with different names and cases and with other methods, but you will need to adapt them to have this exact names and cases, to earn credit for the assignment. 2 Notice that I did not specified the type, so you can use integral values, float-values or strings.