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 *1
static private class BinaryNode
T element; // data part
BinaryNode left; // left child
BinaryNode right; // right child
// Add appropriate constructors for BinaryNode
// end of BinaryNode
private BinaryNode root; // root of the tree private final int LCHILD = 1; // constant for left child private final int RCHILD = 2; // constant for right child
// constructor for BinaryTree public BinaryTree() root = null; // construct an empty tree }
// Below are the methods that you must implement // // Create a tree with the given item as the root with its // subtrees being empty. //
Post: Previous value of the tree is lost. // public void insertRoot (T item)
// 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
// return false.
//
// Pre: data items in the tree are distinct, i.e., no duplicates.
// item, if it can be successfully inserted, is
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 the tree contents in inorder to the stream // associated with the printwriter output
public void printTree(PrintWriter output)
// Returns true if vall exists, val2 exists, and they are // siblings; otherwise, returns false
public boolean siblings (T vall, T val2)
// 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)
// delete subtree rooted at item, if item is present; // otherwise, tree remains unchanged
public void deleteSubtree (T item)
// Post: if item is present, returns reference to a string that has
// all the values stored in the leaves of the subtree
rooted at
// item; consecutive values are separated by a space.
// otherwise, returns null
public String subtreeLeaves (T item)
// Check if the subtree rooted at x in this tree and the // subtree rooted at y in the OtherTree have the same
// NUMBER of nodes
// Pre: items in each tree are distinct
// Return Value:
// 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 otherTree, T y)
// end of 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 BinaryTrcc. However, only [I] through [10] of the array elements will be used. Array elements [I] through [101 will be referred to as tree I 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 homework] 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 I (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 output 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.
deletesubtree
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.