Write a program in Java to implement the ADT Binary Tree part of whose definition is given below. You are...

profile5hn05974j

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<T> */

public class BinaryTree<T extends Comparable<T>> {

/* Class BinaryNode */

static private class BinaryNode<T extends Comparable<T>> {

T
BinaryNode<T>
BinaryNode<T>
element; // data part
left; // left child
right; // right child
    // Add appropriate constructors for BinaryNode
} // end of BinaryNode<T>
private BinaryNode<T> 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 val1 exists, val2 exists, and they are
    // siblings; otherwise, returns false
    public boolean siblings (T val1, 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<T>

otherTree, T y)
} // end of BinaryTree<T>

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<Integer>. 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 <n1>, <n2> is a tree number and hence is an integer between 1 and 10 inclusive, <val>, <parent>, <val1>, and <val2> are integers, and <child> 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 <n1>

Print the specified tree using inorder traversal; consult sample output for format.

insertroot <n1> <val>
Insert <val> as the root of tree <n1>.

insert <n1> <val> <parent> <child>
Insert <val> as the specified <child> of node containing <parent> in tree <n1>, if possible. Report only the failures.

frontier <n1>
Print the frontier of tree <n1>.

siblings <n1> <val1> <val2>
Check if <val1> and <val2> are siblings in tree <n1>. Report outcome.

subtreenodes <n1> <val1> <n2> <val2>
Check if the subtree of tree <n1> rooted at node containing <val1> and subtree of tree <n2> rooted at node containing <val2> have the same number of nodes. Report outcome.

deletesubtree <n1> <val>

Delete the subtree rooted at node containing <val> from tree <n1>, if possible.

leaves <n1> <val1>
Obtain a string containing all the leaves in the subtree of tree <n1> rooted at <val1>, if present. Report outcome.

Restrictions/Hints

• 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

 

 

 

 

                                    Input

 

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

 

 

 

 

 

                                          Output

 

 

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.

 

 

 

    • 8 years ago
    • 999999.99
    Answer(0)
    Bids(0)