Write a program in Java to implement the ADT Binary Tree part of whose definition is given below. You are also to write a driver program that demonstrates the correctness of your implementation by way of taking a series of commands from a text file and carrying them out. In each binary tree that you will deal with, the values are distinct (i.e. there are no duplicates). Note: Code for binary tree that I discussed in class is available on Isidore. Feel free to use it but you will assume responsibility for the correctness. The ADT Binary Tree The only (private) data member you can use is root, as given below. However, feel free to use as many private member functions as you need. /* Class BinaryTree */ public class BinaryTree> { /* Class BinaryNode */ static private class BinaryNode> { // If node containing parent exists, and if the specified // child is absent, create the specified child of parent // with item as data element and return true; otherwise different from // each value in the tree. // Post: if insertion were successful, item is the specified child of // parent. // Parameters: // item: data item to be inserted // parent: data item of the potential parent // child == 1 => item is to be inserted as left child of parent // child == 2 => item is to be inserted as right child of parent // Return Value: // true, if insertion succeeded, and false otherwise. public boolean insertItem (T item, T parent, int child) // print to the given printwriter the frontier of the tree, // i.e., all the leaves in a right to left reading of the // leaves order; consecutive items are separated by a space public void printFrontier (PrintWriter output) // If x is in this tree, y is in otherTree, and // the subtrees referred to have the same number // of nodes, then return true; otherwise return false public boolean equalSubtreeNodes (T x, BinaryTree The driver program The purpose of your main class is to provide the driver code using which your implementation of binary tree can be tested. This code should declare an array of 11 BinaryTree. However, only [1] through [10] of the array elements will be used. Array elements [1] through [10] will be referred to as tree 1 through tree 10. This part of code prompts the user for the name of the input and output files and then proceeds to process each command in the input file. For each command processed, you should output the command itself followed by any output generated by the command. Consult homework1 for the rest of the requirements for the driver program; this applies to all the future assignments as well. The commands that the driver should process are shown below. In each command, each of , is a tree number and hence is an integer between 1 and 10 inclusive, , , , and are integers, and is either 1 (left) or 2 (right). For each of the following, consult the specification of the corresponding function as well as the sample input/output for the required actions. print Print the specified tree using inorder traversal; consult sample out
put for format. insertroot Insert as the root of tree . insert Insert as the specified of node containing in tree , if possible. Report only the failures. frontier Print the frontier of tree . siblings Check if and are siblings in tree . Report outcome. subtreenodes Check if the subtree of tree rooted at node containing and subtree of tree rooted at node containing have the same number of nodes. Report outcome. Delete the subtree rooted at node containing from tree , if possible. leaves Obtain a string containing all the leaves in the subtree of tree rooted at , if present. Report outcome. Restrictions/nts Your implementation should be as efficient as possible. Design (private) helper method(s) that can be used to design other methods. For example, it may be useful to design a method that takes a pointer (reference) to the root of a subtree and a value and locates that node containing that value in the subtree, if present. What should such a method return? Where all could this be useful? Could it really help with delete subtree ? We talked about two different ways of doing things recursively (with or without using the return values). You may find use for both the approaches. Sample input/output print 1 insertroot 1 100 insert 1 50 100 1 insert 1 80 100 2 insert 1 70 50 2 insert 1 25 80 1 insert 1 55 80 2 insert 1 30 1 100 insert 1 30 1 40 print 1 insertroot 2 20 insert 2 4 20 1 insert 2 15 20 2 insert 2 10 4 1 insert 2 2 15 1 insert 2 9 15 2 insert 2 11 9 1 insert 2 7 9 2 insert 2 5 11 1 print 2 siblings 2 7 11 siblings 2 22 11 frontier 2 leaves 2 15 leaves 2 33 subtreenodes 1 80 1 80 subtreenodes 1 100 2 15 subtreenodes 1 50 2 15 subtreenodes 1 10 2 15 deletesubtree 2 9 print 2 deletesubtree 1 30 print 1 deletesubtree 2 20 print 2 Put your name here Input file: input.txt Command: print 1 Empty tree Command: insertroot 1 100 Command: insert 1 50 100 1 Command: insert 1 80 100 2 Command: insert 1 70 50 2 Command: insert 1 25 80 1 Command: insert 1 55 80 2 Command: insert 1 30 1 100 Failed Command: insert 1 30 1 40 Failed Command: print 1 (() 50 (() 70 ())) 100 ((() 25 ()) 80 (() 55 ())) Command: insertroot 2 20 Command: insert 2 4 20 1 Command: insert 2 15 20 2 Command: insert 2 10 4 1 Command: insert 2 2 15 1 Command: insert 2 9 15 2 Command: insert 2 11 9 1 Command: insert 2 7 9 2 Command: insert 2 5 11 1 Command: print 2 ((() 10 ()) 4 ()) 20 ((() 2 ()) 15 (((() 5 ()) 11 ()) 9 (() 7 ()))) Command: siblings 2 7 11 Yes Command: siblings 2 22 11 No Command: frontier 2 7 5 2 10 Command: leaves 2 15 2 5 7 Command: leaves 2 33 Absent Command: subtreenodes 1 80 1 80 Yes Command: subtreenodes 1 100 2 15 Yes Command: subtreenodes 1 50 2 15 No Command: subtreenodes 1 10 2 15 No Command: deletesubtree 2 9 Command: print 2 ((() 10 ()) 4 ()) 20 ((() 2 ()) 15 ()) Command: deletesubtree 1 30 Command: print 1 (() 50 (() 70 ())) 100 ((() 25 ()) 80 (() 55 ())) Command: deletesubtree 2 20 Command: print 2 Empty tree Command processing completed.