Project 2
Instructions
Part 1 – Design and implement a binary tree using generics
Design and implement a generic binary tree consisting of classes BT<T> and BTnode<T> and the interface BTinterface<T>.
The class BT<T> defines the instance variable root of type BTnode<T>, a default constructor which builds an empty tree and implements the methods specified by the interface BTinterface<T>.
The class BTnode<T> defines the instance variable value of type T, the instance variables left and right of type BTnode<T> representing references to the left and right child nodes, a constructor with parameter representing the value of the new node and a method getValue returning the node value.
If necessary, additional instance variables and methods could be added to the classes BT<T> and BTnode<T> (explanation should be provided for these extra resources).
The class BT<T> defines the instance variable root of type BTnode<T>, a default constructor which builds an empty tree and implements the methods specified by the interface BTinterface<T>.
The class BTnode<T> defines the instance variable value of type T, the instance variables left and right of type BTnode<T> representing references to the left and right child nodes, a constructor with parameter representing the value of the new node and a method getValue returning the node value.
If necessary, additional instance variables and methods could be added to the classes BT<T> and BTnode<T> (explanation should be provided for these extra resources).
The interface BTinterface<T> specifies the following methods that will be implemented by the class BT<T> using recursive techniques:
- inorder, preorder, postorder for tree traversal - these methods should return the corresponding string representation of the tree;
- insertLeftChild, insertRightChild - these methods take the value of the new node and the value of its parent node as parameters and return a reference to the new inserted node.
- isMember - takes the value as parameter and returns the reference to the node containing the specified value or null is the value is not in the tree.
- isLeaf - takes the value as parameter and returns true if the node containing that value is a tree leaf and false otherwise.
- getMaxLevels - returns the maximum number of tree levels.
- getNumberOfNodesAtLevel - returns the number of nodes located at a specified level;
- getTotalNumberOfTreeNodes
Part 2 – Representing and processing ancestors
The generic BT<T> class developed in Part 1 will be used as the main data structure for an application of representing and processing personal ancestors.
A binary tree can be represented as an array. At the same time, an array can be represented as a binary tree. For converting an array into a binary tree and vice versa, a level by level approach should be employed. Below is an example showing the binary tree of all known ancestors of john and its array equivalent representation where empty spaces are represented as null values.
- insertLeftChild, insertRightChild - these methods take the value of the new node and the value of its parent node as parameters and return a reference to the new inserted node.
- isMember - takes the value as parameter and returns the reference to the node containing the specified value or null is the value is not in the tree.
- isLeaf - takes the value as parameter and returns true if the node containing that value is a tree leaf and false otherwise.
- getMaxLevels - returns the maximum number of tree levels.
- getNumberOfNodesAtLevel - returns the number of nodes located at a specified level;
- getTotalNumberOfTreeNodes
Part 2 – Representing and processing ancestors
The generic BT<T> class developed in Part 1 will be used as the main data structure for an application of representing and processing personal ancestors.
A binary tree can be represented as an array. At the same time, an array can be represented as a binary tree. For converting an array into a binary tree and vice versa, a level by level approach should be employed. Below is an example showing the binary tree of all known ancestors of john and its array equivalent representation where empty spaces are represented as null values.
2.1 Consider an input text file ancestors.txt representing the values of an array of strings. The strings in the file are separated by a semicolon. Read the textfile and build a corresponding binary tree object. For example the ancestors of john illustrated above will be represented in the input file as:
john;mary;tim;lily;luke;anna;nick;null;null;helen;null;null;bill;null;null;null;
Important note. The ancestors’ names should be unique. In real situations this requirement could be fulfilled by considering the name of the person together with their birth date. For simplicity, in this project we will consider that the person names are unique.
2.2 After building the binary tree object, in a loop, the program should invite the user to select for execution one of the following operations: (1) inorder, (2) preorder, (3) postorder, (4) getMaxLevels, (5) getNumberOfNodesAtLevel, (6) getTotalNumberOfNodes, (7) isMember, (8) isLeaf, (9) insertLeftChild, (10) insertRightChild and (0) exit the loop and the program.
As a result of each operation execution, relevant information should be displayed to the user. For example, as a result of invoking inorder operation method, the tree node values should be displayed.
Important note. The ancestors’ names should be unique. In real situations this requirement could be fulfilled by considering the name of the person together with their birth date. For simplicity, in this project we will consider that the person names are unique.
2.2 After building the binary tree object, in a loop, the program should invite the user to select for execution one of the following operations: (1) inorder, (2) preorder, (3) postorder, (4) getMaxLevels, (5) getNumberOfNodesAtLevel, (6) getTotalNumberOfNodes, (7) isMember, (8) isLeaf, (9) insertLeftChild, (10) insertRightChild and (0) exit the loop and the program.
As a result of each operation execution, relevant information should be displayed to the user. For example, as a result of invoking inorder operation method, the tree node values should be displayed.
The programs should compile without errors.
Notes.
1. If an operation requires additional information, the user will be prompted to enter it.
2. The input file ancestors.txt should be generated by the students using a simple text editor such as Notepad.
3. You may assume that there are no errors in the input file.
4. Tree root is considered as located at level 0. The maximum level of the tree will be considered by counting the nodes, starting with the root, along the longest path.
1. If an operation requires additional information, the user will be prompted to enter it.
2. The input file ancestors.txt should be generated by the students using a simple text editor such as Notepad.
3. You may assume that there are no errors in the input file.
4. Tree root is considered as located at level 0. The maximum level of the tree will be considered by counting the nodes, starting with the root, along the longest path.
Submission Requirements
Submit the following before the due date listed in the Calendar:
1. All .java source files and the input textfile ancestors.txt.
2. The solution description document <YourSecondName>_P2 (.pdf or .doc / .docx) containing:
(2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 12.
2. The solution description document <YourSecondName>_P2 (.pdf or .doc / .docx) containing:
(2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 12.
INSTRUCTIONS
Project 1
Instructions
Part 1
Design and implement a generic stack class StackUMUC<T> and a generic queue class QueueUMUC<T> (these names are chosen as to avoid confusion with similar classes defined in JDK).
For StackUMUC<T> class, implement the following methods:
StackUMUC(int) // class constructor
void push(T)
T pop()
T peek()
String toString()
Design and implement a generic stack class StackUMUC<T> and a generic queue class QueueUMUC<T> (these names are chosen as to avoid confusion with similar classes defined in JDK).
For StackUMUC<T> class, implement the following methods:
StackUMUC(int) // class constructor
void push(T)
T pop()
T peek()
String toString()
For QueueUMUC<T> class, implement the following methods:
QueueUMUC(int) // class constructor
void put(T)
T get()
T peek()
String toString()
void put(T)
T get()
T peek()
String toString()
The source code of the two classes should compile without errors.
Part 2
Test the two classes StackUMUC<T> and QueueUMUC<T> for the JDK types Integer and String and for the user defined type Point. The class Point represents 2D Cartesian points having x and y as instance variables, a constructor with arguments, and the methods getX, getY and toString.
Test the two classes StackUMUC<T> and QueueUMUC<T> for the JDK types Integer and String and for the user defined type Point. The class Point represents 2D Cartesian points having x and y as instance variables, a constructor with arguments, and the methods getX, getY and toString.
The programs should compile without errors.
Submission requirements
Submission requirements
Submit the following before the due date listed in the Calendar:
1. The source files StackUMUC.java, QueueUMUC.java and the source file(s) for the test driver(s).
2. The solution description document <YourSecondName>_P1 (.pdf or .doc / .docx) containing: (2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 12
1. The source files StackUMUC.java, QueueUMUC.java and the source file(s) for the test driver(s).
2. The solution description document <YourSecondName>_P1 (.pdf or .doc / .docx) containing: (2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 12
Homework 2
Instructions
