Objective of this assignment is to reinforce understanding of Binary Trees and recursion. Write program to implement Binary Trees. You use the Node class from
Objective of this assignment is to reinforce understanding of Binary Trees and recursion.
Write program to implement Binary Trees. You use the Node class from the Java Library, or write own Binary Tree Class, and implement the methods listed below. Hint, review section 25.2 (starts on p. 930) in the text for designing and implenting binary trees using linked lists.
Data is provided for this assignment. The data is in the form of sample tree arrays, listed in the additional data file that is attached to the Assignment as a file called A8-BT-testdata.txt.
You are NOT going to read this data from thefile into program !
You will hard code the test data that is providedin A8-BT-testdata.txt, i.e., copy and paste the data. In addition, note that the sample trees use pre order and in order traversals, as indicated by the sample data array names. For example, the array named, double pre[ ] is data used for pre-order traversal, and the array named double in[ ] is for in-order traversal. After the insertion of data for each tree, you must determine whether the tree is a binary search tree or not, and provide that information in test results.
HINT: Create one tree at a time, using the data provided for that tree, execute the methods on that tree, write the results to the screen, and get a screenshot of each output.
METHODS
1. depth
if root is NULL, return -1
otherwise, determine maximum of the depths of the left and right subtrees, add 1 and return
2. max
test that root is not NULL
get the max in the left subtree, the max in the right subtree, and the data value in root
return the largest of these three values
ignore a subtree if it is empty
3. tree_sum
returns the sum of the values in all the nodes in the tree
4. tree_average
returns the average of the values in all the nodes in the tree
5. tree_is_balanced
returns true if and only if the tree is balanced
this means that the absolute value of the difference in depth between the
two subtrees of root is no more than 1.
it also means that both the left and the right subtree are balanced.
An empty tree is considered to be balanced.
if root is empty, the tree is balanced
otherwise, if either the right or the left subtree is not balanced,
then the tree is not balanced
otherwise, if the difference in depths between the left and right subtrees
is greater than one then the tree is not balanced
otherwise, the tree is balanced
TEST: To test the above methods, create 6 trees, one at a time, using the sample data and write results in the listed form shown below
Tree_Name
Binary search tree ? Yes or no // indicate whether the tree is a BST
